This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. 10 IEEE COMMUNICATIONS SURVEYS TUTORIALS.ACCEPTED FOR PUBLICATION TABLE V COMPARISON OF AUTHENTICATION AND PRIVACY PROTECTION SOLUTIONS Compute Complexity in Scope of Applications Resource Requirement Flexibility Tag Side Physical Very simple.The tag is Passive tags with very Very few requirements. Not flexible.The tag is ei- Mechanism- not required to implement limited processing capac. but additional devices are ther screened or fully ex- based Solutions the logic for security and ity. required to provide secu- posed. privacy protection. rity and privacy protec- tion Symmetric-key Complex.20000-30000 Active tags or passive tags High requirement.Enough Very flexible.Encryption Encryption- logical gates are required. with higher processing ca- processing and storage ca- and decryption can be ef- based Solutions pacity to conduct encryp- pability should be guaran- fectively implemented. tion and decryption. teed. Hash Function- Simple.A simple hash Passive tags to conduct Few requirements.A hash Flexible."Forward secu- based Solutions function can be easily im- authentication. function can be realized rity"can be guaranteed, plemented. by 200 bit random series but encryption and de- stored in the tag side cryption cannot be imple- mented. Ouery metalD metalD- (key,ID)- -key Database Reader -ID- Tag The hash-lock protocol -Ouery Search and compare all +R,Hkey(IDR)- the possible -R,Hkey(IDR)- values of ID Hkey(IDR) ID Database Reader Tag The randomized hash-lock protocol Fig.6.The diagram of the hash-lock protocol and the randomized hash-lock protocol random number-based inquiry and response mechanism.When leverages the "forward security"property of hash functions the reader interrogates the tag,the tag first generates a random to update the tag response with each interrogation.In this number R using the pseudo random number generator,then it way,the replay attack can be effectively avoided.However, computes the hash value V=Hke(IDR),finally it sends the attacker can maliciously interrogate the tag multiple times, the hash value V and R to the reader.The reader conducts which breaks the synchronization between the reader and the exhaustive search over the tags and computes all possible hash tag.In this case,the authentication mechanism cannot work values V'=Hkey (IDR)according to the tag ID.If V'=V properly. for a certain tag ID,then the reader successfully identifies the tag.The above mechanism can prevent the tag from replying a fixed message in each response,which can effectively avoid D.Comparative Study malicious tracking.But it cannot prevent the replay attacks, In Table V,we compare and analyze the three kinds of since the illegal user can overhear the random number R and solutions from four aspects:compute complexity,scope of the corresponding hash value V,and replay this message when applications,resource requirement and flexibility.Note that the reader interrogates the tags,pretending to be the specified there are pros and cons for these three kinds of solutions.It tag.Fig.6 provides the diagram of the hash-lock protocol and is essential to choose a reasonable solution according to the the randomized hash-lock protocol. specific application requirements and resource limitations. The hash-chain protocol [64]utilizes a shared secret-based inquiry and response mechanism.In this protocol,the reader and the tag share two hash functions G and H,as well as E.Summing Up Challenges and Opportunities a random initial identifier s.When the reader interrogates a According to the above recent research progress,we sum- tag,the tag responds the current identifier rk=G(sk)to the marize the challenges and opportunities for authentication and reader and locally updates sk+1=H(sk).The reader searches privacy protection in Table VI,respectively for the physical the database with the identifier rk to authenticates the tag, mechanism-based solution,symmetric-key encryption-based and updates sk to synchronize with the tag.This mechanism solution,as well as Hash function-based solution.10 IEEE COMMUNICATIONS SURVEYS & TUTORIALS, ACCEPTED FOR PUBLICATION TABLE V COMPARISON OF AUTHENTICATION AND PRIVACY PROTECTION SOLUTIONS Compute Complexity in Tag Side Scope of Applications Resource Requirement Flexibility Physical Mechanism￾based Solutions Very simple. The tag is not required to implement the logic for security and privacy protection. Passive tags with very limited processing capac￾ity. Very few requirements, but additional devices are required to provide secu￾rity and privacy protec￾tion. Not flexible. The tag is ei￾ther screened or fully ex￾posed. Symmetric-key Encryption￾based Solutions Complex. 20000-30000 logical gates are required. Active tags or passive tags with higher processing ca￾pacity to conduct encryp￾tion and decryption. High requirement. Enough processing and storage ca￾pability should be guaran￾teed. Very flexible. Encryption and decryption can be ef￾fectively implemented. Hash Function￾based Solutions Simple. A simple hash function can be easily im￾plemented. Passive tags to conduct authentication. Few requirements. A hash function can be realized by 200 bit random series stored in the tag side. Flexible. “Forward secu￾rity” can be guaranteed, but encryption and de￾cryption cannot be imple￾mented. Search and compare all the possible values of Hkey(ID||R) Fig. 6. The diagram of the hash-lock protocol and the randomized hash-lock protocol random number-based inquiry and response mechanism. When the reader interrogates the tag, the tag first generates a random number R using the pseudo random number generator, then it computes the hash value V = Hkey(ID||R), finally it sends the hash value V and R to the reader. The reader conducts exhaustive search over the tags and computes all possible hash values V = Hkey(ID||R) according to the tag ID. If V = V for a certain tag ID, then the reader successfully identifies the tag. The above mechanism can prevent the tag from replying a fixed message in each response, which can effectively avoid malicious tracking. But it cannot prevent the replay attacks, since the illegal user can overhear the random number R and the corresponding hash value V , and replay this message when the reader interrogates the tags, pretending to be the specified tag. Fig.6 provides the diagram of the hash-lock protocol and the randomized hash-lock protocol. The hash-chain protocol [64] utilizes a shared secret-based inquiry and response mechanism. In this protocol, the reader and the tag share two hash functions G and H, as well as a random initial identifier s1. When the reader interrogates a tag, the tag responds the current identifier rk = G(sk) to the reader and locally updates sk+1 = H(sk). The reader searches the database with the identifier rk to authenticates the tag, and updates sk to synchronize with the tag. This mechanism leverages the “forward security” property of hash functions to update the tag response with each interrogation. In this way, the replay attack can be effectively avoided. However, the attacker can maliciously interrogate the tag multiple times, which breaks the synchronization between the reader and the tag. In this case, the authentication mechanism cannot work properly. D. Comparative Study In Table V, we compare and analyze the three kinds of solutions from four aspects: compute complexity, scope of applications, resource requirement and flexibility. Note that there are pros and cons for these three kinds of solutions. It is essential to choose a reasonable solution according to the specific application requirements and resource limitations. E. Summing Up Challenges and Opportunities According to the above recent research progress, we sum￾marize the challenges and opportunities for authentication and privacy protection in Table VI, respectively for the physical mechanism-based solution, symmetric-key encryption-based solution, as well as Hash function-based solution. This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.