An optimal probabilistic solution for information confinement, privacy, and security in RFID systems

In this paper, we provide the following contributions to enhance the security of RFID
based systems. First, we assume that among multiple servers storing the information related to the tags some of them can be compromised. For this new threat scenario, we
devise a technique to make RFID identification server dependent, providing a different
unique secret key shared by a tag and a server. The solution proposed requires the tag to
store just a single key, thus fitting the constraints on tag's memory. Second, we provide
a probabilistic tag identification scheme that requires the server to perform just bitwise
operations and simple list manipulation primitives, thus speeding up the identification
process. The tag identification protocol assures privacy, security and resilience to DoS
attacks thanks to its stateless nature. Moreover, we extend the tag identification protocol to achieve mutual authentication and resilience to replay attacks. The proposed identification protocol, unlike other probabilistic protocols, never rejects a legitimate tag. Furthermore, the identification protocol requires the reader to access the local Data Base (DB) of tags' keys O(n) times--where n is the number of tags in the system--, while it has been shown in the literature that a privacy preserving identification protocol requires a reader to access £(n) times this DB. In this sense, our protocol is optimal. Finally, the three features suggested in this paper, namely, reader-dependent key management, tag identification, and mutual authentication, can be independently adopted to build alternative solutions.