Scalable RFID systems: a privacy preserving protocol with constant-time identification

A machine readable memory medium on which are stored machine executable instructions, which when executed by a processor, carry out a plurality of functions for securely identifying and authenticating radio frequency identification (RFID) tags while maintaining privacy, including:

• (a) creating a database in which the RFID tags are identified;
• (b) generating a random nonce that can be conveyed to a RFID tag that is to be identified;
• (c) processing a first hash value and a second hash value that has been conveyed from the RFID tag that is to be identified, the first hash value being computed as a function of a unique pseudonym and a current value of a counter of the RFID tag, and the second hash value being computed by the RFID tag as a function of the random nonce, the unique pseudonym, and the current value of the counter of the RFID tag;
• (d) accessing the database to identify the RFID tag as a function of the first hash value conveyed from the RFID tag, the database also associating the unique pseudonym, the secret key, and a new pseudonym for the RFID tag with the first hash value;
• and
• (e) if successful in identifying the RFID tag, authenticating that the RFID tag for which the first and the second hash values were computed is the RFID tag that was identified in the database, by using the second hash value to confirm that the RFID tag being identified had the secret key that was stored in the database for the RFID tag.