Privacy-Preserving Mutual Authentication in RFID with Designated Readers

We study privacy-preserving mutual authentication in radio-frequency identification systems with designated readers (PP-MADR in short). In PP-MADR, each tag has its designated-reader group instead of all readers, and only tags and their designated readers can authenticate each other. Other readers and adversaries cannot trace tags or know their designated readers. The most challenging task of constructing such a PP-MADR protocol is the verification of reader designation without compromising tag privacy. We found that traditional solutions are impractical due to linear storage growth on tags, linear computation growth on tags, or requiring new key generations for designated readers. In this paper, we show how to construct such an efficient PP-MADR protocol. In our protocol, each tag stores constant-size secret state and performs constant-time computation for mutual authentication. When a tag is created, the server does not generate new private keys for designated readers. Our protocol captures the strong privacy property, where tags cannot be traced and designated readers cannot be distinguished, even if tags are corrupted by adversaries.