A Scalable and Provably Secure Hash-Based RFID Protocol

TLDR

RFID technology must deliver benefits while safeguarding consumer privacy, yet many proposed solutions are vulnerable and existing privacy‑preserving schemes lack scalability. We aim to eliminate the scalability bottleneck of the Ohkubo–Suzuki–Kinoshita scheme by introducing a specific time‑memory trade‑off. We extend the scheme to provide a secure communication channel between RFID tags and their owners using building blocks already available on the tag. We prove the system offers privacy and forward privacy, and demonstrate its feasibility through parameter calculations in a typical use case.

Abstract

The biggest challenge for RFID technology is to provide benefits without threatening the privacy of consumers. Many solutions have been suggested but almost as many ways have been found to break them. An approach by Ohkubo, Suzuki and Kinoshita using an internal refreshment mechanism seems to protect privacy well but is not scalable. We introduce a specific time-memory trade-off that removes the scalability issue of this scheme. Additionally we prove that the system truly offer's privacy and even forward privacy. Our third contribution is an extension of the scheme which offers a secure communication channel between RFID tags and their owner using building blocks that are already available on the tag. Finally we give a typical example of use of our system and show its feasibility by calculating all the parameters.