This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. IEEE COMMUNICATIONS SURVEYS TUTORIALS.ACCEPTED FOR PUBLICATION Query- B.Symmetric-key Encryption-based Solutions 1)Symmetric-key Encryption:The public key encryption RFID Reader RFID (legal &ilegal) Tag is a powerful technique which can effectively implement -Tag ID the encryption and electronic signature.However,due to its -Bit-collision masking- complex operations,the public key encryption cannot be implemented in the RFID system,since the resource in the Recover the bits RFID tag is too few to support it.Therefore,the RFID system Blocker Tag usually leverages the symmetric-key encryption to implement Legitimate or RFID Reader Privacy Enhancement Device the security and privacy protection,as it has a much simpler processing logic.Specifically,the symmetric-key encryption Fig.5.The framework for the jamming/blocking-based protocols can be used to authenticate the tags.Algorithm 1 depicts the protocol of authenticating the tags with the symmetric- key encryption [45].In this protocol,any tag shares a distinct symmetric-key with the RFID reader. "sleep"mechanism [39]can be used to render the tags only temporarily inactive.The tag can be appropriately"waked up" Algorithm 1 Authenticate the tags with the symmetric-key when it is needed. encryption The electrostatic screening is to place the tag into a con- 1:The tag transmits the identifier T to the reader to identify tainer which can physically screen the tags from interrogation. itself. This mechanism needs an additional device like Faraday cage 2:The reader generates a random bit string R and transmits T40]as a shield against the electromagnetic coupling.Active it to the tag jamming uses a device to actively broadcast the interfering 3:The tag encrypts the bit string R with its key ki,i.e.,C= signals to prevent the unauthorized read-write operations over EiR],and transmits C to the reader. tags.Lim et al.propose an active jamming mechanism relying 4:The reader locally computes C=Eki[R],and verifies if on masking of the identifier at the PHY layer [41].In their C=C.If yes,then the tag is authenticated. cross-layer framework,the bit-collisions are induced between the backscattered tag identifier and a protective mask,such Although the above protocol can authenticate the tags,it that a legitimate reader can be allowed to recover the tag cannot effectively protect the privacy of the tag.As in step identifier but an illegitimate party would not be able to do 1 the tag needs to transmit the identifier Ti to the reader, so.The blocking method uses a special blocking tag to all adjacent RFID readers can overhear this message,which prevent unwanted scanning of tags,by exploiting the anti- completely exposes the privacy of the tag.On the other hand, collision protocol.Juels et al.propose the above idea of if the tag does not transmit the identifier T to the reader, blocking tag based on the tree-based anti-collision protocol then the reader cannot quickly find the corresponding key ki [42].Specifically,a blocking tag impedes RFID scanning by to support the following operations.In order to protect the simulating collisions in the singulation tree.Fig.5 depicts the privacy during the authentication,in fact there exists a straight- framework of the above jamming or blocking-based protocols. forward solution with poor performance:In comparison to Generally speaking,a blocker tag or a privacy enhanced device Algorithm 1,the first step is omitted,the tag does not need is used to actively broadcast a collision-bit mask when the to transmit the identifier Ti to the reader,instead it directly legal or illegal readers are interrogating the tags.Then the transmits the ciphertext C=Ei[R]according to the received legitimate reader further communicates with this device to bit string R.After receiving the ciphertext C,the reader locally recover the ID from the collision bits.Therefore,this device enumerates all possible ki to compute C=Eki[R],if there works as a proxy for the privacy-preserving interrogation. exists some key ki to satisfy Ci=C,then the tag with the Moreover,recently some researchers are using the sig- corresponding key is the one being authenticated.Assume nal spectral feature in physical layer to implement secure that there are n tags in the search space,then the compute authentication in RFID systems.Kulseng et al.propose a complexity of the search operation is O(n).When the value lightweight solution to mutual authentication for RFID sys- of n is large,the time cost of the search operation is unac- tems in which only the authenticated readers and tags can ceptable.In order to address this problem,many researchers successfully communicate with each other [43].Their proto- start to focus on how to fast search the data according to the cols are realized utilizing minimalistic cryptography such as received ciphertext.Song et al.propose practical techniques Physically Unclonable Functions(PUF)and Linear Feedback for searches on encrypted data [46].Wang et al.propose Shift Registers(LFSR),which are very efficient in hardware private information retrieval techniques using trusted hardware and particularly suitable for the low-cost RFID tags.By [47.48].In order to fast search over the encrypted data,Chiu et utilizing the dynamic bit encoding in the physical layer,Sakai al.maintain a monotonically increasing counter in the tag,and et al.propose two novel RFID backward channel protection use it to conduct fast searching based on the binary splitting protocols for privacy protection against correlation attacks in method [49]. RFID backward channel [44].By leveraging the physical layer 2)Light-weight Solution:When the length of the key ki is features,these protocols are able to greatly reduce the compute large enough(more than 128 bits),it is rather difficult to derive complexities in privacy protection and authentication. the key ki within a short time simply according to the bit string8 IEEE COMMUNICATIONS SURVEYS & TUTORIALS, ACCEPTED FOR PUBLICATION Fig. 5. The framework for the jamming/blocking-based protocols “sleep” mechanism [39] can be used to render the tags only temporarily inactive. The tag can be appropriately “waked up” when it is needed. The electrostatic screening is to place the tag into a con￾tainer which can physically screen the tags from interrogation. This mechanism needs an additional device like Faraday cage [40] as a shield against the electromagnetic coupling. Active jamming uses a device to actively broadcast the interfering signals to prevent the unauthorized read-write operations over tags. Lim et al. propose an active jamming mechanism relying on masking of the identifier at the PHY layer [41]. In their cross-layer framework, the bit-collisions are induced between the backscattered tag identifier and a protective mask, such that a legitimate reader can be allowed to recover the tag identifier but an illegitimate party would not be able to do so. The blocking method uses a special blocking tag to prevent unwanted scanning of tags, by exploiting the anti￾collision protocol. Juels et al. propose the above idea of blocking tag based on the tree-based anti-collision protocol [42]. Specifically, a blocking tag impedes RFID scanning by simulating collisions in the singulation tree. Fig.5 depicts the framework of the above jamming or blocking-based protocols. Generally speaking, a blocker tag or a privacy enhanced device is used to actively broadcast a collision-bit mask when the legal or illegal readers are interrogating the tags. Then the legitimate reader further communicates with this device to recover the ID from the collision bits. Therefore, this device works as a proxy for the privacy-preserving interrogation. Moreover, recently some researchers are using the sig￾nal spectral feature in physical layer to implement secure authentication in RFID systems. Kulseng et al. propose a lightweight solution to mutual authentication for RFID sys￾tems in which only the authenticated readers and tags can successfully communicate with each other [43]. Their proto￾cols are realized utilizing minimalistic cryptography such as Physically Unclonable Functions (PUF) and Linear Feedback Shift Registers (LFSR), which are very efficient in hardware and particularly suitable for the low-cost RFID tags. By utilizing the dynamic bit encoding in the physical layer, Sakai et al. propose two novel RFID backward channel protection protocols for privacy protection against correlation attacks in RFID backward channel [44]. By leveraging the physical layer features, these protocols are able to greatly reduce the compute complexities in privacy protection and authentication. B. Symmetric-key Encryption-based Solutions 1) Symmetric-key Encryption: The public key encryption is a powerful technique which can effectively implement the encryption and electronic signature. However, due to its complex operations, the public key encryption cannot be implemented in the RFID system, since the resource in the RFID tag is too few to support it. Therefore, the RFID system usually leverages the symmetric-key encryption to implement the security and privacy protection, as it has a much simpler processing logic. Specifically, the symmetric-key encryption can be used to authenticate the tags. Algorithm 1 depicts the protocol of authenticating the tags with the symmetric￾key encryption [45]. In this protocol, any tag shares a distinct symmetric-key with the RFID reader. Algorithm 1 Authenticate the tags with the symmetric-key encryption 1: The tag transmits the identifier Ti to the reader to identify itself. 2: The reader generates a random bit string R and transmits it to the tag. 3: The tag encrypts the bit string R with its key ki, i.e.,C = Eki[R], and transmits C to the reader. 4: The reader locally computes C = Eki[R], and verifies if C = C. If yes, then the tag is authenticated. Although the above protocol can authenticate the tags, it cannot effectively protect the privacy of the tag. As in step 1 the tag needs to transmit the identifier Ti to the reader, all adjacent RFID readers can overhear this message, which completely exposes the privacy of the tag. On the other hand, if the tag does not transmit the identifier Ti to the reader, then the reader cannot quickly find the corresponding key ki to support the following operations. In order to protect the privacy during the authentication, in fact there exists a straight￾forward solution with poor performance: In comparison to Algorithm 1, the first step is omitted, the tag does not need to transmit the identifier Ti to the reader, instead it directly transmits the ciphertext C = Eki[R] according to the received bit string R. After receiving the ciphertext C, the reader locally enumerates all possible ki to compute C = Eki[R], if there exists some key ki to satisfy Ci = C, then the tag with the corresponding key is the one being authenticated. Assume that there are n tags in the search space, then the compute complexity of the search operation is O(n). When the value of n is large, the time cost of the search operation is unac￾ceptable. In order to address this problem, many researchers start to focus on how to fast search the data according to the received ciphertext. Song et al. propose practical techniques for searches on encrypted data [46]. Wang et al. propose private information retrieval techniques using trusted hardware [47, 48]. In order to fast search over the encrypted data, Chiu et al. maintain a monotonically increasing counter in the tag, and use it to conduct fast searching based on the binary splitting method [49]. 2) Light-weight Solution: When the length of the key ki is large enough (more than 128 bits), it is rather difficult to derive the key ki within a short time simply according to the bit string This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.