RFID Privacy: Relation between Two Notions, Minimal Condition, and Efficient Construction

• Main Authors: MA, Changshe, LI, Yingjiu, DENG, Robert H., LI, Tieyan
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2009
• Subjects: RFID; privacy; pseudorandom function; Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/491; http://dx.doi.org/10.1145/1653662.1653670
• Institution: Singapore Management University

Privacy of RFID systems is receiving increasing attention in the RFID community. Basically, there are two kinds of RFID privacy notions: one based on the indistinguishability of two tags, denoted as ind-privacy, and the other based on the unpredictability of the output of a protocol, denoted as unp-privacy. In this paper, the definition of unp-privacy is refined and the relation between the two notions is clarified: it is proven that ind-privacy is weaker than unp-privacy. Moreover, the minimal (necessary and sufficient) condition on RFID tags to achieve unp-privacy is determined. It is shown that if an RFID system has strong (or weak) unpprivacy then the computational power of an RFID tag can be used to construct a pseudorandom function family provided that the RFID system is complete and sound. On the other hand, if each tag is able to compute a pseudorandom function, then the tags can be used to construct an RFID system with strong (or weak) unp-privacy. In this sense, a pseudorandom function family is the minimal requirement on an RFID tag’s computational power for enforcing strong RFID system privacy. Finally, a new RFID protocol is proposed to satisfy the minimal requirement, which also outperforms the state-of-the-art RFID protocols in terms of computational cost and communication overhead.