Abstract. We provide a formal model for identification schemes. Under this model, we give strong definitions for security and privacy. Our model captures the notion of a powerful adversary who can monitor all communications, trace tags within a limited period of time, corrupt tags, and get side channel information on the reader output. Adversaries who do not have access to this side channel are called narrow adversaries. Depending on restrictions on corruption, adversaries are called strong, destructive, forward, or weak adversaries. We derive some separation results: strong privacy is impossible. Narrow-strong privacy implies key agreement. We also prove some constructions: narrow-strong and forward privacy based on a public-key cryptosystem, narrow-destructive privacy based on a random oracle, and weak privacy based on a pseudorandom function. RFID protocols are used to identify cheap tags through wireless channels. However, putting tags in wearable items leads to privacy concerns. Although several privacy models exist so far, all have their own limitations, and finally, the classes of protocols that achieve privacy for one model or the other are not always comparable. A widely accepted flexible model permitting to establish a common measure of the performance of identification protocol is still under construction. We aim at contributing to this effort. To do so, we propose formal definitions of RFID schemes and adversaries and consider a twofold characterization of a scheme in terms of security and privacy. The former assesses the soundness of tag authentication. The latter property is for the ability to resist to adversaries aiming at identifying, tracing, or linking tags. In a nutshell, we formalize several types of privacy and study inherent limitations for RFID applications. We discuss which restrictions we can assume regarding tag corruption and availability of side channels. We show how to achieve those levels of privacy and what must be used in terms of conventional vs. publickey cryptography or stateless vs. rewritable tags. We show that the strongest possible level of privacy implies key agreement, thus mandating the use of some public-key cryptography techniques. We present a simple protocol for that. We assume a powerful adversary who can control all communications and interfere with the system. Cheap tags are not tamper-resistant so we analyze
Vaudenay REF firstly proposed a tag authentication protocol based on a generic public-key encryption (PKE) with a formal security proof.
On Privacy Models for RFID
ASIACRYPT
Computer Science