This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. XIE er al:MANAGING RFID DATA:CHALLENGES.OPPORTUNITIES AND SOLUTIONS 9 R and the ciphertext C.In this situation.the symmetric-key which employs a novel sparse tree architecture,such that the encryption-based protocols have high security.However,due key of every tag is independent from one another. to the limitation of manufacturing cost,the off-the-shelf RFID The group-based approaches are another novel authentica- tags often have limited memory which is less than 512 bits, tion schemes which improves the tradeoff between scalability the number of logical gates is also very limited.In practical and privacy by dividing the tags into a number of tags.Hoque use of RFID systems,the length of bit string R.C and ki et al.propose a group-based anonymous private authentication is much less than the expected value to achieve the security protocol,which provides unlinkability and thereby preserves standard.For example,Texas Instruments Inc.has devised the privacy [58].The adversary cannot link the responses with encrypted RFID tags used for vehicle security alarm systems. the tags in the protocol,even if he/she can learn the identifier In consideration of the tag cost,the length of the bit string R that the tags are using to produce the response.Based on the and the key k;is only 40 bits,the length of tag response C group-based method,Gong et al.design a fine-grained batch is only 24 bits.In this situation,techniques like the reverse authentication scheme [59],which provides authentication engineering and password cracking can be used to crack the results with accurate estimates of the number of counterfeiting encryption systems.In order to address the above problem, tags and genuine tags. the researchers have proposed various kinds of lightweight While a tree-based approach achieves high performance in solutions to guarantee security.DESL [50]is a lightweight key authentication,it suffers from the issue of low privacy extension based on the traditional encryption protocol DES.It should a fraction of tags be compromised.On the contrary, is specially devised to accommodate the resource requirement while group-based key authentication is relatively invulnerable for those tiny computing devices like the RFID tags.HIGHT to compromise attacks,it is not scalable to the large number of [51]is a protocol based on block encryption algorithm,which tags.Therefore,recently several new techniques are proposed utilizes the 64-bit block and 128-bit key.The subkeys are for private authentication based on various structures.Sakai generated during the process of encryption and decryption,et al.propose a new private tag authentication protocol based which has a low requirement for the hardware resources. on skip lists [60].Without sacrificing the authentication per- Realizing that most lightweight protocols are not fully con- formance,their scheme provides a strong privacy preserving forming to the Gen2 standard,Sun et al.propose a novel mechanism.In order to achieve forward secrecy and resistance authentication protocol based on Gen2,called Gen2+,for low- to attacks,Yao et al.propose a lightweight RFID private cost RFID tags.Gen2+is a multiple round protocol using authentication protocol based on the random walk concept shared pseudonyms and Cyclic Redundancy Check (CRC)to [611 achieve reader-to-tag authentication.Their protocol follows every message flow in Gen2 to provide backward compatibility C.Hash Function-based Solutions 52]. 3)Efficient Key Management:Recently a number of re- In comparison to the symmetric-key encryption,in most searchers have turned their attention to the privacy-preserving cases an equivalent security mechanism can be implemented authentication in RFID systems.The key technical issue is using the hash functions,but the implementation logic can be how can a reader and tag that share a secret efficiently greatly simplified.Therefore,in recent years many researchers authenticate each other without revealing their identities to have focused on implementing a lightweight security mech- an adversary [53].In order to tackle the above problem,an anism using the hash function-based solutions.In regard to essential method is to implement the efficient key management the RFID systems,although the implementation logic of hash in RFID systems.Based on how keys are managed in the function is fairly simple,it still exceeds the resource limitation system,the privacy preserving tag authentications proposed in of RFID tags.Therefore,the hash function in the RFID system the past can be mainly categorized into tree-based and group- should be further simplified.It is found that,the hash value based approaches. can be derived from a pool of random bits pre-stored in the The tree-based approaches employ tree structures to achieve tag's onboard memory [33].First,a string of 200 random bits fast authentication,which allow any pair of tags to share a can be generated for each tag by an offline random number number of key components.Dimitriou propose a lightweight generator,using the tag ID as the seed.The random bits are protocol to the RFID privacy problem,which has the potential then stored in the tag.These bits form a logical ring.Then the to guarantee user privacy without requiring changes to existing hash function H(ID,r)returns a certain number of bits after infrastructure or reducing business value from the use of RFID the rth bit in the ring.200 random bits provide 200 different technology [54].Lu et al.propose a strong and lightweight hash values,which are sufficient for general purpose usage. RFID private authentication protocol,SPA [55].By designing The hash function-based protocols mainly include the hash- a novel key updating method,they achieve the forward secrecy lock protocol,the randomized hash-lock protocol,and the hash in SPA with an efficient key search algorithm.To address the chain protocol.Instead of using the real tag ID Ti,the hash- heavy computational demand for the tree-based authentication,lock protocol [62]utilizes the metalD (the hash value of the Li et al.design two privacy-preserving protocols based on tag's key)for effective authentication to the RFID reader.In cryptographical encoding [56].which significantly reduces this way,the tag's ID can avoid being revealed.However, both authentication data transmitted by each tag and computa-as the metalD keeps unchanged for any tag,if the fixed tion overhead incurred at the reader.To address compromising metalD is used in each response for a specified tag,then the attacks in the tree-based key management structure,Lu et al.RFID system is vulnerable to malicious tracking and replay propose an anti-compromising authentication protocol [57]. attacks.The randomized hash-lock protocol [63]utilizes aXIE et al.: MANAGING RFID DATA: CHALLENGES, OPPORTUNITIES AND SOLUTIONS 9 R and the ciphertext C. In this situation, the symmetric-key encryption-based protocols have high security. However, due to the limitation of manufacturing cost, the off-the-shelf RFID tags often have limited memory which is less than 512 bits, the number of logical gates is also very limited. In practical use of RFID systems, the length of bit string R, C and ki is much less than the expected value to achieve the security standard. For example, Texas Instruments Inc. has devised the encrypted RFID tags used for vehicle security alarm systems. In consideration of the tag cost, the length of the bit string R and the key ki is only 40 bits, the length of tag response C is only 24 bits. In this situation, techniques like the reverse engineering and password cracking can be used to crack the encryption systems. In order to address the above problem, the researchers have proposed various kinds of lightweight solutions to guarantee security. DESL [50] is a lightweight extension based on the traditional encryption protocol DES. It is specially devised to accommodate the resource requirement for those tiny computing devices like the RFID tags. HIGHT [51] is a protocol based on block encryption algorithm, which utilizes the 64-bit block and 128-bit key. The subkeys are generated during the process of encryption and decryption, which has a low requirement for the hardware resources. Realizing that most lightweight protocols are not fully con￾forming to the Gen2 standard, Sun et al. propose a novel authentication protocol based on Gen2, called Gen2+, for low￾cost RFID tags. Gen2+ is a multiple round protocol using shared pseudonyms and Cyclic Redundancy Check (CRC) to achieve reader-to-tag authentication. Their protocol follows every message flow in Gen2 to provide backward compatibility [52]. 3) Efficient Key Management: Recently a number of re￾searchers have turned their attention to the privacy-preserving authentication in RFID systems. The key technical issue is how can a reader and tag that share a secret efficiently authenticate each other without revealing their identities to an adversary [53]. In order to tackle the above problem, an essential method is to implement the efficient key management in RFID systems. Based on how keys are managed in the system, the privacy preserving tag authentications proposed in the past can be mainly categorized into tree-based and group￾based approaches. The tree-based approaches employ tree structures to achieve fast authentication, which allow any pair of tags to share a number of key components. Dimitriou propose a lightweight protocol to the RFID privacy problem, which has the potential to guarantee user privacy without requiring changes to existing infrastructure or reducing business value from the use of RFID technology [54]. Lu et al. propose a strong and lightweight RFID private authentication protocol, SPA [55]. By designing a novel key updating method, they achieve the forward secrecy in SPA with an efficient key search algorithm. To address the heavy computational demand for the tree-based authentication, Li et al. design two privacy-preserving protocols based on cryptographical encoding [56], which significantly reduces both authentication data transmitted by each tag and computa￾tion overhead incurred at the reader. To address compromising attacks in the tree-based key management structure, Lu et al. propose an anti-compromising authentication protocol [57], which employs a novel sparse tree architecture, such that the key of every tag is independent from one another. The group-based approaches are another novel authentica￾tion schemes which improves the tradeoff between scalability and privacy by dividing the tags into a number of tags. Hoque et al. propose a group-based anonymous private authentication protocol, which provides unlinkability and thereby preserves privacy [58]. The adversary cannot link the responses with the tags in the protocol, even if he/she can learn the identifier that the tags are using to produce the response. Based on the group-based method, Gong et al. design a fine-grained batch authentication scheme [59], which provides authentication results with accurate estimates of the number of counterfeiting tags and genuine tags. While a tree-based approach achieves high performance in key authentication, it suffers from the issue of low privacy should a fraction of tags be compromised. On the contrary, while group-based key authentication is relatively invulnerable to compromise attacks, it is not scalable to the large number of tags. Therefore, recently several new techniques are proposed for private authentication based on various structures. Sakai et al. propose a new private tag authentication protocol based on skip lists [60]. Without sacrificing the authentication per￾formance, their scheme provides a strong privacy preserving mechanism. In order to achieve forward secrecy and resistance to attacks, Yao et al. propose a lightweight RFID private authentication protocol based on the random walk concept [61]. C. Hash Function-based Solutions In comparison to the symmetric-key encryption, in most cases an equivalent security mechanism can be implemented using the hash functions, but the implementation logic can be greatly simplified. Therefore, in recent years many researchers have focused on implementing a lightweight security mech￾anism using the hash function-based solutions. In regard to the RFID systems, although the implementation logic of hash function is fairly simple, it still exceeds the resource limitation of RFID tags. Therefore, the hash function in the RFID system should be further simplified. It is found that, the hash value can be derived from a pool of random bits pre-stored in the tag’s onboard memory [33]. First, a string of 200 random bits can be generated for each tag by an offline random number generator, using the tag ID as the seed. The random bits are then stored in the tag. These bits form a logical ring. Then the hash function H(ID, r) returns a certain number of bits after the rth bit in the ring. 200 random bits provide 200 different hash values, which are sufficient for general purpose usage. The hash function-based protocols mainly include the hash￾lock protocol, the randomized hash-lock protocol, and the hash chain protocol. Instead of using the real tag ID Ti, the hash￾lock protocol [62] utilizes the metaID (the hash value of the tag’s key) for effective authentication to the RFID reader. In this way, the tag’s ID can avoid being revealed. However, as the metaID keeps unchanged for any tag, if the fixed metaID is used in each response for a specified tag, then the RFID system is vulnerable to malicious tracking and replay attacks. The randomized hash-lock protocol [63] utilizes a This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination