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 Tag A 1Ta熙H Expected State Observed ) State Polling Cannot decide if tag Tag E,F are Tag His C is missing,false Results missing positive error. missing. Fig.4.An example of the polling mechanism in slotted ALOHA-based protocol TABLE IV bits,while the user memory can only store 512 bits.Hence, CHALLENGES AND OPPORTUNITIES FOR ANTI-COLLISION ALGORITHMS the tag's scarce resource cannot support the implementation Mechanism Challenges Opportunities of the above encryption and decryption operations.Therefore, Tag Iden- Ensuring time-efficiency Dynamically adjusting the greatest challenge to the security and privacy protection tification in realistic situations. the parameters like in RFID systems lies in how to implement the authentication the reader's power,the scanning angle,and the and privacy protection protocols in a lightweight approach.In frame size can effectively the following subsections,we elaborate more on the related improve the actual research work respectively in physical mechanism-based so- performance. Estimating Ensuring both the The regular probability lutions,symmetric-key encryption-based solutions,and hash the Tag accuracy and the time- distribution in Monte function-based solutions. Size efficiency for estimation. Carlo method contributes to accurate estimation. Polling Ensuring time-efficiency Pseudo randomness can the Tags while reducing false be leveraged for effective A.Physical Mechanism-based Solutions positive/negative errors. polling. The privacy problem of RFID system is caused by the lack of authentication when the RFID reader interrogates the tags.Without the privacy protection,any RFID reader can IV.AUTHENTICATION AND PRIVACY PROTECTION privately interrogate the surrounding tags to obtain their ID. PROTOCOLS In regard to those encrypted tags which cannot be directly The premise of efficient RFID data management is to identified,they can still be tracked by the illegal readers guarantee the security and privacy of RFID data.The threats according to the backscattered encrypted messages.In order to of RFID systems mainly come from the unauthorized access protect the users'privacy in RFID systems,a straightforward to the tags and the existence of counterfeit tags.Specifically. approach is to utilize the physical mechanism-based solutions. the security problem is how to effectively authenticate the tags which mainly include tag killing,electrostatic screening,active when there exist counterfeit tags;the privacy problem is how jamming and blocking. to prevent the illegal access from the readers to preserve the The tag killing is actually a brute-force operation.In order users'privacy. to prevent a tag from illegal eavesdropping,the reader simply For conventional solutions in network security,there are deactivates a tag by sending a"kill"command with a tag- already some encryption and decryption algorithms like DES, specific PIN.When a tag receives a "kill"command from AES,RSA and ECC.They can implement functions like the reader,it renders itself permanently inoperative.In this encryption and authentication,such that the illegal access,respect,the killing operation leads to loss of primary functions spoofing,eavesdropping and replay attack can be effec- for RFID tags,while preventing arbitrary interrogation and tively resisted.However,they require a large number of tracking from illegal users,since "dead tags tell no tales" logic processing units on the chip,e.g..AES requires about Apparently,it is not a very reasonable solution to completely 20000~30000 logic gates,whereas RSA and ECC require deactivate a tag.Sarma et al.propose a solution to partially more logic gates to implement their functions. erase the unique part of identification code while keeping the Due to the low cost limitation of RFID tags,conventionally other part including the category ID [38].In this way,the one RFID tag can only have 5000~10000 logic gates.More-tag can be prevented from being tracked,while sacrificing the over,these logic gates are mainly used to implement the basic unique identification.Inoue et al.propose to use a new identifi- functions of the tag,leaving very few gates for the security cation code to replace the former code for unique identification functions.Besides,the tag's on-board memory is also rather [39].The former identification code can be reactivated when limited,conventionally the EPC memory can only store 96 the tag is recycled.In consideration of reusing the tags,theXIE et al.: MANAGING RFID DATA: CHALLENGES, OPPORTUNITIES AND SOLUTIONS 7 0 0 1 0 C 0 0 C 1 1 0 0 Tag A Tag B Tag C Tag D Tag E Tag F Tag G Tag H Ă 0 0 1 0 C 0 0 Ă 0 1 0 0 0 Expected State Observed State Polling Results Tag E,F are missing Tag H is missing. Cannot decide if tag C is missing, false positive error. Fig. 4. An example of the polling mechanism in slotted ALOHA-based protocol TABLE IV CHALLENGES AND OPPORTUNITIES FOR ANTI-COLLISION ALGORITHMS Mechanism Challenges Opportunities Tag Iden￾tification Ensuring time-efficiency in realistic situations. Dynamically adjusting the parameters like the reader’s power, the scanning angle, and the frame size can effectively improve the actual performance. Estimating the Tag Size Ensuring both the accuracy and the time￾efficiency for estimation. The regular probability distribution in Monte Carlo method contributes to accurate estimation. Polling the Tags Ensuring time-efficiency while reducing false￾positive/negative errors. Pseudo randomness can be leveraged for effective polling. IV. AUTHENTICATION AND PRIVACY PROTECTION PROTOCOLS The premise of efficient RFID data management is to guarantee the security and privacy of RFID data. The threats of RFID systems mainly come from the unauthorized access to the tags and the existence of counterfeit tags. Specifically, the security problem is how to effectively authenticate the tags when there exist counterfeit tags; the privacy problem is how to prevent the illegal access from the readers to preserve the users’ privacy. For conventional solutions in network security, there are already some encryption and decryption algorithms like DES, AES, RSA and ECC. They can implement functions like encryption and authentication, such that the illegal access, spoofing, eavesdropping and replay attack can be effec￾tively resisted. However, they require a large number of logic processing units on the chip, e.g., AES requires about 20000∼30000 logic gates, whereas RSA and ECC require more logic gates to implement their functions. Due to the low cost limitation of RFID tags, conventionally one RFID tag can only have 5000∼10000 logic gates. More￾over, these logic gates are mainly used to implement the basic functions of the tag, leaving very few gates for the security functions. Besides, the tag’s on-board memory is also rather limited, conventionally the EPC memory can only store 96 bits, while the user memory can only store 512 bits. Hence, the tag’s scarce resource cannot support the implementation of the above encryption and decryption operations. Therefore, the greatest challenge to the security and privacy protection in RFID systems lies in how to implement the authentication and privacy protection protocols in a lightweight approach. In the following subsections, we elaborate more on the related research work respectively in physical mechanism-based so￾lutions, symmetric-key encryption-based solutions, and hash function-based solutions. A. Physical Mechanism-based Solutions The privacy problem of RFID system is caused by the lack of authentication when the RFID reader interrogates the tags. Without the privacy protection, any RFID reader can privately interrogate the surrounding tags to obtain their ID. In regard to those encrypted tags which cannot be directly identified, they can still be tracked by the illegal readers according to the backscattered encrypted messages. In order to protect the users’ privacy in RFID systems, a straightforward approach is to utilize the physical mechanism-based solutions, which mainly include tag killing, electrostatic screening, active jamming and blocking. The tag killing is actually a brute-force operation. In order to prevent a tag from illegal eavesdropping, the reader simply deactivates a tag by sending a “kill” command with a tag￾specific PIN. When a tag receives a “kill” command from the reader, it renders itself permanently inoperative. In this respect, the killing operation leads to loss of primary functions for RFID tags, while preventing arbitrary interrogation and tracking from illegal users, since “dead tags tell no tales”. Apparently, it is not a very reasonable solution to completely deactivate a tag. Sarma et al. propose a solution to partially erase the unique part of identification code while keeping the other part including the category ID [38]. In this way, the tag can be prevented from being tracked, while sacrificing the unique identification. Inoue et al. propose to use a new identifi- cation code to replace the former code for unique identification [39]. The former identification code can be reactivated when the tag is recycled. In consideration of reusing the tags, the This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination