Rfid Privacy: Relation between Two Notions, Minimal Condition, and Efficient Construction
Abstract
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.