Date Added: Apr 2010
In RFID literature, most "Privacy-preserving" protocols require the reader to search all tags in the system in order to identify a single tag. In another class of protocols, the search complexity is reduced to be logarithmic in the number of tags, but it comes with two major drawbacks: it requires a large communication overhead over the fragile wireless channel, and the compromise of a tag in the system reveals secret information about other, uncompromised, tags in the same system. In this work, the authors take a different approach to address time-complexity of private identification in large-scale RFID systems. They utilize the special architecture of RFID systems to propose the first symmetric-key privacy-preserving authentication protocol for RFID systems with constant-time identification.