International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: RFID Security: Tradeoffs between Security and Efficiency

Ivan Damgård
Michael {\O}stergaard
Search ePrint
Search Google
Abstract: Recently, Juels and Weis defined strong privacy for RFID tags. We add to this definition a completeness and a soundness requirement, i.e., a reader should accept valid tags and only such tags. For the case where tags hold independent keys, we prove a conjecture by Juels and Weis, namely in a strongly private and sound RFID system using only symmetric cryptography, a reader must access virtually all keys in the system when reading a tag. It was already known from work by Molnar et al. that when keys are dependent, the reader only needs to access a logarithmic number of keys, but at a cost in terms of privacy: for that system, strong privacy is lost if an adversary corrupts only a single tag. We propose protocols offering a new range of tradeoffs between security and efficiency. For instance the number of keys accessed by a reader to read a tag can be significantly smaller than the number of tags while retaining security, as long as we assume suitable limitations on the adversary.
  title={RFID Security: Tradeoffs between Security and Efficiency},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols, RFID security, symmetric cryptography, protocols},
  note={ 13360 received 7 Jul 2006, last revised 31 Jul 2006},
  author={Ivan Damgård and Michael {\O}stergaard},