Title: Anonymous RFID authentication supporting constant-cost key-lookup against active adversaries

Authors: M. Burmester, B. De Medeiros, R. Motta

Addresses: Department of Computer Science, Florida State University, Tallahassee, FL 32306, USA. ' Google Inc., 1600 Amphitheatre Pkwy, Mountain View, CA 94043. ' Department of Computer Science, Florida State University, Tallahassee, FL 32306, USA

Abstract: In the absence of sufficiently optimised public key constructions, anonymous authentication for Radio-Frequency Identification Devices (RFIDs) requires state synchronisation between tags and a trusted server. Active adversaries disrupt this synchrony, making a recovery strategy necessary. In some protocols, tags recover by replaying previously used values, thus compromising unlinkability of their transcripts; other schemes require servers to search through the set of issued keys, incurring costs that are not constant with the number of legitimate tags. This article describes an approach based on a lightweight trapdoor one-way function from modular squaring. The solution exploits the fact that synchrony can be recovered even if tags are endowed with only the ability to perform public-key operations, whilst the trusted server is capable of trapdoor computations. The construction is provably secure and generic, transforming any anonymous, challenge-response RFID authentication protocol into another that is robust against active adversaries and supports constant key-lookup cost.

Keywords: anonymous authentication; lightweight cryptography; provably secure protocols; RFID devices; radio frequency identification; RFID security; scalable security; unlinkability; modular squaring; RFID authentication protocols; constant cost key lookup; state synchronisation; RFID tags; trusted servers.

DOI: 10.1504/IJACT.2008.021082

International Journal of Applied Cryptography, 2008 Vol.1 No.2, pp.79 - 90

Available online: 03 Nov 2008 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article