Privacy versus scalability in radio frequency identification systems

Embedding a Radio Frequency Identification (RFID) tag into individual items enables the unique identification of such items over the wireless medium, without the need for a line-of-sight path. One of the main challenges for the successful commercialization of the RFID technology is the efficient, yet private, identification of low-cost tags in the presence of adversaries attempting to illegally track users via tags in their possession. An RFID system consists of two functional components, namely, the interactive protocol between RFID reader-tag pairs and the reader-database information retrieval mechanism. Because of the large number of tags in a typical RFID system, the private identification of tags can be a challenging problem. In this paper, we investigate privacy-preserving RFID systems and classify them based on the computational efficiency of tag identification. We show the close relation between the degree of privacy achieved by the reader-tag interaction and the reader-database information retrieval complexity.