Citation: A. Juels. Minimalist Cryptography for RFID Tags. In C. Blundo, ed., Security of Communication Networks (SCN), pp.149—164. 2004
Abstract: Cryptography offers an abundance of tools for protecting privacy and enforcing strong authentication. Basic RFID tags, however, are not presently believed to have enough computational power to perform even the most rudimentary cryptographic algorithms. RSA Laboratories has elaborated a framework for "minimalist cryptography" in RFID tags -- that is, achievement of the goals of cryptography under the special constraints posed by RFID.
One of the key ideas in this work is the application of pseudonyms to
help enforce privacy in RFID tags. In a nutshell, a tag may carry multiple,
random-looking names. Each time it is queried, the tag releases a different
name. In principal, then only a valid verifier can tell when two different
names belong to the same tag. Of course, an adversary could query a tag
multiple times to harvest all names so as to defeat the scheme. The approach
described here involves some special enhancements to help prevent this.
First, tags release their names only at a certain (suitably slow) prescribed
rate. Second, pseudonyms can be refreshed by authorized readers.