A Privacy-friendly RFID Protocol using Reusable Anonymous Tickets

A majority of the existing privacy-friendly RFID protocols use the output of a cryptographic hash function in place of real identity of an RFID tag to ensure anonymity and untraceability. In order to provide unique identification for the tags, these protocols assume that the hash functions are collision resistant. We show that, under this assumption on the hash functions, a substantial number of the existing protocols suffer from a traceability problem that causes differentiating a tag from another. We propose a scalable privacy-friendly RFID protocol and describe its design and implementation issues. Our protocol substitutes the hash functions used for identification with anonymous tickets, thus avoiding the aforementioned traceability problem. The anonymous tickets are reusable. They nevertheless identify the tags uniquely, at any given point in time. The query and search algorithm of our proposed protocol is of O(1) time complexity, and it imposes small storage overhead on the backend database. We show that the protocol is scalable, and compare its storage and computational requirements to some existing protocols. We formally prove the security requirements of our protocol, and mechanically analyze some of its requirements using the model checker OFMC.