We address these issues through an RFID pseudonym protocol. Each time it is queried, the RFID tag emits a different pseudonym using a pseudo-random function. Without consent of a special Trusted Center that shares secrets with the tag, it is infeasible to map the pseudonym to the tag's real identity. We present a scheme for RFID pseudonyms that works with legacy, untrusted readers, requires only one message from tag to reader, and is scalable: decoding tag pseudonyms takes work logarithmic in the number of tags. Our scheme further allows for time-limited delegation, so that we can give an RFID reader the power to disambiguate a limited number of pseudonyms without further help from the Trusted Center. We show how RFID pseudonyms facilitate the transfer of ownership of RFID tags between mutually distrustful parties.
Our scheme requires only limited cryptographic functionality from the tag: we need a pseudo-random function (PRF) and the ability to update tag state or to generate random numbers. Tag storage and communication requirements are modest: we give example parameters for a deployment of one million tags in which each tag stores only $128$ bits, makes $6$ PRF evaluations, and sends $158$ bits each time it is read.
Category / Keywords: cryptographic protocols / RFID private authentication Publication Info: Abbreviated version in Selected Areas in Cryptography 2005. This is the long version Date: received 7 Sep 2005 Contact author: dmolnar at eecs berkeley edu Available format(s): PDF | BibTeX Citation Version: 20050912:121127 (All versions of this report) Discussion forum: Show discussion | Start new discussion