# Untangling RFID Privacy Models

Authors: Iwen Coisel; Tania Martin
Journal: Journal of Computer Networks and Communications
 (2013)

---

## Abstract

The rise of wireless applications based on RFID has brought up major concerns on privacy. Indeed nowadays, when such an application is deployed, informed customers yearn for guarantees that their privacy will not be threatened. One formal way to perform this task is to assess the privacy level of the RFID application with a model. However, if the chosen model does not reflect the assumptions and requirements of the analyzed application, it may misevaluate its privacy level. Therefore, selecting the most appropriate model among all the existing ones is not an easy task. This paper investigates the eight most well-known RFID privacy models and thoroughly examines their advantages and drawbacks in three steps. Firstly, five RFID authentication protocols are analyzed with these models. This discloses a main worry: although these protocols intuitively ensure different privacy levels, no model is able to accurately distinguish them. Secondly, these models are grouped according to their features (e.g., tag corruption ability). This classification reveals the most appropriate candidate model(s) to be used for a privacy analysis when one of these features is especially required. Furthermore, it points out that none of the models are comprehensive. Hence, some combinations of features may not match any model. Finally, the privacy properties of the eight models are compared in order to provide an overall view of their relations. This part highlights that no model globally outclasses the other ones. Considering the required properties of an application, the thorough study provided in this paper aims to assist system designers to choose the best suited model.


---

## Body

## 1. Introduction

Radio Frequency IDentification (RFID) is a technology that permits identifying and authenticating remote objects or persons without line of sight. In a simple manner, a tag (i.e., a transponder composed of a microcircuit and an antenna) is embedded into an object and interacts with a reader when it enters within its electromagnetic field. The first use of RFID goes back to the early 1940s, during World War II, when the Royal Air Force deployed the IFF (Identify Friend or Foe) system to identify the Allies airplanes. Today, RFID is more and more exploited in many domains such as library management, pet identification, antitheft cars, anticounterfeiting, ticketing in public transportation, access control, or even biometric passports. It thus covers a wide ranging of wireless technologies, from systems based on low-cost tags (such as EPCs [1]) to more evolved ones operating with contactless smartcards [2, 3].As predictable, some problems come up with this large-scale deployment. One general assumption of RFID systems is that the messages exchanged between the tags and the readers can easily be eavesdropped by an adversary. This raises the problem of information disclosure when the data emitted by a tag reveal details about its holder (called “information leakage”), but also when the eavesdropping of communications allows tracking a tag at different places or times (called “malicious traceability”) and consequently its holder. Many articles pointed out the dangers of RFID with respect to privacy, and the authorities are now aware of this problem. For instance, Ontario Information and Privacy Commissioner Cavoukian aims to advocate the concept of “privacy-by-design” [4] which states that privacy should be put in place in every IT system before its widespread use. In 2009, the European Commissioner for Justice, Fundamental Rights and Citizenship issued a recommendation [5] which strongly supports the implementation of privacy in RFID-based applications.Various researches have emerged these last years to fight against information leakage and malicious traceability in RFID. However, the search for a generic, efficient, and secure solution that can be implemented in reasonably costly tags remains open [6–8]. Solutions are usually designed empirically and analyzed with ad hoc methods that do not detect all their weaknesses. In parallel, many investigations have been conducted to formalize the privacy notion in RFID. In 2005, Avoine was the earliest researcher to present a privacy model [9]. Since then, many attempts [10–22] have been carried out to propose a convenient and appropriate privacy model for RFID. But each one suffers from distinct shortcomings. In particular, most of these models generally do not take into account all the alternatives that a power may offer to an adversary. For instance, when an adversary is allowed to corrupt a tag, then several possibilities may arise: a corrupted tag could be either destroyed or not, and, in the last case, this tag could still be requested to interact within the system. At Asiacrypt 2007, Vaudenay introduced the most evolved RFID privacy model [22] known so far. However, this model is not as convenient as some protocol designers may expect, and they sometimes prefer to use a less comprehensive model to analyze a system. Consequently, providing an analysis and a comparison of the major RFID privacy models is meaningful to help designers in their choice. Such a work aims to highlight the strengths and weaknesses of each model. Su et al. already achieved a similar work in [23]. Unfortunately, they only focused on privacy notions and did not consider all the subtleties that are brought by different models. As a consequence, their study considers some models as weak, even though they offer interesting properties.Our contribution is threefold. Firstly, in Sections3 to 10, we chronologically present eight well-known models designed to analyze identification/authentication protocols preserving privacy. Some of them are very popular like [9, 16, 22]. Other ones have interesting frameworks like [12, 13, 18] (e.g., [18] is derived from the well-known universal composability framework). Other alternative models are attractive successors of [22], such as [11, 15]. Secondly, in Section 11, we analyze five different authentication protocols with each of these models in order to exhibit the lack of granularity of the state of the art. Finally, in Sections 12 and 13, we thoroughly compare the eight models regarding their different features and their privacy notions. We show that none of these models can fairly analyze and compare protocols. This fact is especially undeniable when the system’s assumptions (that can differ from one system to another) are taken into account for an analysis.


## 2. Common Definitions

In this section, we give all the common definitions that are used in the presented privacy models.


### 2.1. The RFID System

For all the privacy models, an RFID system𝒮 is composed of three kinds of entities: tags, readers, and a centralized database. It is generally considered that the database and the readers are connected online all together through a secure channel, and therefore they form one unique entity, the reader.We denote𝒯 as a tag, ℛ as the reader, and DB as the reader’s database. A tag 𝒯 is able to communicate with ℛ when it enters into ℛ’s electromagnetic field. Then both reader and tag can participate together to an RFID protocol execution π. This protocol can be an identification or an authentication protocol. We define an i-pass RFID protocol as being a protocol where i messages are exchanged between ℛ and 𝒯.The readerℛ is a powerful transceiver device whose computation capabilities approach the ones of a small computer. A tag 𝒯 is a transponder with identifier ID𝒯. Its memory can vary from a hundred of bits (as for EPC tags [1]) to a few Kbytes (such as contactless smartcards [2, 3]). Its computation capabilities are generally much lower than a reader, but, depending on the tag, it can perform simple logic operations, symmetric-key cryptography, or even public-key cryptography. A tag is considered as legitimate when it is registered in the database DB as being an authorized entity of the system. The database DB stores, at least, the identifier ID𝒯 and potentially a secret k𝒯 of each legitimate tag 𝒯 involved in the system.


### 2.2. Basic Definitions

First, we defineλ as the security parameter of the system 𝒮 and poly(·) as a polynomial function. Thus, we define ϵ(λ):ℕ→ℝ as being a negligible function in λ if, for every positive function poly(·), there exists an integer N such that, for all λ>N, |ϵ(λ)|<1/poly(λ).Then, we define all the different entities that may play a role in the presented privacy models. Anadversary𝒜 is a malicious entity whose aim is to perform some attacks, either through the wireless communications between readers and tags (e.g., eavesdropping), or on the RFID devices themselves (e.g., corruption of a device and obtaining all the information stored on it). The adversary advantage is the success measure of an attack performed by 𝒜. In some models, 𝒜 is requested to answer to a kind of riddle, which is determined by an honest entity, called challenger𝒞. A challenge tag is a tag which is suffering from an attack performed by 𝒜. It can be chosen either by 𝒜 or by 𝒞.Generally, a modelization with oracles is used to represent the possible interactions between𝒜 and the system. Thus, 𝒜 carries out its attack on the system, performing some queries to the oracles that simulate the system. The generic oracles used in the presented privacy models are detailed in Section  2.4.We consider that𝒜 is able to play/interact with a tag when this last one is in 𝒜’s neighborhood. At that moment, the tag is called by its pseudonym 𝒯 (not by its identifier ID𝒯). During an attack, if a tag goes out and comes back to 𝒜’s neighborhood, then it is considered that its pseudonym has changed. This notion is detailed in the Vaudenay model [22] (see Section 5). The same case happens when a set of tags is given to the challenger 𝒞: when 𝒞 gives the tags back to 𝒜, their pseudonyms are changed.


### 2.3. Procedures

Most of the models studied in this paper focus on an RFID system𝒮 based on an anonymous identification protocol implying a single reader and several tags. The system is generally composed of several procedures, either defining how to set up the system, the reader, and the tags, or defining the studied protocol. One way to define these procedures is detailed in the following. Note that this is just a generalization but it may be different in some models. (i)
SetupReader(1λ) defines ℛ’s parameters (e.g., generating a private/public key pair (KS,KP)) depending on the security parameter λ. It also creates an empty database DB which will later contain, at least, the identifiers and secrets of all tags.(ii)
SetupTagKP(ID𝒯) returns k𝒯, that is, the secret k𝒯 of the tag 𝒯 with identifier ID𝒯.  (ID𝒯,k𝒯) is stored in the database DB of the reader.(iii)
Ident is a polynomial-time interactive protocol between the reader ℛ and a tag 𝒯, where ℛ ends with a private tape Output. At the end of the protocol, the reader either accepts the tag (if legitimate) and Output=ID𝒯, or rejects it (if not) and Output=⊥.


### 2.4. The Generic Oracles

An adversary𝒜 is able to interact/play with the system with the following oracles. First, it can setup a new tag of identifier ID𝒯.(i)
CreateTag(ID𝒯) creates a tag 𝒯 with a unique identifier ID𝒯. It uses SetupTagKP to set up the tag. It updates DB, adding this new tag.𝒜 can ask for a full execution of the protocol on a tag 𝒯. (i)
Execute(𝒯)→(π,transcript) executes an Ident protocol between ℛ and 𝒯. It outputs the transcript of the protocol execution π, that is the whole list of the successive messages of the execution π.Also, it can decompose a protocol execution, combining the following oracles.(i)
Launch()→π makes ℛ start a new Ident protocol execution π.(ii)
SendReader(m,π)→r sends a message m to ℛ in the protocol execution π. It outputs the response r of the reader.(iii)
SendTag(m,𝒯)→r sends a message m to 𝒯. It outputs the response r of the tag.Then,𝒜 can obtain for the reader’s result of a protocol execution π. (i)
Result(π)→x: when π is completed, it outputs x=1 if Output≠⊥, and x=0 otherwise.And finally, it can corrupt a tag𝒯 in order to recover its secret. (i)
Corrupt(𝒯)→k𝒯 returns the current secret k𝒯 of 𝒯.If the conditions of the oracles’ uses are not respected, then the oracles return⊥. Note that these definitions are generic ones. Some models do not use exactly the same generic oracles: in those cases, some refinements will be provided on their definitions.


## 2.1. The RFID System

For all the privacy models, an RFID system𝒮 is composed of three kinds of entities: tags, readers, and a centralized database. It is generally considered that the database and the readers are connected online all together through a secure channel, and therefore they form one unique entity, the reader.We denote𝒯 as a tag, ℛ as the reader, and DB as the reader’s database. A tag 𝒯 is able to communicate with ℛ when it enters into ℛ’s electromagnetic field. Then both reader and tag can participate together to an RFID protocol execution π. This protocol can be an identification or an authentication protocol. We define an i-pass RFID protocol as being a protocol where i messages are exchanged between ℛ and 𝒯.The readerℛ is a powerful transceiver device whose computation capabilities approach the ones of a small computer. A tag 𝒯 is a transponder with identifier ID𝒯. Its memory can vary from a hundred of bits (as for EPC tags [1]) to a few Kbytes (such as contactless smartcards [2, 3]). Its computation capabilities are generally much lower than a reader, but, depending on the tag, it can perform simple logic operations, symmetric-key cryptography, or even public-key cryptography. A tag is considered as legitimate when it is registered in the database DB as being an authorized entity of the system. The database DB stores, at least, the identifier ID𝒯 and potentially a secret k𝒯 of each legitimate tag 𝒯 involved in the system.


## 2.2. Basic Definitions

First, we defineλ as the security parameter of the system 𝒮 and poly(·) as a polynomial function. Thus, we define ϵ(λ):ℕ→ℝ as being a negligible function in λ if, for every positive function poly(·), there exists an integer N such that, for all λ>N, |ϵ(λ)|<1/poly(λ).Then, we define all the different entities that may play a role in the presented privacy models. Anadversary𝒜 is a malicious entity whose aim is to perform some attacks, either through the wireless communications between readers and tags (e.g., eavesdropping), or on the RFID devices themselves (e.g., corruption of a device and obtaining all the information stored on it). The adversary advantage is the success measure of an attack performed by 𝒜. In some models, 𝒜 is requested to answer to a kind of riddle, which is determined by an honest entity, called challenger𝒞. A challenge tag is a tag which is suffering from an attack performed by 𝒜. It can be chosen either by 𝒜 or by 𝒞.Generally, a modelization with oracles is used to represent the possible interactions between𝒜 and the system. Thus, 𝒜 carries out its attack on the system, performing some queries to the oracles that simulate the system. The generic oracles used in the presented privacy models are detailed in Section  2.4.We consider that𝒜 is able to play/interact with a tag when this last one is in 𝒜’s neighborhood. At that moment, the tag is called by its pseudonym 𝒯 (not by its identifier ID𝒯). During an attack, if a tag goes out and comes back to 𝒜’s neighborhood, then it is considered that its pseudonym has changed. This notion is detailed in the Vaudenay model [22] (see Section 5). The same case happens when a set of tags is given to the challenger 𝒞: when 𝒞 gives the tags back to 𝒜, their pseudonyms are changed.


## 2.3. Procedures

Most of the models studied in this paper focus on an RFID system𝒮 based on an anonymous identification protocol implying a single reader and several tags. The system is generally composed of several procedures, either defining how to set up the system, the reader, and the tags, or defining the studied protocol. One way to define these procedures is detailed in the following. Note that this is just a generalization but it may be different in some models. (i)
SetupReader(1λ) defines ℛ’s parameters (e.g., generating a private/public key pair (KS,KP)) depending on the security parameter λ. It also creates an empty database DB which will later contain, at least, the identifiers and secrets of all tags.(ii)
SetupTagKP(ID𝒯) returns k𝒯, that is, the secret k𝒯 of the tag 𝒯 with identifier ID𝒯.  (ID𝒯,k𝒯) is stored in the database DB of the reader.(iii)
Ident is a polynomial-time interactive protocol between the reader ℛ and a tag 𝒯, where ℛ ends with a private tape Output. At the end of the protocol, the reader either accepts the tag (if legitimate) and Output=ID𝒯, or rejects it (if not) and Output=⊥.


## 2.4. The Generic Oracles

An adversary𝒜 is able to interact/play with the system with the following oracles. First, it can setup a new tag of identifier ID𝒯.(i)
CreateTag(ID𝒯) creates a tag 𝒯 with a unique identifier ID𝒯. It uses SetupTagKP to set up the tag. It updates DB, adding this new tag.𝒜 can ask for a full execution of the protocol on a tag 𝒯. (i)
Execute(𝒯)→(π,transcript) executes an Ident protocol between ℛ and 𝒯. It outputs the transcript of the protocol execution π, that is the whole list of the successive messages of the execution π.Also, it can decompose a protocol execution, combining the following oracles.(i)
Launch()→π makes ℛ start a new Ident protocol execution π.(ii)
SendReader(m,π)→r sends a message m to ℛ in the protocol execution π. It outputs the response r of the reader.(iii)
SendTag(m,𝒯)→r sends a message m to 𝒯. It outputs the response r of the tag.Then,𝒜 can obtain for the reader’s result of a protocol execution π. (i)
Result(π)→x: when π is completed, it outputs x=1 if Output≠⊥, and x=0 otherwise.And finally, it can corrupt a tag𝒯 in order to recover its secret. (i)
Corrupt(𝒯)→k𝒯 returns the current secret k𝒯 of 𝒯.If the conditions of the oracles’ uses are not respected, then the oracles return⊥. Note that these definitions are generic ones. Some models do not use exactly the same generic oracles: in those cases, some refinements will be provided on their definitions.


## 3. Avoine [9], 2005

In 2005, Avoine proposed the first privacy model for RFID systems. The goal was to analyze the untraceability notion of 3-pass protocols following the idea of communication intervals: the adversary𝒜 asks some oracles’ queries on specific intervals of the targeted tags lives. The privacy notion behind this model represents the unfeasibility to distinguish one tag among two.


### 3.1. The Oracles

This model considers that each tag has a unique and independent secret, and that, at the initialization of the system,DB already stores all the tags’ secrets, that is, a SetupTag has already been performed on every tag.Then𝒜 has only access to the following modified generic oracles adapted for 3-pass protocols. Instead of using the entities’ names, Avoine uses the protocol executions names. Since 𝒯 and ℛ can run several protocol executions, π𝒯i (resp., πℛj) denotes the ith (resp., jth) execution of 𝒯 (resp., ℛ). These notations favor the precise description of ℛ’s and 𝒯’s lifetimes.(i)
SendTag(m1,m3,π𝒯i)→r sends a request m1 to 𝒯, and then 𝒜 sends the message m3 after receiving 𝒯’s answer r. This is done during the execution π𝒯i of 𝒯.(ii)
SendReader(m2,πℛj)→r sends the message m2 to ℛ in the protocol execution πℛj. It outputs ℛ’s answer r.(iii)
Execute(π𝒯i,πℛj)→transcript executes a whole execution of the protocol between 𝒯 and ℛ. This is done during the execution π𝒯i of 𝒯 and the execution πℛj of ℛ. 𝒜 obtains the whole transcript.(iv)
Execute*(π𝒯i,πℛj)→ℛ-transcript this is the same as the normal Execute. But it only returns the ℛ-transcript, that is, the messages sent by ℛ.(v)
Corrupt(π𝒯i)→k𝒯: returns the current secret k𝒯 of 𝒯 when the tag is in its ith execution.The goal of the Execute* oracle is to simulate the fact that the forward channel (from reader to tag) has a longer communication range than the backward channel (from tag to reader) and therefore can be easily eavesdropped. It formalizes the asymmetry regarding the channels.Two remarks are of interest for the Corrupt oracle. First, Corrupt can be used only once by𝒜. After this oracle query, 𝒜 cannot use the other oracles anymore. Second, Corrupt is called on the tag execution number, and not the tag itself. This allows 𝒜 to specify exactly the targeted moment of the tag’s life.During its attack,𝒜 has access to the oracles 𝒪⊂{T,R,E,E*,C} = {SendTag, SendReader, Execute, Execute*, Corrupt}.Avoine denotesωi(𝒯) as being the result of an oracle query on 𝒯: therefore ωi(𝒯)∈{SendTag(*,*,π𝒯i), Execute(π𝒯i,*), Execute*(π𝒯i,*), Corrupt(π𝒯i)}. Avoine defines an interactionΩI(𝒯) as being a set of executions on the same tag 𝒯 during an interval I when 𝒜 can play with 𝒯. Formally, ΩI(𝒯)={ωi(𝒯)∣i∈I}∪{SendReader(*,π*j)∣j∈J}, where I,J⊂ℕ. By this definition, the length of ΩI(𝒯) is |I|.Avoine also defines a functionOracle which takes as parameters a tag 𝒯, an interval I, and the oracles 𝒪, and which outputs the interaction Ω^I(𝒯) that maximizes 𝒜’s advantage.


### 3.2. Untraceability Experiments

Avoine defines two experiments to represent two untraceability notions. They depend onλref and λchal, which represent, respectively, a reference length and a challenge length and which are function of the security parameter λ.The first experiment given in Box1 works as follows. First, 𝒜 receives the interactions of a tag 𝒯 during an interval I that it chooses. Then, it receives the interactions of the challenge tags 𝒯0 and 𝒯1, also during the intervals I0 and I1 that it chooses, such that 𝒯=𝒯0 or 𝒯1. This last information is unknown to 𝒜. Additionally here, none of these two intervals I0 and I1 cross the interval I of 𝒯. At the end, 𝒜 has to decide which one of the challenge tags is the tag 𝒯.Box 1
ExperimentExp𝒮,𝒜Existential-UNT[λref,λchal,𝒪].
(1)𝒞 initializes the system 𝒮.
(2)𝒜 requests 𝒞 to receive a tag 𝒯.
(3)𝒜 chooses I, queries Oracle(𝒯,I,𝒪) where |I|≤λref, and then receives Ω^I(𝒯).
(4)𝒜 requests 𝒞 to receive two challenge tags 𝒯0 and 𝒯1, such that 𝒯=𝒯0 or 𝒯1.
(5)𝒜 chooses I0 and I1 such that |I0|≤λchal, |I1|≤λchal, and (I0∪I1)∩I=∅.
(6)𝒜 queries Oracle(𝒯0,I0,𝒪) and Oracle(𝒯1,I1,𝒪), and then receives Ω^I0(𝒯0) and Ω^I1(𝒯1).
(7)𝒜 decides which of 𝒯0 or 𝒯1 is 𝒯, and outputs a guess bit b.
Exp
𝒮
,
𝒜
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T succeeds if 𝒯=𝒯b.The second experiment given in Box2 has the same mechanism. The only difference is that, now, 𝒞 is the one that chooses the intervals I0 and I1 of the challenge tags, and not 𝒜 anymore.Box 2
ExperimentExp𝒮,𝒜Universal-UNT[λref,λchal,𝒪]
(1)𝒞 initializes the system 𝒮.
(2)𝒜 requests 𝒞 to receive a tag 𝒯.
(3)𝒜 chooses I, queries Oracle(𝒯,I,𝒪) where |I|≤λref, and then receives Ω^I(𝒯). Here I is known by 𝒞.
(4)𝒜requests 𝒞 to receive two challenges 𝒯0, 𝒯1, I0 and I1, such that 𝒯=𝒯0 or 𝒯1.
(5)𝒜 queries Oracle(𝒯0,I0,𝒪) and Oracle(𝒯1,I1,𝒪), and then receives Ω^I0(𝒯0) and Ω^I1(𝒯1).
(6)𝒜 decides which of 𝒯0 or 𝒯1 is 𝒯, and outputs a guess bit b.
Exp
𝒮
,
𝒜
U
n
i
v
e
r
s
a
l
-
U
N
T succeeds if 𝒯=𝒯b.


### 3.3. Untraceability Notions

From the experiments defined above, the notions ofExistential-UNT and Universal-UNT are extended in this model, depending on restrictions about the choices of I0 and I1. Existential-UNT is when 𝒜 chooses I0 and I1, whereas Universal-UNT is when 𝒞 chooses them. Then, if I<I0,I1 (resp., I>I0,I1), that means I0 and I1 take place after (resp., before) I, with respect to the lifetime of the system. (i)
If𝒜 (resp., 𝒞) chooses I0 and I1 such that I<I0,I1, then it is denoted Existential+ (resp., Universal+).(ii)
If𝒜 (resp., 𝒞) chooses I0 and I1 such that I>I0,I1, then it is denoted Existential- (resp., Universal-).The notion ofUniversal- when the Corrupt oracle is used is called Forward-UNT.Definition 1 (untraceability [9]).
An RFID system𝒮 is said to be P-UNT-𝒪 (for P∈{Existential, Forward, Universal}) if, for every adversary 𝒜,
(1)|Pr(Exp𝒮,𝒜P-UNT[λref,λchal,𝒪]succeeds)-12|≤ϵ(λref,λchal).Direct implications are made from these notions:(2)Existential-UNT-𝒪⇒Forward-UNT-𝒪⇒Universal-UNT-𝒪


## 3.1. The Oracles

This model considers that each tag has a unique and independent secret, and that, at the initialization of the system,DB already stores all the tags’ secrets, that is, a SetupTag has already been performed on every tag.Then𝒜 has only access to the following modified generic oracles adapted for 3-pass protocols. Instead of using the entities’ names, Avoine uses the protocol executions names. Since 𝒯 and ℛ can run several protocol executions, π𝒯i (resp., πℛj) denotes the ith (resp., jth) execution of 𝒯 (resp., ℛ). These notations favor the precise description of ℛ’s and 𝒯’s lifetimes.(i)
SendTag(m1,m3,π𝒯i)→r sends a request m1 to 𝒯, and then 𝒜 sends the message m3 after receiving 𝒯’s answer r. This is done during the execution π𝒯i of 𝒯.(ii)
SendReader(m2,πℛj)→r sends the message m2 to ℛ in the protocol execution πℛj. It outputs ℛ’s answer r.(iii)
Execute(π𝒯i,πℛj)→transcript executes a whole execution of the protocol between 𝒯 and ℛ. This is done during the execution π𝒯i of 𝒯 and the execution πℛj of ℛ. 𝒜 obtains the whole transcript.(iv)
Execute*(π𝒯i,πℛj)→ℛ-transcript this is the same as the normal Execute. But it only returns the ℛ-transcript, that is, the messages sent by ℛ.(v)
Corrupt(π𝒯i)→k𝒯: returns the current secret k𝒯 of 𝒯 when the tag is in its ith execution.The goal of the Execute* oracle is to simulate the fact that the forward channel (from reader to tag) has a longer communication range than the backward channel (from tag to reader) and therefore can be easily eavesdropped. It formalizes the asymmetry regarding the channels.Two remarks are of interest for the Corrupt oracle. First, Corrupt can be used only once by𝒜. After this oracle query, 𝒜 cannot use the other oracles anymore. Second, Corrupt is called on the tag execution number, and not the tag itself. This allows 𝒜 to specify exactly the targeted moment of the tag’s life.During its attack,𝒜 has access to the oracles 𝒪⊂{T,R,E,E*,C} = {SendTag, SendReader, Execute, Execute*, Corrupt}.Avoine denotesωi(𝒯) as being the result of an oracle query on 𝒯: therefore ωi(𝒯)∈{SendTag(*,*,π𝒯i), Execute(π𝒯i,*), Execute*(π𝒯i,*), Corrupt(π𝒯i)}. Avoine defines an interactionΩI(𝒯) as being a set of executions on the same tag 𝒯 during an interval I when 𝒜 can play with 𝒯. Formally, ΩI(𝒯)={ωi(𝒯)∣i∈I}∪{SendReader(*,π*j)∣j∈J}, where I,J⊂ℕ. By this definition, the length of ΩI(𝒯) is |I|.Avoine also defines a functionOracle which takes as parameters a tag 𝒯, an interval I, and the oracles 𝒪, and which outputs the interaction Ω^I(𝒯) that maximizes 𝒜’s advantage.


## 3.2. Untraceability Experiments

Avoine defines two experiments to represent two untraceability notions. They depend onλref and λchal, which represent, respectively, a reference length and a challenge length and which are function of the security parameter λ.The first experiment given in Box1 works as follows. First, 𝒜 receives the interactions of a tag 𝒯 during an interval I that it chooses. Then, it receives the interactions of the challenge tags 𝒯0 and 𝒯1, also during the intervals I0 and I1 that it chooses, such that 𝒯=𝒯0 or 𝒯1. This last information is unknown to 𝒜. Additionally here, none of these two intervals I0 and I1 cross the interval I of 𝒯. At the end, 𝒜 has to decide which one of the challenge tags is the tag 𝒯.Box 1
ExperimentExp𝒮,𝒜Existential-UNT[λref,λchal,𝒪].
(1)𝒞 initializes the system 𝒮.
(2)𝒜 requests 𝒞 to receive a tag 𝒯.
(3)𝒜 chooses I, queries Oracle(𝒯,I,𝒪) where |I|≤λref, and then receives Ω^I(𝒯).
(4)𝒜 requests 𝒞 to receive two challenge tags 𝒯0 and 𝒯1, such that 𝒯=𝒯0 or 𝒯1.
(5)𝒜 chooses I0 and I1 such that |I0|≤λchal, |I1|≤λchal, and (I0∪I1)∩I=∅.
(6)𝒜 queries Oracle(𝒯0,I0,𝒪) and Oracle(𝒯1,I1,𝒪), and then receives Ω^I0(𝒯0) and Ω^I1(𝒯1).
(7)𝒜 decides which of 𝒯0 or 𝒯1 is 𝒯, and outputs a guess bit b.
Exp
𝒮
,
𝒜
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T succeeds if 𝒯=𝒯b.The second experiment given in Box2 has the same mechanism. The only difference is that, now, 𝒞 is the one that chooses the intervals I0 and I1 of the challenge tags, and not 𝒜 anymore.Box 2
ExperimentExp𝒮,𝒜Universal-UNT[λref,λchal,𝒪]
(1)𝒞 initializes the system 𝒮.
(2)𝒜 requests 𝒞 to receive a tag 𝒯.
(3)𝒜 chooses I, queries Oracle(𝒯,I,𝒪) where |I|≤λref, and then receives Ω^I(𝒯). Here I is known by 𝒞.
(4)𝒜requests 𝒞 to receive two challenges 𝒯0, 𝒯1, I0 and I1, such that 𝒯=𝒯0 or 𝒯1.
(5)𝒜 queries Oracle(𝒯0,I0,𝒪) and Oracle(𝒯1,I1,𝒪), and then receives Ω^I0(𝒯0) and Ω^I1(𝒯1).
(6)𝒜 decides which of 𝒯0 or 𝒯1 is 𝒯, and outputs a guess bit b.
Exp
𝒮
,
𝒜
U
n
i
v
e
r
s
a
l
-
U
N
T succeeds if 𝒯=𝒯b.


## 3.3. Untraceability Notions

From the experiments defined above, the notions ofExistential-UNT and Universal-UNT are extended in this model, depending on restrictions about the choices of I0 and I1. Existential-UNT is when 𝒜 chooses I0 and I1, whereas Universal-UNT is when 𝒞 chooses them. Then, if I<I0,I1 (resp., I>I0,I1), that means I0 and I1 take place after (resp., before) I, with respect to the lifetime of the system. (i)
If𝒜 (resp., 𝒞) chooses I0 and I1 such that I<I0,I1, then it is denoted Existential+ (resp., Universal+).(ii)
If𝒜 (resp., 𝒞) chooses I0 and I1 such that I>I0,I1, then it is denoted Existential- (resp., Universal-).The notion ofUniversal- when the Corrupt oracle is used is called Forward-UNT.Definition 1 (untraceability [9]).
An RFID system𝒮 is said to be P-UNT-𝒪 (for P∈{Existential, Forward, Universal}) if, for every adversary 𝒜,
(1)|Pr(Exp𝒮,𝒜P-UNT[λref,λchal,𝒪]succeeds)-12|≤ϵ(λref,λchal).Direct implications are made from these notions:(2)Existential-UNT-𝒪⇒Forward-UNT-𝒪⇒Universal-UNT-𝒪


## 4. Juels and Weis [16], 2007

Two years after Avoine’s publication, Juels and Weis proposed a new privacy model, referred in the sequel as JW, based on indistinguishability of tags. It intended to analyze classical challenge/response protocols based on symmetric-key cryptography (with possible additional messages in order to update the tags keys).In their article, the authors highlighted that the Avoine model lacks two important features. Firstly, they proved that it is unable to catch an important attack on systems where tags have correlated secrets, because Avoine’s adversary can only play with two tags. Secondly, they showed that Avoine did not have hindsight regarding all the possible attacks that can be performed on a protocol. The Avoine model does not capture all the relevant information that can be extracted from a protocol execution. For instance, it does not consider that𝒜 has access to any execution result. However, this simple “side information bit” allows formalizing a special kind of attacks on desynchronizable protocols like OSK, as explained in Appendix  B.3. and in [24]. Therefore, the JW model aimed to fill that gap.


### 4.1. Oracles

At the initialization of the system,DB already stores all the tags’ content, that is, a SetupTag has already been performed on every tag. Then 𝒜 has access to the generic oracles Launch SendTag and SendReader, with the difference that the Output of SendReader includes the output of Result. It has furthermore access to the following oracles. (i)
TagInit(𝒯)→π: when 𝒯 receives this query, it begins a new protocol execution π and deletes the information related to any existing execution.(ii)
SetKey(𝒯,k𝒯new)→k𝒯: when 𝒯 receives this query, it outputs its current key k𝒯 and replaces it by a new one, k𝒯new.The SetKey oracle is equivalent to the Corrupt oracle given in Section  2.4 in the sense that it reveals to𝒜 the tag’s current key. Note that its use and its result have an interesting feature: 𝒜 is able to put any new key in the targeted tag: either the revealed one or a random one (that can be illegitimate).


### 4.2. Privacy Experiment

Letρ, σ, and τ be, respectively, the numbers of Launch, computation steps (represented by the SendReader and SendTag queries), and TagInit that are allowed to 𝒜. Let n be the total number of tags involved in the system 𝒮. The privacy experiment is given in Box 3.Box 3
ExperimentExp𝒮,𝒜JW-priv[λ,n,ρ,σ,τ]
Setup:
(1)𝒞 initializes the system 𝒮.
Phase 1 (Learning):
(2)𝒜 may do the following in any interleaved order:
(a) Make Launch and TagInit queries, without exceeding ρ and τ overall queries respectively.
(b) Make arbitrary SetKey queries to any (n-2) tags.
(c) Make SendReader and SendTag queries, without exceeding σ overall queries.
Phase 2 (Challenge):
(3)𝒜 selects two challenge tags 𝒯i and 𝒯j to which it did not send SetKey queries.
(4) Let𝒯0*=𝒯i and 𝒯1*=𝒯j, and remove both from the current tag set.
(5)𝒞 chooses a bit b at random, and provides 𝒜 access to 𝒯b*.
(6)𝒜 may do the following in any interleaved order:
(a) Make Launch and TagInit queries, without exceeding ρ and τ overall queries respectively.
(b) Make arbitrary SetKey queries to any tag in the current tag set, except𝒯b*.
(c) Make SendReader and SendTag queries, without exceeding σ overall queries.
(7)𝒜 outputs a guess bit b'.
Exp
𝒮
,
𝒜
J
W
-
p
r
i
v succeeds if b=b'.


### 4.3. Privacy Notions

From the previous experiment, the JW model defines the following privacy property, whereρ, σ, and τ can be function of the system security parameter λ.Definition 2 ((ρ,σ,τ)-privacy [16]).
A protocol initiated byℛ in an RFID system 𝒮 with security parameter λ is (ρ,σ,τ)-private if, for every adversary 𝒜,
(3)|Pr(Exp𝒮,𝒜JW-priv[λ,n,ρ,σ,τ]succeeds)-12|≤ϵ(λ).Considering a variant of experimentExp𝒮,𝒜JW-priv where the “except𝒯b*” is removed from step (6.b), then forward-(ρ,σ,τ)-privacy can be defined in the same way as the previous definition.Note that, if𝒜 uses SetKey to put an illegitimate key in a tag, then this last one will possibly no longer be authenticated successfully by the reader. Nevertheless, whether this is performed on the nonchallenge tags or on 𝒯b* (only for the forward-(ρ,σ,τ)-privacy experiment), this does not help 𝒜 to find more easily the bit b and thus does not influence its success to win the experiment.


## 4.1. Oracles

At the initialization of the system,DB already stores all the tags’ content, that is, a SetupTag has already been performed on every tag. Then 𝒜 has access to the generic oracles Launch SendTag and SendReader, with the difference that the Output of SendReader includes the output of Result. It has furthermore access to the following oracles. (i)
TagInit(𝒯)→π: when 𝒯 receives this query, it begins a new protocol execution π and deletes the information related to any existing execution.(ii)
SetKey(𝒯,k𝒯new)→k𝒯: when 𝒯 receives this query, it outputs its current key k𝒯 and replaces it by a new one, k𝒯new.The SetKey oracle is equivalent to the Corrupt oracle given in Section  2.4 in the sense that it reveals to𝒜 the tag’s current key. Note that its use and its result have an interesting feature: 𝒜 is able to put any new key in the targeted tag: either the revealed one or a random one (that can be illegitimate).


## 4.2. Privacy Experiment

Letρ, σ, and τ be, respectively, the numbers of Launch, computation steps (represented by the SendReader and SendTag queries), and TagInit that are allowed to 𝒜. Let n be the total number of tags involved in the system 𝒮. The privacy experiment is given in Box 3.Box 3
ExperimentExp𝒮,𝒜JW-priv[λ,n,ρ,σ,τ]
Setup:
(1)𝒞 initializes the system 𝒮.
Phase 1 (Learning):
(2)𝒜 may do the following in any interleaved order:
(a) Make Launch and TagInit queries, without exceeding ρ and τ overall queries respectively.
(b) Make arbitrary SetKey queries to any (n-2) tags.
(c) Make SendReader and SendTag queries, without exceeding σ overall queries.
Phase 2 (Challenge):
(3)𝒜 selects two challenge tags 𝒯i and 𝒯j to which it did not send SetKey queries.
(4) Let𝒯0*=𝒯i and 𝒯1*=𝒯j, and remove both from the current tag set.
(5)𝒞 chooses a bit b at random, and provides 𝒜 access to 𝒯b*.
(6)𝒜 may do the following in any interleaved order:
(a) Make Launch and TagInit queries, without exceeding ρ and τ overall queries respectively.
(b) Make arbitrary SetKey queries to any tag in the current tag set, except𝒯b*.
(c) Make SendReader and SendTag queries, without exceeding σ overall queries.
(7)𝒜 outputs a guess bit b'.
Exp
𝒮
,
𝒜
J
W
-
p
r
i
v succeeds if b=b'.


## 4.3. Privacy Notions

From the previous experiment, the JW model defines the following privacy property, whereρ, σ, and τ can be function of the system security parameter λ.Definition 2 ((ρ,σ,τ)-privacy [16]).
A protocol initiated byℛ in an RFID system 𝒮 with security parameter λ is (ρ,σ,τ)-private if, for every adversary 𝒜,
(3)|Pr(Exp𝒮,𝒜JW-priv[λ,n,ρ,σ,τ]succeeds)-12|≤ϵ(λ).Considering a variant of experimentExp𝒮,𝒜JW-priv where the “except𝒯b*” is removed from step (6.b), then forward-(ρ,σ,τ)-privacy can be defined in the same way as the previous definition.Note that, if𝒜 uses SetKey to put an illegitimate key in a tag, then this last one will possibly no longer be authenticated successfully by the reader. Nevertheless, whether this is performed on the nonchallenge tags or on 𝒯b* (only for the forward-(ρ,σ,τ)-privacy experiment), this does not help 𝒜 to find more easily the bit b and thus does not influence its success to win the experiment.


## 5. Vaudenay [22], 2007

Later the same year, Vaudenay proposed formal definitions for RFID systems and adversaries and considered that a system𝒮 can be characterized by two notions: security and privacy. In this paper, we only present the privacy notion. Vaudenay’s article followed some joint work done with Bocchetti [25], and its goal was to propose a comprehensive model that can formalize a wide range of adversaries. This characteristic is missing in the previous models and turns to be an asset of the Vaudenay model.This model defines tags with respect to the adversary possibility to interact with them, as explained in Section  2.2. Clearly, when a tag is within𝒜’s neighborhood, it is said to be drawn and has a pseudonym so that 𝒜 is able to communicate with the tag. In the opposite situation, a tag is said to be free (i.e., not drawn), and 𝒜 cannot communicate with it. Consequently, the model considers that, at any given time, a tag can be either free or drawn. For example, the same tag with identifier ID𝒯 which is drawn, freed, and drawn again has two pseudonyms: 𝒜 sees two different tags. Additionally, all the tags may not be accessible to 𝒜 during all the attack: for instance, 𝒜 may only play with two (drawn) tags during its attack.


### 5.1. Oracles

Contrary to the other previous models,DB is empty at the initialization of the system. Then 𝒜 has access to all the generic oracles defined in Section  2.4. The only modification done on these ones is that 𝒜 can create a fake tag with CreateTag. In that case, no information related to this tag is stored in DB. It can also query the following ones.(i)
DrawTag(distr)→(𝒯1,b1,…,𝒯k,bk): following the distribution probability distr (which is specified by a polynomially bounded sampling algorithm), it randomly selects k tags between all the existing (not already drawn) ones. For each chosen tag, the oracle assigns to it a new pseudonym, denoted 𝒯i, and changes its status from free to drawn. Finally, the oracle outputs all the generated temporary tags (𝒯1,…,𝒯k) in any random order. If there is not enough free tags (i.e., less than k), or tags already drawn, then the oracle outputs ⊥. It is further assumed that this oracle returns bits (b1,…,bk) telling if each of the drawn tags is legitimate or not. All relations (𝒯i,ID𝒯i) are kept in an a priori secret table denoted Tab.(ii)
Free(𝒯) moves the tag 𝒯 from the status drawn to the status free. 𝒯 is unavailable from now on.


### 5.2. Privacy Experiment

From the oracles given above, Vaudenay defines five classes of polynomial-time adversary, characterized by𝒜’s ability to use the oracles.Definition 3 (adversary class [22]).
An adversary class is said to be(i)
STRONG if 𝒜 has access to all the oracles;(ii)
DESTRUCTIVE if 𝒜 cannot use anymore a “corrupted” tag (i.e., the tag has been destroyed);(iii)
FORWARD if 𝒜 can only use the Corrupt oracle after its first query to the Corrupt oracle;(iv)
WEAK if 𝒜 has no access to the Corrupt oracle;(v)
NARROW if 𝒜 has no access to the Result oracle.Remark 4.
The following relation is clear:WEAK⊆FORWARD⊆DESTRUCTIVE⊆STRONG.Note that theWIDE notion is the contrary to the NARROW one. If an adversary 𝒜 is not said to be NARROW, then nothing is said, but the term WIDE is implicitly meant.Vaudenay’s privacy experiment is given in Box4. P is the adversary class, P∈{∅,NARROW}×{WEAK,FORWARD,DESTRUCTIVE,STRONG}.Box 4
ExperimentExp𝒮,𝒜Vaud-priv[λ]
(1)𝒞 initializes the system and sends 1λ, and KP to 𝒜.
(2)𝒜 interacts with the whole system, limited by its class P.
(3)𝒜 analyzes the system without oracle queries.
(4)𝒜 receives the hidden table Tab of the DrawTag oracle.
(5)𝒜 returns true or false.
Exp
𝒮
,
𝒜
V
a
u
d
-
p
r
i
v succeeds if 𝒜 returns true.


### 5.3. Privacy Notions

To define the privacy property of Vaudenay, it is first needed to define the notions ofblinder (i.e., an algorithm able to simulate the answers of some specific oracles) and trivial adversary (i.e., an adversary that learns nothing about the system).Definition 5 (blinder, trivial adversary [22]).
A blinderℬ for an adversary 𝒜 is a polynomial-time algorithm which sees the same messages as 𝒜 and simulates the Launch, SendReader, SendTag, and Result oracles to 𝒜. ℬ does not have access to the reader tapes, so it does not know the secret key nor the database.
A blinded adversary𝒜ℬ is itself an adversary that does not use the Launch, SendReader, SendTag, and Result oracles.
An adversary𝒜 is trivial if there exists a blinder ℬ such that
(4)|Pr(Exp𝒮,𝒜Vaud-priv[λ]succeeds)-Pr(Exp𝒮,𝒜ℬVaud-priv[λ]succeeds)|≤ϵ(λ).Definition 6 (privacy [22]).
The RFID system𝒮 is said to be P-private if all the adversaries which belong to class P are trivial following Definition 5.The implications between Vaudenay’s privacy notions are as follows:(5)STRONG⇒DESTRUCTIVE⇒FORWARD⇒WEAK⇓⇓⇓⇓NARROW-STRONG⇒NARROW-DESTRUCTIVE⇒NARROW-FORWARD⇒NARROW-WEAKThe main result of Vaudenay is thatSTRONG-privacy is impossible, by proving that a DESTRUCTIVE-private protocol is not NARROW-STRONG-private. However, Vaudenay does not define which privacy level should be targeted by a protocol: it is never specified if NARROW-STRONG-privacy is better or not than DESTRUCTIVE-privacy.Also, it is not explicit how the blinded adversary𝒜ℬ operates. Basically, there are two options: (i) 𝒜ℬ aims the same probability than 𝒜, or (ii) 𝒜ℬ aims the same behavior than 𝒜. It is obvious that the first option allows proving the privacy of some protocols which are actually not private, but this should be correctly formalized.


### 5.4. Extensions of the Model

#### 5.4.1.  Model [21], 2008

Paise and Vaudenay extended the Vaudenay model to analyze mutual authentication protocols. Actually, they enriched the definition of the RFID system𝒮 by introducing an output on the tag side: either the tag accepts the reader (if legitimate) and outputs OK, or rejects it (if not) and outputs ⊥. This formalizes the concept of reader authentication. Nevertheless, their extension does not modify the core of the Vaudenay model.They also showed an important impossibility result: if the corruption of a tag reveals its entire state (and not only its secretk𝒯), then no RFID scheme providing reader authentication is NARROW-FORWARD-private. To counter this issue, they claimed that the temporary memory of a tag should be automatically erased as soon as the tag is put back as free. However, this idea is not formalized in the paper.This division between the persistent and the temporary memory of a tag has also been investigated by Armknecht et al. [26]. Based on the work of Paise and Vaudenay, they showed several impossibility results in attack scenarios with special uses of tag corruption.


#### 5.4.2. Model [20], 2011

Ouafi presented in his thesis an adaptation of the Vaudenay model in order to counter Vaudenay’s impossibility result ofSTRONG-privacy. Concretely, the author proposed to incorporate the blinder with the adversary, so that the blinder has the knowledge of all the random choices and incoming messages made by the adversary. With this new definition of the blinder, Ouafi proved that STRONG-privacy can be ensured. This result is demonstrated with a public-key-based authentication protocol where the encryption scheme is IND-CCA2 secure and PA1+ plaintext-aware. (More details about these security notions can be found in [27].)


#### 5.4.3. Other Extensions

The Vaudenay model has also been broadened in different works. In a nutshell, this is generally performed via the addition of a new oracle to the adversary capabilities (e.g., Timer in [28], MakeInactive in [29], or DestroyReader in [30]) and the corresponding new adversary class (e.g., the TIMEFUL class when 𝒜 is allowed to use Timer).


## 5.1. Oracles

Contrary to the other previous models,DB is empty at the initialization of the system. Then 𝒜 has access to all the generic oracles defined in Section  2.4. The only modification done on these ones is that 𝒜 can create a fake tag with CreateTag. In that case, no information related to this tag is stored in DB. It can also query the following ones.(i)
DrawTag(distr)→(𝒯1,b1,…,𝒯k,bk): following the distribution probability distr (which is specified by a polynomially bounded sampling algorithm), it randomly selects k tags between all the existing (not already drawn) ones. For each chosen tag, the oracle assigns to it a new pseudonym, denoted 𝒯i, and changes its status from free to drawn. Finally, the oracle outputs all the generated temporary tags (𝒯1,…,𝒯k) in any random order. If there is not enough free tags (i.e., less than k), or tags already drawn, then the oracle outputs ⊥. It is further assumed that this oracle returns bits (b1,…,bk) telling if each of the drawn tags is legitimate or not. All relations (𝒯i,ID𝒯i) are kept in an a priori secret table denoted Tab.(ii)
Free(𝒯) moves the tag 𝒯 from the status drawn to the status free. 𝒯 is unavailable from now on.


## 5.2. Privacy Experiment

From the oracles given above, Vaudenay defines five classes of polynomial-time adversary, characterized by𝒜’s ability to use the oracles.Definition 3 (adversary class [22]).
An adversary class is said to be(i)
STRONG if 𝒜 has access to all the oracles;(ii)
DESTRUCTIVE if 𝒜 cannot use anymore a “corrupted” tag (i.e., the tag has been destroyed);(iii)
FORWARD if 𝒜 can only use the Corrupt oracle after its first query to the Corrupt oracle;(iv)
WEAK if 𝒜 has no access to the Corrupt oracle;(v)
NARROW if 𝒜 has no access to the Result oracle.Remark 4.
The following relation is clear:WEAK⊆FORWARD⊆DESTRUCTIVE⊆STRONG.Note that theWIDE notion is the contrary to the NARROW one. If an adversary 𝒜 is not said to be NARROW, then nothing is said, but the term WIDE is implicitly meant.Vaudenay’s privacy experiment is given in Box4. P is the adversary class, P∈{∅,NARROW}×{WEAK,FORWARD,DESTRUCTIVE,STRONG}.Box 4
ExperimentExp𝒮,𝒜Vaud-priv[λ]
(1)𝒞 initializes the system and sends 1λ, and KP to 𝒜.
(2)𝒜 interacts with the whole system, limited by its class P.
(3)𝒜 analyzes the system without oracle queries.
(4)𝒜 receives the hidden table Tab of the DrawTag oracle.
(5)𝒜 returns true or false.
Exp
𝒮
,
𝒜
V
a
u
d
-
p
r
i
v succeeds if 𝒜 returns true.


## 5.3. Privacy Notions

To define the privacy property of Vaudenay, it is first needed to define the notions ofblinder (i.e., an algorithm able to simulate the answers of some specific oracles) and trivial adversary (i.e., an adversary that learns nothing about the system).Definition 5 (blinder, trivial adversary [22]).
A blinderℬ for an adversary 𝒜 is a polynomial-time algorithm which sees the same messages as 𝒜 and simulates the Launch, SendReader, SendTag, and Result oracles to 𝒜. ℬ does not have access to the reader tapes, so it does not know the secret key nor the database.
A blinded adversary𝒜ℬ is itself an adversary that does not use the Launch, SendReader, SendTag, and Result oracles.
An adversary𝒜 is trivial if there exists a blinder ℬ such that
(4)|Pr(Exp𝒮,𝒜Vaud-priv[λ]succeeds)-Pr(Exp𝒮,𝒜ℬVaud-priv[λ]succeeds)|≤ϵ(λ).Definition 6 (privacy [22]).
The RFID system𝒮 is said to be P-private if all the adversaries which belong to class P are trivial following Definition 5.The implications between Vaudenay’s privacy notions are as follows:(5)STRONG⇒DESTRUCTIVE⇒FORWARD⇒WEAK⇓⇓⇓⇓NARROW-STRONG⇒NARROW-DESTRUCTIVE⇒NARROW-FORWARD⇒NARROW-WEAKThe main result of Vaudenay is thatSTRONG-privacy is impossible, by proving that a DESTRUCTIVE-private protocol is not NARROW-STRONG-private. However, Vaudenay does not define which privacy level should be targeted by a protocol: it is never specified if NARROW-STRONG-privacy is better or not than DESTRUCTIVE-privacy.Also, it is not explicit how the blinded adversary𝒜ℬ operates. Basically, there are two options: (i) 𝒜ℬ aims the same probability than 𝒜, or (ii) 𝒜ℬ aims the same behavior than 𝒜. It is obvious that the first option allows proving the privacy of some protocols which are actually not private, but this should be correctly formalized.


## 5.4. Extensions of the Model

### 5.4.1.  Model [21], 2008

Paise and Vaudenay extended the Vaudenay model to analyze mutual authentication protocols. Actually, they enriched the definition of the RFID system𝒮 by introducing an output on the tag side: either the tag accepts the reader (if legitimate) and outputs OK, or rejects it (if not) and outputs ⊥. This formalizes the concept of reader authentication. Nevertheless, their extension does not modify the core of the Vaudenay model.They also showed an important impossibility result: if the corruption of a tag reveals its entire state (and not only its secretk𝒯), then no RFID scheme providing reader authentication is NARROW-FORWARD-private. To counter this issue, they claimed that the temporary memory of a tag should be automatically erased as soon as the tag is put back as free. However, this idea is not formalized in the paper.This division between the persistent and the temporary memory of a tag has also been investigated by Armknecht et al. [26]. Based on the work of Paise and Vaudenay, they showed several impossibility results in attack scenarios with special uses of tag corruption.


### 5.4.2. Model [20], 2011

Ouafi presented in his thesis an adaptation of the Vaudenay model in order to counter Vaudenay’s impossibility result ofSTRONG-privacy. Concretely, the author proposed to incorporate the blinder with the adversary, so that the blinder has the knowledge of all the random choices and incoming messages made by the adversary. With this new definition of the blinder, Ouafi proved that STRONG-privacy can be ensured. This result is demonstrated with a public-key-based authentication protocol where the encryption scheme is IND-CCA2 secure and PA1+ plaintext-aware. (More details about these security notions can be found in [27].)


### 5.4.3. Other Extensions

The Vaudenay model has also been broadened in different works. In a nutshell, this is generally performed via the addition of a new oracle to the adversary capabilities (e.g., Timer in [28], MakeInactive in [29], or DestroyReader in [30]) and the corresponding new adversary class (e.g., the TIMEFUL class when 𝒜 is allowed to use Timer).


## 5.4.1.  Model [21], 2008

Paise and Vaudenay extended the Vaudenay model to analyze mutual authentication protocols. Actually, they enriched the definition of the RFID system𝒮 by introducing an output on the tag side: either the tag accepts the reader (if legitimate) and outputs OK, or rejects it (if not) and outputs ⊥. This formalizes the concept of reader authentication. Nevertheless, their extension does not modify the core of the Vaudenay model.They also showed an important impossibility result: if the corruption of a tag reveals its entire state (and not only its secretk𝒯), then no RFID scheme providing reader authentication is NARROW-FORWARD-private. To counter this issue, they claimed that the temporary memory of a tag should be automatically erased as soon as the tag is put back as free. However, this idea is not formalized in the paper.This division between the persistent and the temporary memory of a tag has also been investigated by Armknecht et al. [26]. Based on the work of Paise and Vaudenay, they showed several impossibility results in attack scenarios with special uses of tag corruption.


## 5.4.2. Model [20], 2011

Ouafi presented in his thesis an adaptation of the Vaudenay model in order to counter Vaudenay’s impossibility result ofSTRONG-privacy. Concretely, the author proposed to incorporate the blinder with the adversary, so that the blinder has the knowledge of all the random choices and incoming messages made by the adversary. With this new definition of the blinder, Ouafi proved that STRONG-privacy can be ensured. This result is demonstrated with a public-key-based authentication protocol where the encryption scheme is IND-CCA2 secure and PA1+ plaintext-aware. (More details about these security notions can be found in [27].)


## 5.4.3. Other Extensions

The Vaudenay model has also been broadened in different works. In a nutshell, this is generally performed via the addition of a new oracle to the adversary capabilities (e.g., Timer in [28], MakeInactive in [29], or DestroyReader in [30]) and the corresponding new adversary class (e.g., the TIMEFUL class when 𝒜 is allowed to use Timer).


## 6. Van Le et al. [10, 18], 2007

Also in 2007, van Le et al. introduced a privacy model in [18] (and an extended version in [10]) that is derived from the universal composability (UC) framework [31, 32] (and not on the oracle-based framework). Their aim was to provide security proofs of protocols under concurrent and modular composition, such that protocols can be easily incorporated in more complex systems without reanalyses. Basically, the model, denoted LBM in the following, is based on the indistinguishability between two worlds: the real world and the ideal one.The transposition of RFID privacy into such a framework is a great contribution since universal composability is considered as one of the most powerful tools for security, especially when composition among several functionalities is required.


### 6.1. UC Security

General statements about the UC framework are briefly detailed in AppendixA for the reader nonfamiliar with the field. Here, we present the security notion provided in such a framework.To prove that anIdent protocol is as secure as the corresponding ideal functionality ℱ, no environment 𝒵 should distinguish if it is interacting with the real adversary 𝒜 and Ident (i.e., the real world), or with the simulated adversary Sim and ℱ (i.e., the ideal world). Consequently, ℱ must be well defined such that all the targeted security properties are trivially ensured. Canetti formally defines this concept in [31] as follows, where PPT denotes probabilistic polynomial time turing machine.Definition 7 (UC-emulation [31]).
A protocolIdentUC-emulates a protocol Φ if, for all PPT adversary 𝒜, there exists a PPT simulated adversary Sim such that, for all PPT environment 𝒵, the distributions ExecIdent,𝒜,𝒵 and ExecΦ,Sim,𝒵 are indistinguishable.Based on this security framework, van Le et al. designed in [10, 18] several ideal functionalities to formalize anonymous authentication as well as anonymous authenticated key exchange.


### 6.2. Description of the LBM Model

The advantage of using this UC-based model is that all the possible adversaries and environments are considered during the security proof that can be carried out with LBM. In this paper, we only focus on theforward-security objective led by anonymous authentication.


#### 6.2.1. Assumptions of an RFID System𝒮

First, the LBM model establishes that the readerℛ is the only entity that can start a protocol execution. Then, it considers that only tags can be corrupted by an adversary 𝒜. Upon corruption of a tag, 𝒜 obtains its keys and all its persistent memory values.


#### 6.2.2. The LBM Ideal Functionalityℱaauth

This ideal functionality represents theanonymous authentication security objective of a given protocol. To do so, several parties (at least ℛ and one tag) may be involved in a protocol execution. Two parties 𝒫 and 𝒫′ are said to be feasible partners if and only if they are, respectively, ℛ and a tag. In the ideal world, communication channels between tags and ℛ are assumed to be anonymous (meaning that they only reveal the type type(𝒫) of a party, either tag or reader), and a sent message is necessarily delivered to the recipient. Finally, state(𝒫) is the list of all the execution records, and active(𝒫) is the list of all the preceding incomplete executions (Box 5).Box 5
Ideal Functionalityℱaauth
(i)Upon receiving Initiate  from  𝒫: if 𝒫 is corrupted then ignore this message. Else generate a unique
execution identificationsid, record init(sid,𝒫) and send init(sid,type(𝒫),active(𝒫)) to the adversary.
(ii)Upon receiving Accept(sid,sid')  from the adversary: if there are two records init(sid,𝒫)
andinit(sid',𝒫') where 𝒫 and 𝒫' are feasible partners, then remove them, record
partner
(
s
i
d
'
,
𝒫
'
,
s
i
d
,
𝒫
) and write output ACCEPT(𝒫') to 𝒫. Else if there is a record
partner
(
s
i
d
,
𝒫
,
s
i
d
'
,
𝒫
'
), then remove it and write output ACCEPT(𝒫') to 𝒫.
(iii)Upon receiving Impersonate(sid,𝒫')   from the adversary: if there is a record init(sid,𝒫)
and party𝒫' is corrupted, then remove this record and write output ACCEPT(𝒫') to 𝒫.
(iv)Upon receiving Corrupt(sid)   from the adversary: if there is a record init(sid,𝒫) or
partner
(
s
i
d
,
𝒫
,
s
i
d
'
,
𝒫
'
) such that 𝒫 is corruptible, then mark 𝒫 as corrupted and remove state(𝒫).


#### 6.2.3.Forward-Security

When the adversary corrupts a tag𝒯, it gets its identifier ID𝒯 and is then able to impersonate this tag using the Impersonate command. A corrupted tag is thereafter considered as totally controlled by the adversary. Consequently, ℱaauth will no longer manage the behavior of this corrupted tag and thus will reject every Initiate command from this tag. As state(𝒯) is removed after a corruption, the adversary is not able to link the related tag to its previous authentication.However, the adversary is able to link all the incomplete protocol executions of a corrupted tag𝒯 up to the last successfully completed one, based on the knowledge of active(𝒯). Thus, the ideal functionality obviously provides forward-security for all previous completed protocol executions.


## 6.1. UC Security

General statements about the UC framework are briefly detailed in AppendixA for the reader nonfamiliar with the field. Here, we present the security notion provided in such a framework.To prove that anIdent protocol is as secure as the corresponding ideal functionality ℱ, no environment 𝒵 should distinguish if it is interacting with the real adversary 𝒜 and Ident (i.e., the real world), or with the simulated adversary Sim and ℱ (i.e., the ideal world). Consequently, ℱ must be well defined such that all the targeted security properties are trivially ensured. Canetti formally defines this concept in [31] as follows, where PPT denotes probabilistic polynomial time turing machine.Definition 7 (UC-emulation [31]).
A protocolIdentUC-emulates a protocol Φ if, for all PPT adversary 𝒜, there exists a PPT simulated adversary Sim such that, for all PPT environment 𝒵, the distributions ExecIdent,𝒜,𝒵 and ExecΦ,Sim,𝒵 are indistinguishable.Based on this security framework, van Le et al. designed in [10, 18] several ideal functionalities to formalize anonymous authentication as well as anonymous authenticated key exchange.


## 6.2. Description of the LBM Model

The advantage of using this UC-based model is that all the possible adversaries and environments are considered during the security proof that can be carried out with LBM. In this paper, we only focus on theforward-security objective led by anonymous authentication.


### 6.2.1. Assumptions of an RFID System𝒮

First, the LBM model establishes that the readerℛ is the only entity that can start a protocol execution. Then, it considers that only tags can be corrupted by an adversary 𝒜. Upon corruption of a tag, 𝒜 obtains its keys and all its persistent memory values.


### 6.2.2. The LBM Ideal Functionalityℱaauth

This ideal functionality represents theanonymous authentication security objective of a given protocol. To do so, several parties (at least ℛ and one tag) may be involved in a protocol execution. Two parties 𝒫 and 𝒫′ are said to be feasible partners if and only if they are, respectively, ℛ and a tag. In the ideal world, communication channels between tags and ℛ are assumed to be anonymous (meaning that they only reveal the type type(𝒫) of a party, either tag or reader), and a sent message is necessarily delivered to the recipient. Finally, state(𝒫) is the list of all the execution records, and active(𝒫) is the list of all the preceding incomplete executions (Box 5).Box 5
Ideal Functionalityℱaauth
(i)Upon receiving Initiate  from  𝒫: if 𝒫 is corrupted then ignore this message. Else generate a unique
execution identificationsid, record init(sid,𝒫) and send init(sid,type(𝒫),active(𝒫)) to the adversary.
(ii)Upon receiving Accept(sid,sid')  from the adversary: if there are two records init(sid,𝒫)
andinit(sid',𝒫') where 𝒫 and 𝒫' are feasible partners, then remove them, record
partner
(
s
i
d
'
,
𝒫
'
,
s
i
d
,
𝒫
) and write output ACCEPT(𝒫') to 𝒫. Else if there is a record
partner
(
s
i
d
,
𝒫
,
s
i
d
'
,
𝒫
'
), then remove it and write output ACCEPT(𝒫') to 𝒫.
(iii)Upon receiving Impersonate(sid,𝒫')   from the adversary: if there is a record init(sid,𝒫)
and party𝒫' is corrupted, then remove this record and write output ACCEPT(𝒫') to 𝒫.
(iv)Upon receiving Corrupt(sid)   from the adversary: if there is a record init(sid,𝒫) or
partner
(
s
i
d
,
𝒫
,
s
i
d
'
,
𝒫
'
) such that 𝒫 is corruptible, then mark 𝒫 as corrupted and remove state(𝒫).


### 6.2.3.Forward-Security

When the adversary corrupts a tag𝒯, it gets its identifier ID𝒯 and is then able to impersonate this tag using the Impersonate command. A corrupted tag is thereafter considered as totally controlled by the adversary. Consequently, ℱaauth will no longer manage the behavior of this corrupted tag and thus will reject every Initiate command from this tag. As state(𝒯) is removed after a corruption, the adversary is not able to link the related tag to its previous authentication.However, the adversary is able to link all the incomplete protocol executions of a corrupted tag𝒯 up to the last successfully completed one, based on the knowledge of active(𝒯). Thus, the ideal functionality obviously provides forward-security for all previous completed protocol executions.


## 6.2.1. Assumptions of an RFID System𝒮

First, the LBM model establishes that the readerℛ is the only entity that can start a protocol execution. Then, it considers that only tags can be corrupted by an adversary 𝒜. Upon corruption of a tag, 𝒜 obtains its keys and all its persistent memory values.


## 6.2.2. The LBM Ideal Functionalityℱaauth

This ideal functionality represents theanonymous authentication security objective of a given protocol. To do so, several parties (at least ℛ and one tag) may be involved in a protocol execution. Two parties 𝒫 and 𝒫′ are said to be feasible partners if and only if they are, respectively, ℛ and a tag. In the ideal world, communication channels between tags and ℛ are assumed to be anonymous (meaning that they only reveal the type type(𝒫) of a party, either tag or reader), and a sent message is necessarily delivered to the recipient. Finally, state(𝒫) is the list of all the execution records, and active(𝒫) is the list of all the preceding incomplete executions (Box 5).Box 5
Ideal Functionalityℱaauth
(i)Upon receiving Initiate  from  𝒫: if 𝒫 is corrupted then ignore this message. Else generate a unique
execution identificationsid, record init(sid,𝒫) and send init(sid,type(𝒫),active(𝒫)) to the adversary.
(ii)Upon receiving Accept(sid,sid')  from the adversary: if there are two records init(sid,𝒫)
andinit(sid',𝒫') where 𝒫 and 𝒫' are feasible partners, then remove them, record
partner
(
s
i
d
'
,
𝒫
'
,
s
i
d
,
𝒫
) and write output ACCEPT(𝒫') to 𝒫. Else if there is a record
partner
(
s
i
d
,
𝒫
,
s
i
d
'
,
𝒫
'
), then remove it and write output ACCEPT(𝒫') to 𝒫.
(iii)Upon receiving Impersonate(sid,𝒫')   from the adversary: if there is a record init(sid,𝒫)
and party𝒫' is corrupted, then remove this record and write output ACCEPT(𝒫') to 𝒫.
(iv)Upon receiving Corrupt(sid)   from the adversary: if there is a record init(sid,𝒫) or
partner
(
s
i
d
,
𝒫
,
s
i
d
'
,
𝒫
'
) such that 𝒫 is corruptible, then mark 𝒫 as corrupted and remove state(𝒫).


## 6.2.3.Forward-Security

When the adversary corrupts a tag𝒯, it gets its identifier ID𝒯 and is then able to impersonate this tag using the Impersonate command. A corrupted tag is thereafter considered as totally controlled by the adversary. Consequently, ℱaauth will no longer manage the behavior of this corrupted tag and thus will reject every Initiate command from this tag. As state(𝒯) is removed after a corruption, the adversary is not able to link the related tag to its previous authentication.However, the adversary is able to link all the incomplete protocol executions of a corrupted tag𝒯 up to the last successfully completed one, based on the knowledge of active(𝒯). Thus, the ideal functionality obviously provides forward-security for all previous completed protocol executions.


## 7. Van Deursen et al. [13], 2008

The model of van Deursen et al., published in 2008, definesuntraceability in the standard Dolev-Yao intruder model [33]. The untraceability notion is inspired by the anonymity theory given in [34, 35] and is used as a formal verification of RFID protocols. Such a technique is based on symbolic protocol analysis approach (and not on the oracle-based framework). This model will be called DMR in what follows.


### 7.1. Definition of the System

We remind below the basic definitions given in DMR.First, the system is composed of a number ofagents (e.g., Alice or Bob) that execute a security protocol, the latter being described by a set of traces. A security protocol represents the behavior of a set of roles (i.e., initiator, responder, and server), each one specifying a set of actions. These actions depict the role specifications with a sequence of events (e.g., sending or reception of a message). A role term is a message contained in an event, and it is built from basic role terms (e.g., nonces, role names, or keys). A complex term is built with functions (e.g., tupling, encryption, hashing, and XOR).Each tracet is composed of interleaved runs and run prefixes, denoted subtraces. A run of a role R is a protocol execution from R’s point of view, denoted R#sid, where sid is a (possibly unique) run identifier. Thus, a run is an instantiation of a role. A run event is an instantiation of a role event, that is an instantiation of an event’s role terms. A run term denotes an instantiated role term. A run prefix is an unfinished run.An adversary𝒜 is in the Dolev-Yao model and is characterized by its knowledge. This knowledge is composed of a set of run terms known at the beginning, and the set of run terms that it will observe during its attack. The adversary is allowed to manipulate the information of its knowledge to understand terms or build new ones. However, perfect cryptography is assumed (i.e., cryptographic primitives are assumed unbreakable and considered as black boxes). The inference of term a from term set K is denoted by K⊢a.Corrupted agents are modeled. (Note that, regarding corruption, there is no restriction about the role of such an agent: it can be either a tag or a reader.)𝒜 is given all the secrets of a corrupted agent in its initial knowledge. When an agent is corrupted, it is said to be “destroyed,” that is, it cannot be used during 𝒜’s attack. Yet, the security evaluation of a system is done on noncorrupted agents, that is, 𝒜 cannot have access to the secret of an agent after the beginning of its attack.


### 7.2. Untraceability Notion

First, the model defines several notions oflinkability, reinterpretation, and indistinguishability, before giving the untraceability one.Definition 8 (linkability of subtraces [13]).
Two subtracestiR and tjR are linked, denoted by L(tiR,tjR), if they are instantiated by the same agent:
(6)L(tiR,tjR)≡(agent(tiR)=agent(tjR)).The notion ofreinterpretation has been introduced in [34] in order to show that subterms of a message can be replaced by other subterms if the adversary 𝒜 is not able to understand these subterms. Note that, when 𝒜 is able to understand a subterm, it remains unchanged.Definition 9 (reinterpretation [13]).
A mapμ from run terms to run terms is called a reinterpretation under knowledge set K if it and its inverse μ-1 satisfy the following conditions: (i)
μ(a)=a if a is a basic run term,(ii)
μ(a)=(μ(a1),…,μ(an)) if a=(a1,…,an) is n-tuple,(iii)
μ({a}k)={μ(a)}k if K⊢k-1 or (K⊢a∧K⊢k), and {·}k is an encryption under key k,(iv)
μ(f(a))=f(μ(a)) if K⊢a or f is not a hash function.Reinterpretations are used to defineindistinguishability of traces.Definition 10 (indistinguishability of traces [13]).
LetK be the adversary’s knowledge at the end of trace t. The trace t is indistinguishable from a trace t′, denoted t~t′, if there is a reinterpretation μ under K, such that μ(tiR)=t′iR for all roles R and subtraces tiR.From all the above notions, the untraceability notion of a role is defined as follows.Definition 11 (untraceability [13]).
AnIdent protocol is said to be untraceable with respect to role R if:
(7)(∀t∈Traces(Ident))(∀i≠j)(L(tiR,tjR)⇒(∃t′∈Traces(Ident))((t~t′)∧¬L(t′iR,t′jR))).
In this paper, if no role is specified, we consider that “untraceability” means “untraceability for role 𝒯.”


## 7.1. Definition of the System

We remind below the basic definitions given in DMR.First, the system is composed of a number ofagents (e.g., Alice or Bob) that execute a security protocol, the latter being described by a set of traces. A security protocol represents the behavior of a set of roles (i.e., initiator, responder, and server), each one specifying a set of actions. These actions depict the role specifications with a sequence of events (e.g., sending or reception of a message). A role term is a message contained in an event, and it is built from basic role terms (e.g., nonces, role names, or keys). A complex term is built with functions (e.g., tupling, encryption, hashing, and XOR).Each tracet is composed of interleaved runs and run prefixes, denoted subtraces. A run of a role R is a protocol execution from R’s point of view, denoted R#sid, where sid is a (possibly unique) run identifier. Thus, a run is an instantiation of a role. A run event is an instantiation of a role event, that is an instantiation of an event’s role terms. A run term denotes an instantiated role term. A run prefix is an unfinished run.An adversary𝒜 is in the Dolev-Yao model and is characterized by its knowledge. This knowledge is composed of a set of run terms known at the beginning, and the set of run terms that it will observe during its attack. The adversary is allowed to manipulate the information of its knowledge to understand terms or build new ones. However, perfect cryptography is assumed (i.e., cryptographic primitives are assumed unbreakable and considered as black boxes). The inference of term a from term set K is denoted by K⊢a.Corrupted agents are modeled. (Note that, regarding corruption, there is no restriction about the role of such an agent: it can be either a tag or a reader.)𝒜 is given all the secrets of a corrupted agent in its initial knowledge. When an agent is corrupted, it is said to be “destroyed,” that is, it cannot be used during 𝒜’s attack. Yet, the security evaluation of a system is done on noncorrupted agents, that is, 𝒜 cannot have access to the secret of an agent after the beginning of its attack.


## 7.2. Untraceability Notion

First, the model defines several notions oflinkability, reinterpretation, and indistinguishability, before giving the untraceability one.Definition 8 (linkability of subtraces [13]).
Two subtracestiR and tjR are linked, denoted by L(tiR,tjR), if they are instantiated by the same agent:
(6)L(tiR,tjR)≡(agent(tiR)=agent(tjR)).The notion ofreinterpretation has been introduced in [34] in order to show that subterms of a message can be replaced by other subterms if the adversary 𝒜 is not able to understand these subterms. Note that, when 𝒜 is able to understand a subterm, it remains unchanged.Definition 9 (reinterpretation [13]).
A mapμ from run terms to run terms is called a reinterpretation under knowledge set K if it and its inverse μ-1 satisfy the following conditions: (i)
μ(a)=a if a is a basic run term,(ii)
μ(a)=(μ(a1),…,μ(an)) if a=(a1,…,an) is n-tuple,(iii)
μ({a}k)={μ(a)}k if K⊢k-1 or (K⊢a∧K⊢k), and {·}k is an encryption under key k,(iv)
μ(f(a))=f(μ(a)) if K⊢a or f is not a hash function.Reinterpretations are used to defineindistinguishability of traces.Definition 10 (indistinguishability of traces [13]).
LetK be the adversary’s knowledge at the end of trace t. The trace t is indistinguishable from a trace t′, denoted t~t′, if there is a reinterpretation μ under K, such that μ(tiR)=t′iR for all roles R and subtraces tiR.From all the above notions, the untraceability notion of a role is defined as follows.Definition 11 (untraceability [13]).
AnIdent protocol is said to be untraceable with respect to role R if:
(7)(∀t∈Traces(Ident))(∀i≠j)(L(tiR,tjR)⇒(∃t′∈Traces(Ident))((t~t′)∧¬L(t′iR,t′jR))).
In this paper, if no role is specified, we consider that “untraceability” means “untraceability for role 𝒯.”


## 8. Canard et al. [11, 36], 2010

In the same vein as the Vaudenay model, Canard et al. proposed in 2010 a security model that comprises the properties of (strong) correctness, soundness, and untraceability. We only present the last notion. Contrary to Vaudenay, the authors only defined untraceability (and not privacy in general) and their main goal was to use the strongest adversary of the Vaudenay model. During the following, this model will be denoted CCEG.


### 8.1. Oracles

As for Vaudenay,DB is empty after the setup of the system, and a tag can be either free or drawn. Then 𝒜 has access to all the generic oracles. It may also use the following ones.(i)
DrawTag(k)→(𝒯1,…,𝒯k) works similarly as the one of Vaudenay. It first randomly and uniformly selects k tags between all existing (not already drawn) ones. For each chosen tag, the oracle gives it a new pseudonym denoted by 𝒯i and changes its status from free to drawn. Finally, since 𝒜 cannot create here fake tags, then the oracle only outputs all the generated pseudonyms (𝒯1,…,𝒯k) in any order. If there is not enough free tags (i.e., less than k), then the oracle outputs ⊥. All relations (𝒯i,ID𝒯i) are kept in an a priori secret table denoted by Tab.(ii)
Free(𝒯) works exactly as the one of Vaudenay.


### 8.2. Untraceability Experiment

From the oracles given above, CCEG defines three classes of polynomial-time adversaries for the untraceability experiment.Definition 12 (adversary class [11]).
An adversary class is said to be(i)
STRONG if 𝒜 has access to all the oracles;(ii)
DESTRUCTIVE if 𝒜 cannot use anymore a “corrupted” tag (i.e., the tag has been destroyed);(iii)
WEAK if 𝒜 has no access to the Corrupt oracle;The authors do not define theNARROW adversary class introduced in the Vaudenay model (see Section 5 for more details). They consider that the model aims to be as powerful as possible: the NARROW notion weakens the adversary.Alink is a couple of pseudonyms (𝒯i,𝒯j) associated to the same identifier in Tab. Some links are considered obvious (e.g., both 𝒯i and 𝒯j have been corrupted). Therefore, the authors define the notion of nonobvious link. As remark, links are chronologically ordered, that is, (𝒯i,𝒯j) means that 𝒯i has been freed before 𝒯j has been drawn.Definition 13 (nonobvious link (NOL) [11]).
(
𝒯
i
,
𝒯
j
) is a nonobvious link if 𝒯i and 𝒯j refer to the same ID𝒯 in Tab and if a “dummy” adversary 𝒜d, that only has access to CreateTag, DrawTag, Free, and Corrupt, is not able to output this link with a probability better than 1/2. Moreover, a nonobvious link is said to be (i)
standard if 𝒜 has not corrupted 𝒯i or 𝒯j;(ii)
past if 𝒜 has corrupted 𝒯j;(iii)
future if 𝒜 has corrupted 𝒯i.Note that this model uses a “dummy” adversary𝒜d, instead of a blinded adversary 𝒜ℬ as in the Vaudenay model. Both adversaries are equivalent but not identical. Indeed, the main difference is that Vaudenay’s blinder ℬ is an entity clearly separated from 𝒜ℬ. Therefore ℬ does not know the random choices done by the 𝒜ℬ during the experiment. On the opposite in CCEG, 𝒜d is a single entity, and consequently it is aware of its random choices.AWEAK adversary is only able to output a standard NOL as it cannot query the Corrupt oracle. A DESTRUCTIVE adversary is not able to output a future NOL as a tag corruption destroys the tag (and thus prevents the tag from being drawn again). However, this adversary can output a standard or past NOL. Then, a STRONG adversary is able to output every NOL.CCEG’s untraceability experiment is given in Box6. P is the adversary class, P∈{STRONG,DESTRUCTIVE,WEAK}.Box 6
ExperimentExp𝒮,𝒜CCEG-UNT[λ]
(1)𝒞 initializes the system and sends 1λ, 𝒮's public parameters param (including KP) to 𝒜.
(2)𝒜 interacts with the whole system, limited by its class P.
(3)𝒜 returns one link (𝒯i,𝒯j).
Exp
𝒮
,
𝒜
C
C
E
G
-
U
N
T succeeds if (𝒯i,𝒯j) is a NOL.


### 8.3. Untraceability Notions

With the previous experiment, the CCEG untraceability of a system𝒮 is proved if no adversary is able to output a NOL with a probability better than the one of the dummy adversary 𝒜d.Definition 14 (untraceability [11]).
An RFID system𝒮 is said to be standard-untraceable (resp., past-untraceable/future-untraceable) if, for every WEAK (resp., DESTRUCTIVE/STRONG) adversary 𝒜 running in polynomial-time, it is possible to define a “dummy” adversary 𝒜d that only has access to oracles CreateTag, DrawTag, Free, and Corrupt such that
(8)|Pr(Exp𝒮,𝒜CCEG-UNT[λ]succeeds)-Pr(Exp𝒮,𝒜dCCEG-UNT[λ]succeeds)|≤ϵ(λ).Direct implications are made from these notions:(9)Future-untraceability⇒Past-untraceability⇒Standard-untraceabilityThe main result of this paper is thatfuture-untraceability (the strongest privacy property) is achievable.


## 8.1. Oracles

As for Vaudenay,DB is empty after the setup of the system, and a tag can be either free or drawn. Then 𝒜 has access to all the generic oracles. It may also use the following ones.(i)
DrawTag(k)→(𝒯1,…,𝒯k) works similarly as the one of Vaudenay. It first randomly and uniformly selects k tags between all existing (not already drawn) ones. For each chosen tag, the oracle gives it a new pseudonym denoted by 𝒯i and changes its status from free to drawn. Finally, since 𝒜 cannot create here fake tags, then the oracle only outputs all the generated pseudonyms (𝒯1,…,𝒯k) in any order. If there is not enough free tags (i.e., less than k), then the oracle outputs ⊥. All relations (𝒯i,ID𝒯i) are kept in an a priori secret table denoted by Tab.(ii)
Free(𝒯) works exactly as the one of Vaudenay.


## 8.2. Untraceability Experiment

From the oracles given above, CCEG defines three classes of polynomial-time adversaries for the untraceability experiment.Definition 12 (adversary class [11]).
An adversary class is said to be(i)
STRONG if 𝒜 has access to all the oracles;(ii)
DESTRUCTIVE if 𝒜 cannot use anymore a “corrupted” tag (i.e., the tag has been destroyed);(iii)
WEAK if 𝒜 has no access to the Corrupt oracle;The authors do not define theNARROW adversary class introduced in the Vaudenay model (see Section 5 for more details). They consider that the model aims to be as powerful as possible: the NARROW notion weakens the adversary.Alink is a couple of pseudonyms (𝒯i,𝒯j) associated to the same identifier in Tab. Some links are considered obvious (e.g., both 𝒯i and 𝒯j have been corrupted). Therefore, the authors define the notion of nonobvious link. As remark, links are chronologically ordered, that is, (𝒯i,𝒯j) means that 𝒯i has been freed before 𝒯j has been drawn.Definition 13 (nonobvious link (NOL) [11]).
(
𝒯
i
,
𝒯
j
) is a nonobvious link if 𝒯i and 𝒯j refer to the same ID𝒯 in Tab and if a “dummy” adversary 𝒜d, that only has access to CreateTag, DrawTag, Free, and Corrupt, is not able to output this link with a probability better than 1/2. Moreover, a nonobvious link is said to be (i)
standard if 𝒜 has not corrupted 𝒯i or 𝒯j;(ii)
past if 𝒜 has corrupted 𝒯j;(iii)
future if 𝒜 has corrupted 𝒯i.Note that this model uses a “dummy” adversary𝒜d, instead of a blinded adversary 𝒜ℬ as in the Vaudenay model. Both adversaries are equivalent but not identical. Indeed, the main difference is that Vaudenay’s blinder ℬ is an entity clearly separated from 𝒜ℬ. Therefore ℬ does not know the random choices done by the 𝒜ℬ during the experiment. On the opposite in CCEG, 𝒜d is a single entity, and consequently it is aware of its random choices.AWEAK adversary is only able to output a standard NOL as it cannot query the Corrupt oracle. A DESTRUCTIVE adversary is not able to output a future NOL as a tag corruption destroys the tag (and thus prevents the tag from being drawn again). However, this adversary can output a standard or past NOL. Then, a STRONG adversary is able to output every NOL.CCEG’s untraceability experiment is given in Box6. P is the adversary class, P∈{STRONG,DESTRUCTIVE,WEAK}.Box 6
ExperimentExp𝒮,𝒜CCEG-UNT[λ]
(1)𝒞 initializes the system and sends 1λ, 𝒮's public parameters param (including KP) to 𝒜.
(2)𝒜 interacts with the whole system, limited by its class P.
(3)𝒜 returns one link (𝒯i,𝒯j).
Exp
𝒮
,
𝒜
C
C
E
G
-
U
N
T succeeds if (𝒯i,𝒯j) is a NOL.


## 8.3. Untraceability Notions

With the previous experiment, the CCEG untraceability of a system𝒮 is proved if no adversary is able to output a NOL with a probability better than the one of the dummy adversary 𝒜d.Definition 14 (untraceability [11]).
An RFID system𝒮 is said to be standard-untraceable (resp., past-untraceable/future-untraceable) if, for every WEAK (resp., DESTRUCTIVE/STRONG) adversary 𝒜 running in polynomial-time, it is possible to define a “dummy” adversary 𝒜d that only has access to oracles CreateTag, DrawTag, Free, and Corrupt such that
(8)|Pr(Exp𝒮,𝒜CCEG-UNT[λ]succeeds)-Pr(Exp𝒮,𝒜dCCEG-UNT[λ]succeeds)|≤ϵ(λ).Direct implications are made from these notions:(9)Future-untraceability⇒Past-untraceability⇒Standard-untraceabilityThe main result of this paper is thatfuture-untraceability (the strongest privacy property) is achievable.


## 9. Deng et al. [12], 2010

Also in 2010, Deng et al. proposed a new framework based on zero-knowledge formulation to define the security and privacy of RFID systems. Here, we only present thezero-knowledge privacy (denoted ZK-privacy), which is a new way of thinking in privacy for RFID. This model, denoted DLYZ in the sequel, is part of the unpredictability models family [12, 14, 17, 19]. They all rely on the unpredictability of the output returned by a tag or a reader in a protocol execution. In this paper, we decide to only present DLYZ since it is the most achieved model of this family.


### 9.1. Considered Protocol

This model considers that an RFID protocol executionπ is, w.l.o.g., always initialized by ℛ, and π consists of 2γ+1 rounds for some γ≥1. Each protocol execution π is associated to a unique identifier sid. At each execution, a tag may update its internal state and secret key, and ℛ may update its internal state and database. The update process (of the secret key or the internal state) on a tag always erases the old values. The outputs bits oℛsid and o𝒯sid (equal to 1 if ℛ and 𝒯 accept the protocol execution with identifier sid, or 0 otherwise) are publicly known. Note that the authors claim that each tag 𝒯 has its output bit o𝒯sid=0 if the authentication protocol is not mutual. However, we consider this fact too limiting since 𝒯 can have an output (possibly known by 𝒜), even if it may not authenticate the reader. For instance, its output can be “I arrived correctly at the end of the protocol on my side.”DLYZ assumes that a tag may participate to at mosts executions in its life with ℛ; thus ℛ is involved in at most sn executions, where s is polynomial in λ and n is the total number of tags involved in the system.


### 9.2. Oracles

In a nutshell, DLYZ aims to analyze protocols where entities’ secrets may potentially be updated at every protocol execution. Therefore, the model automatically enumerates the internal information of each entity. At the initialization of the system, the database is in an initial state, calledDB0, and already stores the secrets of all the tags, that is, a SetupTag has already been performed on every tag. The only differences in the initialization are the following: (i)
SetupReader additionally generates ℛ’s initial internal state sℛ0;(ii)
SetupTag associates to every tag 𝒯 a triplet (ξ𝒯,k𝒯0,s𝒯0), which is, respectively, 𝒯’s public parameter, initial secret key, and initial internal state.This information is stored inDB0. Finally, let param=(KP,{ξ𝒯}∀𝒯) denote the public parameters of the system 𝒮. At the end of the system’s initialization, all the tags are accessible to the adversary.Then,𝒜 has access to the following modified generic oracles. (i)
Launch()→(π,m) makes ℛ launch a new protocol execution π and generates the 1st-round message m which is also used as the execution identifier sid. If this is the jth new execution run by ℛ, then ℛ stores η1=m into its internal state sℛj.(ii)
SendTag(m,𝒯)→r sends m to 𝒯. The output response r of 𝒯 is as follows.
(1)
If𝒯 currently does not run any execution, then 𝒯
(a)
initiates a new execution with identifiersid=m,(b)
treatsm as the 1st-round message of the new execution,(c)
and returns the2nd-round message (sid,r=α1).(2)
If𝒯 is currently running an incomplete execution with identifier sid and is waiting for the uth message from ℛ (u≥2), then 𝒯 works as follows:
(a)
if2≤u≤γ, 𝒯 treats m as the uth message from ℛ and returns the next round message (sid,r=αu);(b)
ifu=γ+1 (i.e., the last-round message of the execution), 𝒯 returns its output o𝒯sid and updates its internal state to s𝒯v+1 (where sid corresponds to the vth execution run by 𝒯, where 1≤v≤s).(iii)
SendReader(m,sid)→r sends m to ℛ for the execution with identifier sid. After receiving m, ℛ checks from its internal state whether it is running such an execution, and ℛ’s response r is as follows.
(1)
Ifℛ is currently running an incomplete execution with identifier sid and is waiting for the uth message from a tag (1≤u≤γ), then ℛ works as follows:
(a)
ifu≤γ, ℛ treats m as the uth message from the tag and returns the next round message r=ηu+1;(b)
ifu=γ, ℛ returns the last-round message r=ηγ+1 and its output oℛsid and updates its internal state to sℛj+1 and the database DBj+1 (where sid corresponds to the jth execution run by ℛ).(2)
In all the other cases,ℛ returns ⊥ (for invalid queries).(iv)
Corrupt(𝒯)→(k𝒯v,s𝒯v) returns the secret key k𝒯v and the internal state s𝒯v currently held by 𝒯. Once 𝒯 is corrupted, all its actions are controlled and performed by 𝒜.For a completed protocol execution with identifiersid, the transcript of the exchanged messages is (sid,η1sid,α1sid,…,αγsid,ηγ+1sid), excluding the entities’ outputs.Let𝒪 denote the set of these four oracles. 𝒜𝒪(ℛ,T,param) denotes a PPT adversary 𝒜 that takes on input the system public parameters param, the reader ℛ, and the tags set T of the already initialized system. Then 𝒜 interacts with ℛ and the tags of T via the four oracles. 𝒜′𝒪(ℛ,T^,ℐ(𝒯c),aux) denotes a PPT adversary 𝒜′ equivalent to 𝒜, where aux∈{0,1}* generally includes param or some historical state information of 𝒜′. Then 𝒜′ interacts with ℛ and the tags set T^ via the four oracles. 𝒜′ is said to have a blinded access to a challenge tag 𝒯c∉T^ if it interacts with 𝒯c via a special interface ℐ (i.e., a PPT algorithm which runs 𝒯c internally and interacts with 𝒜′ externally). To send a message m to 𝒯c, 𝒜′ sends a SendTag(m,challenge) to ℐ; then ℐ invokes 𝒯c with SendTag(m,𝒯c) and answers 𝒯c’s output to 𝒜′. 𝒜′ does not know which tag is interacting with it. 𝒜′ interacts with 𝒯c via SendTag queries only.Definition 15 (clean tag [12]).
A tag𝒯 is said to be clean if it is not corrupted (i.e., no query to Corrupt on 𝒯) and is not currently running an incomplete execution with ℛ (i.e., 𝒯’s last execution is either finished or aborted).The main goal of this definition is to force the adversary to use some uncorrupted and nonrunning tags to proceed theZK-privacy experiment (see next section). This notion of nonrunning tags is very similar to the TagInit oracle of JW.


### 9.3. Privacy Experiments

In the experiments, a PPT CMIM (concurrent man-in-the-middle) adversary𝒜 (resp., PPT simulator Sim) is composed of a pair of adversaries (𝒜1,𝒜2) (resp., (Sim1,Sim2)) and runs in two stages. Note that, if δ=0, then no challenge tag is selected, and 𝒜 is reduced to 𝒜1 in the experiment.The first experiment given in Box7 is the one performed by the real adversary 𝒜. After the system initialization, 𝒜1 plays with all the entities and returns a set of clean tags C. Then from this set C, a challenge tag 𝒯c is chosen at random. Then 𝒜2 plays with all the entities, including the challenge tag via the interface ℐ, except the set of clean tags. At the end, 𝒜 outputs a view of the system.Box 7
ExperimentExp𝒮,𝒜ZK-priv[λ,n]                               (real world)
(1)𝒞 initializes the system and sends 1λ, param to 𝒜.
(2){C,info}←𝒜1𝒪(ℛ,T,param), where C={𝒯i1,𝒯i2,…,𝒯iδ}⊆T is a set of clean tags
(0≤δ≤n), and info is a state information.
(3)c∈R{1,…,δ}, set 𝒯c=𝒯ic and T^=T-C.
(4)view𝒜←𝒜2𝒪(ℛ,T^,ℐ(𝒯c),info).
(5)  Output(c,view𝒜(λ,n)).Then, the second experiment given in Box8 is the one performed by the simulator Sim. As in the previous experiment, Sim1 plays with all the entities and returns a set of clean tags C. Then from this set C, a challenge tag 𝒯c is chosen at random, but Sim is not informed about its identity and cannot play anymore with this tag. Then Sim2 plays with all the entities, except the set of clean tags. At the end, Sim outputs a simulated view of the system.Box 8
ExperimentExp𝒮,SimZK-priv[λ,n]                                 (simulated world)
(1)𝒞 initializes the system and sends 1λ, param to 𝒜.
(2){C,  info}←Sim1𝒪(ℛ,T,param), where C={𝒯i1,𝒯i2,…,𝒯iδ}⊆T is a set of clean tags (0≤δ≤n),
andinfo is a state information.
(3)c∈R{1,…,δ} unknown to Sim, and set T^=T-C.
(4)sview←Sim2𝒪(ℛ,T^,  info), where sview includes all oracle answers to queries made by Sim.
(5) Output(c,sview(λ,n)).


### 9.4. Privacy Notions

From the previous experiments, theZK-privacy of a system 𝒮 is proved when no one is able to distinguish if it is interacting with the real world or with the simulated one.Definition 16 (ZK-privacy [12]).
An RFID system𝒮 satisfies computational (resp., statistical) ZK-privacy if, for any PPT CMIM adversary 𝒜, there exists a polynomial-time simulator Sim such that, for all sufficiently large λ and any n which is polynomial in λ, the following ensembles are computationally (resp., statistically) indistinguishable: (i)
{c,view𝒜(λ,n)}λ∈ℕ,n∈poly(λ),(ii)
{c,sview(λ,n)}λ∈ℕ,n∈poly(λ).
That is, for any polynomial-time (resp., any computationally power unlimited) algorithm𝒟, it holds that
(10)|Pr[𝒟(λ,n,c,view𝒜(λ,n))=1]-Pr[𝒟(λ,n,c,sview(λ,n))=1]|=ϵ(λ).The probability is taken over the random coins used during the system initialization, the random coins used by𝒜, Sim, ℛ, and all (uncorrupted) tags, the choice of c, and the coins used by the distinguisher algorithm 𝒟.Definition 17 (Forward/Backward-ZK-privacy [12]).
Let us denote(k𝒯cfinal,s𝒯cfinal) (resp., (k𝒯c0,s𝒯c0)) the final (resp., initial) secret key and internal state of the challenge tag 𝒯c at the end (resp., beginning) of Exp𝒮,𝒜ZK-priv. An RFID system 𝒮 is forward (resp., backward)-ZK-private if, for any PPT CMIM adversary 𝒜, there exists a polynomial-time simulator Sim such that, for all sufficiently large λ and any n which is polynomial in λ, the following distributions are indistinguishable: (i)
{k𝒯cfinal,s𝒯cfinal(resp.,k𝒯c0,s𝒯c0),c,view𝒜(λ,n)},(ii)
{k𝒯cfinal,s𝒯cfinal(resp.,k𝒯c0,s𝒯c0),c,sview(λ,n)}.
It is required that𝒯c should remain clean at the end of Exp𝒮,𝒜ZK-priv. Note that 𝒜 is allowed to corrupt it after the end of Exp𝒮,𝒜ZK-priv.One justification of the authors on the way of corrupting𝒯c is that it is enough to give its secrets to 𝒜 at the end. Another reason pointed out by the authors is that forward-ZK or backward-ZK-privacy cannot be achieved if 𝒜 corrupts 𝒯c before the end of the experiment.


## 9.1. Considered Protocol

This model considers that an RFID protocol executionπ is, w.l.o.g., always initialized by ℛ, and π consists of 2γ+1 rounds for some γ≥1. Each protocol execution π is associated to a unique identifier sid. At each execution, a tag may update its internal state and secret key, and ℛ may update its internal state and database. The update process (of the secret key or the internal state) on a tag always erases the old values. The outputs bits oℛsid and o𝒯sid (equal to 1 if ℛ and 𝒯 accept the protocol execution with identifier sid, or 0 otherwise) are publicly known. Note that the authors claim that each tag 𝒯 has its output bit o𝒯sid=0 if the authentication protocol is not mutual. However, we consider this fact too limiting since 𝒯 can have an output (possibly known by 𝒜), even if it may not authenticate the reader. For instance, its output can be “I arrived correctly at the end of the protocol on my side.”DLYZ assumes that a tag may participate to at mosts executions in its life with ℛ; thus ℛ is involved in at most sn executions, where s is polynomial in λ and n is the total number of tags involved in the system.


## 9.2. Oracles

In a nutshell, DLYZ aims to analyze protocols where entities’ secrets may potentially be updated at every protocol execution. Therefore, the model automatically enumerates the internal information of each entity. At the initialization of the system, the database is in an initial state, calledDB0, and already stores the secrets of all the tags, that is, a SetupTag has already been performed on every tag. The only differences in the initialization are the following: (i)
SetupReader additionally generates ℛ’s initial internal state sℛ0;(ii)
SetupTag associates to every tag 𝒯 a triplet (ξ𝒯,k𝒯0,s𝒯0), which is, respectively, 𝒯’s public parameter, initial secret key, and initial internal state.This information is stored inDB0. Finally, let param=(KP,{ξ𝒯}∀𝒯) denote the public parameters of the system 𝒮. At the end of the system’s initialization, all the tags are accessible to the adversary.Then,𝒜 has access to the following modified generic oracles. (i)
Launch()→(π,m) makes ℛ launch a new protocol execution π and generates the 1st-round message m which is also used as the execution identifier sid. If this is the jth new execution run by ℛ, then ℛ stores η1=m into its internal state sℛj.(ii)
SendTag(m,𝒯)→r sends m to 𝒯. The output response r of 𝒯 is as follows.
(1)
If𝒯 currently does not run any execution, then 𝒯
(a)
initiates a new execution with identifiersid=m,(b)
treatsm as the 1st-round message of the new execution,(c)
and returns the2nd-round message (sid,r=α1).(2)
If𝒯 is currently running an incomplete execution with identifier sid and is waiting for the uth message from ℛ (u≥2), then 𝒯 works as follows:
(a)
if2≤u≤γ, 𝒯 treats m as the uth message from ℛ and returns the next round message (sid,r=αu);(b)
ifu=γ+1 (i.e., the last-round message of the execution), 𝒯 returns its output o𝒯sid and updates its internal state to s𝒯v+1 (where sid corresponds to the vth execution run by 𝒯, where 1≤v≤s).(iii)
SendReader(m,sid)→r sends m to ℛ for the execution with identifier sid. After receiving m, ℛ checks from its internal state whether it is running such an execution, and ℛ’s response r is as follows.
(1)
Ifℛ is currently running an incomplete execution with identifier sid and is waiting for the uth message from a tag (1≤u≤γ), then ℛ works as follows:
(a)
ifu≤γ, ℛ treats m as the uth message from the tag and returns the next round message r=ηu+1;(b)
ifu=γ, ℛ returns the last-round message r=ηγ+1 and its output oℛsid and updates its internal state to sℛj+1 and the database DBj+1 (where sid corresponds to the jth execution run by ℛ).(2)
In all the other cases,ℛ returns ⊥ (for invalid queries).(iv)
Corrupt(𝒯)→(k𝒯v,s𝒯v) returns the secret key k𝒯v and the internal state s𝒯v currently held by 𝒯. Once 𝒯 is corrupted, all its actions are controlled and performed by 𝒜.For a completed protocol execution with identifiersid, the transcript of the exchanged messages is (sid,η1sid,α1sid,…,αγsid,ηγ+1sid), excluding the entities’ outputs.Let𝒪 denote the set of these four oracles. 𝒜𝒪(ℛ,T,param) denotes a PPT adversary 𝒜 that takes on input the system public parameters param, the reader ℛ, and the tags set T of the already initialized system. Then 𝒜 interacts with ℛ and the tags of T via the four oracles. 𝒜′𝒪(ℛ,T^,ℐ(𝒯c),aux) denotes a PPT adversary 𝒜′ equivalent to 𝒜, where aux∈{0,1}* generally includes param or some historical state information of 𝒜′. Then 𝒜′ interacts with ℛ and the tags set T^ via the four oracles. 𝒜′ is said to have a blinded access to a challenge tag 𝒯c∉T^ if it interacts with 𝒯c via a special interface ℐ (i.e., a PPT algorithm which runs 𝒯c internally and interacts with 𝒜′ externally). To send a message m to 𝒯c, 𝒜′ sends a SendTag(m,challenge) to ℐ; then ℐ invokes 𝒯c with SendTag(m,𝒯c) and answers 𝒯c’s output to 𝒜′. 𝒜′ does not know which tag is interacting with it. 𝒜′ interacts with 𝒯c via SendTag queries only.Definition 15 (clean tag [12]).
A tag𝒯 is said to be clean if it is not corrupted (i.e., no query to Corrupt on 𝒯) and is not currently running an incomplete execution with ℛ (i.e., 𝒯’s last execution is either finished or aborted).The main goal of this definition is to force the adversary to use some uncorrupted and nonrunning tags to proceed theZK-privacy experiment (see next section). This notion of nonrunning tags is very similar to the TagInit oracle of JW.


## 9.3. Privacy Experiments

In the experiments, a PPT CMIM (concurrent man-in-the-middle) adversary𝒜 (resp., PPT simulator Sim) is composed of a pair of adversaries (𝒜1,𝒜2) (resp., (Sim1,Sim2)) and runs in two stages. Note that, if δ=0, then no challenge tag is selected, and 𝒜 is reduced to 𝒜1 in the experiment.The first experiment given in Box7 is the one performed by the real adversary 𝒜. After the system initialization, 𝒜1 plays with all the entities and returns a set of clean tags C. Then from this set C, a challenge tag 𝒯c is chosen at random. Then 𝒜2 plays with all the entities, including the challenge tag via the interface ℐ, except the set of clean tags. At the end, 𝒜 outputs a view of the system.Box 7
ExperimentExp𝒮,𝒜ZK-priv[λ,n]                               (real world)
(1)𝒞 initializes the system and sends 1λ, param to 𝒜.
(2){C,info}←𝒜1𝒪(ℛ,T,param), where C={𝒯i1,𝒯i2,…,𝒯iδ}⊆T is a set of clean tags
(0≤δ≤n), and info is a state information.
(3)c∈R{1,…,δ}, set 𝒯c=𝒯ic and T^=T-C.
(4)view𝒜←𝒜2𝒪(ℛ,T^,ℐ(𝒯c),info).
(5)  Output(c,view𝒜(λ,n)).Then, the second experiment given in Box8 is the one performed by the simulator Sim. As in the previous experiment, Sim1 plays with all the entities and returns a set of clean tags C. Then from this set C, a challenge tag 𝒯c is chosen at random, but Sim is not informed about its identity and cannot play anymore with this tag. Then Sim2 plays with all the entities, except the set of clean tags. At the end, Sim outputs a simulated view of the system.Box 8
ExperimentExp𝒮,SimZK-priv[λ,n]                                 (simulated world)
(1)𝒞 initializes the system and sends 1λ, param to 𝒜.
(2){C,  info}←Sim1𝒪(ℛ,T,param), where C={𝒯i1,𝒯i2,…,𝒯iδ}⊆T is a set of clean tags (0≤δ≤n),
andinfo is a state information.
(3)c∈R{1,…,δ} unknown to Sim, and set T^=T-C.
(4)sview←Sim2𝒪(ℛ,T^,  info), where sview includes all oracle answers to queries made by Sim.
(5) Output(c,sview(λ,n)).


## 9.4. Privacy Notions

From the previous experiments, theZK-privacy of a system 𝒮 is proved when no one is able to distinguish if it is interacting with the real world or with the simulated one.Definition 16 (ZK-privacy [12]).
An RFID system𝒮 satisfies computational (resp., statistical) ZK-privacy if, for any PPT CMIM adversary 𝒜, there exists a polynomial-time simulator Sim such that, for all sufficiently large λ and any n which is polynomial in λ, the following ensembles are computationally (resp., statistically) indistinguishable: (i)
{c,view𝒜(λ,n)}λ∈ℕ,n∈poly(λ),(ii)
{c,sview(λ,n)}λ∈ℕ,n∈poly(λ).
That is, for any polynomial-time (resp., any computationally power unlimited) algorithm𝒟, it holds that
(10)|Pr[𝒟(λ,n,c,view𝒜(λ,n))=1]-Pr[𝒟(λ,n,c,sview(λ,n))=1]|=ϵ(λ).The probability is taken over the random coins used during the system initialization, the random coins used by𝒜, Sim, ℛ, and all (uncorrupted) tags, the choice of c, and the coins used by the distinguisher algorithm 𝒟.Definition 17 (Forward/Backward-ZK-privacy [12]).
Let us denote(k𝒯cfinal,s𝒯cfinal) (resp., (k𝒯c0,s𝒯c0)) the final (resp., initial) secret key and internal state of the challenge tag 𝒯c at the end (resp., beginning) of Exp𝒮,𝒜ZK-priv. An RFID system 𝒮 is forward (resp., backward)-ZK-private if, for any PPT CMIM adversary 𝒜, there exists a polynomial-time simulator Sim such that, for all sufficiently large λ and any n which is polynomial in λ, the following distributions are indistinguishable: (i)
{k𝒯cfinal,s𝒯cfinal(resp.,k𝒯c0,s𝒯c0),c,view𝒜(λ,n)},(ii)
{k𝒯cfinal,s𝒯cfinal(resp.,k𝒯c0,s𝒯c0),c,sview(λ,n)}.
It is required that𝒯c should remain clean at the end of Exp𝒮,𝒜ZK-priv. Note that 𝒜 is allowed to corrupt it after the end of Exp𝒮,𝒜ZK-priv.One justification of the authors on the way of corrupting𝒯c is that it is enough to give its secrets to 𝒜 at the end. Another reason pointed out by the authors is that forward-ZK or backward-ZK-privacy cannot be achieved if 𝒜 corrupts 𝒯c before the end of the experiment.


## 10. Hermans et al. [15], 2011

Following the path opened by Vaudenay with his privacy model, Hermans et al. presented in 2011 a new model, denoted here HPVP, based on indistinguishability between two “worlds”: it is most commonly called the “left-or-right” paradigm.The main goal of the authors was to propose a model with a clear defined purpose, that is straightforward to use for proving privacy. Also as CCEG, HPVP aimed to use Vaudenay’s strongest adversary.


### 10.1. Oracles

As for Vaudenay and CCEG,DB is empty after the initialization of the system, and a tag can be either free or drawn. Then 𝒜 has access to the generic oracles CreateTag (here it additionally returns a reference 𝒯 to the new created tag), SendReader, and Result. Then, 𝒜 has also access to these other following oracles. (i)
DrawTag(𝒯i,𝒯j)→𝒯drawn generates a drawn tag 𝒯drawn and stores (𝒯drawn,𝒯i,𝒯j) in a table Tab. Depending on the bit b chosen at the start of the privacy experiment (see next section), 𝒯drawn will either reference 𝒯i or 𝒯j. If one of the two tags (𝒯i,𝒯j) is already referenced in Tab, then it outputs ⊥.(ii)
Freeb(𝒯drawn) recovers the tuple (𝒯drawn,𝒯i,𝒯j) in Tab. If b=0 then it resets 𝒯i, otherwise it resets 𝒯j. Then it removes the tuple from Tab. When a tag is reset, its volatile memory is erased, not its nonvolatile memory (which contains its secret k𝒯).This specific definition of the Free oracle comes from one important statement highlighted by Paise and Vaudenay in their model (see Section  5.4 for more details).Finally𝒜 has access to the following modified generic oracles. (i)
Launch()→(π,m) makes ℛ launch a new Ident protocol execution π, together with ℛ’s first message m.(ii)
SendTag(m,𝒯)→r retrieves the tuple (𝒯,𝒯i,𝒯j) in Tab. It sends a message m to the corresponding tag (𝒯i if b=0, 𝒯j otherwise). It outputs the response r of the tag. If 𝒯 is not found in Tab, it returns ⊥.(iii)
Corrupt(𝒯)→k𝒯 returns the whole memory (including the current secret k𝒯) of 𝒯. If 𝒯 is drawn, it returns ⊥.All these oracles are very similar to the ones of Vaudenay, but with important differences. First, DrawTag is only applied on two tags chosen by the adversary when it queries this oracle. Then, Free specifies clearly that it erases the volatile memory of the chosen tag. Lastly, Corrupt is only authorized on afree tag. However, the intrinsic definition of a free tag (given in the Vaudenay model [22]) is that it is not accessible to 𝒜, since it is not in its neighborhood. Thus, it seems impossible for 𝒜 to query a Corrupt on a tag that it cannot manipulate (i.e., not drawn).


### 10.2. Privacy Experiment

The authors keep the same adversary classes as the ones given by Vaudenay:STRONG, DESTRUCTIVE, FORWARD, WEAK, and NARROW.Their privacy experiment is given in Box9, where P represents the adversary class: P∈{∅,NARROW}×{WEAK,FORWARD, DESTRUCTIVE,STRONG}.Box 9
ExperimentExp𝒮,𝒜HPVP-priv[λ,b]
(1)𝒞 initializes the system, chooses a random bit b, and sends 1λ and 𝒮's public parameters param to 𝒜.
(2)𝒜 interacts with the whole system, limited by its class 𝒫.
(3)𝒜 outputs a guess bit b'.
Exp
𝒮
,
𝒜
H
P
V
P
-
p
r
i
v succeeds if b=b'.


### 10.3. Privacy Notions

From the previous experiment, the HPVP privacy property is based on the adversary advantage to distinguish the two worlds.Definition 18 (privacy [15]).
The RFID system𝒮 is said to unconditionally (resp., computationally) provide P-privacy if and only if, for all the adversaries (resp., polynomial time adversaries) which belong to class P, it holds that
(11)|Pr(Exp𝒮,𝒜HPVP-Priv[λ,0]succeeds)+Pr(Exp𝒮,𝒜HPVP-Priv[λ,1]succeeds)-1|=0(resp.≤ϵ(λ)).Note that, all along the paper, the authors claim that the already existing models do not take care about some privacy leakage information such as the cardinality of the tags’ set. Yet, they never prove nor explain how their model can handle this issue, nor why this is indeed a privacy issue.


## 10.1. Oracles

As for Vaudenay and CCEG,DB is empty after the initialization of the system, and a tag can be either free or drawn. Then 𝒜 has access to the generic oracles CreateTag (here it additionally returns a reference 𝒯 to the new created tag), SendReader, and Result. Then, 𝒜 has also access to these other following oracles. (i)
DrawTag(𝒯i,𝒯j)→𝒯drawn generates a drawn tag 𝒯drawn and stores (𝒯drawn,𝒯i,𝒯j) in a table Tab. Depending on the bit b chosen at the start of the privacy experiment (see next section), 𝒯drawn will either reference 𝒯i or 𝒯j. If one of the two tags (𝒯i,𝒯j) is already referenced in Tab, then it outputs ⊥.(ii)
Freeb(𝒯drawn) recovers the tuple (𝒯drawn,𝒯i,𝒯j) in Tab. If b=0 then it resets 𝒯i, otherwise it resets 𝒯j. Then it removes the tuple from Tab. When a tag is reset, its volatile memory is erased, not its nonvolatile memory (which contains its secret k𝒯).This specific definition of the Free oracle comes from one important statement highlighted by Paise and Vaudenay in their model (see Section  5.4 for more details).Finally𝒜 has access to the following modified generic oracles. (i)
Launch()→(π,m) makes ℛ launch a new Ident protocol execution π, together with ℛ’s first message m.(ii)
SendTag(m,𝒯)→r retrieves the tuple (𝒯,𝒯i,𝒯j) in Tab. It sends a message m to the corresponding tag (𝒯i if b=0, 𝒯j otherwise). It outputs the response r of the tag. If 𝒯 is not found in Tab, it returns ⊥.(iii)
Corrupt(𝒯)→k𝒯 returns the whole memory (including the current secret k𝒯) of 𝒯. If 𝒯 is drawn, it returns ⊥.All these oracles are very similar to the ones of Vaudenay, but with important differences. First, DrawTag is only applied on two tags chosen by the adversary when it queries this oracle. Then, Free specifies clearly that it erases the volatile memory of the chosen tag. Lastly, Corrupt is only authorized on afree tag. However, the intrinsic definition of a free tag (given in the Vaudenay model [22]) is that it is not accessible to 𝒜, since it is not in its neighborhood. Thus, it seems impossible for 𝒜 to query a Corrupt on a tag that it cannot manipulate (i.e., not drawn).


## 10.2. Privacy Experiment

The authors keep the same adversary classes as the ones given by Vaudenay:STRONG, DESTRUCTIVE, FORWARD, WEAK, and NARROW.Their privacy experiment is given in Box9, where P represents the adversary class: P∈{∅,NARROW}×{WEAK,FORWARD, DESTRUCTIVE,STRONG}.Box 9
ExperimentExp𝒮,𝒜HPVP-priv[λ,b]
(1)𝒞 initializes the system, chooses a random bit b, and sends 1λ and 𝒮's public parameters param to 𝒜.
(2)𝒜 interacts with the whole system, limited by its class 𝒫.
(3)𝒜 outputs a guess bit b'.
Exp
𝒮
,
𝒜
H
P
V
P
-
p
r
i
v succeeds if b=b'.


## 10.3. Privacy Notions

From the previous experiment, the HPVP privacy property is based on the adversary advantage to distinguish the two worlds.Definition 18 (privacy [15]).
The RFID system𝒮 is said to unconditionally (resp., computationally) provide P-privacy if and only if, for all the adversaries (resp., polynomial time adversaries) which belong to class P, it holds that
(11)|Pr(Exp𝒮,𝒜HPVP-Priv[λ,0]succeeds)+Pr(Exp𝒮,𝒜HPVP-Priv[λ,1]succeeds)-1|=0(resp.≤ϵ(λ)).Note that, all along the paper, the authors claim that the already existing models do not take care about some privacy leakage information such as the cardinality of the tags’ set. Yet, they never prove nor explain how their model can handle this issue, nor why this is indeed a privacy issue.


## 11. Privacy Analysis of Different ExistingProtocols

To investigate more deeply the differences between the presented models, we study the privacy level of five different protocols in all these models. These protocols differ according to their building blocks and their underlying key infrastructure. The first protocol [37] is based on unique long-term secret key for each tag. On the contrary in the tree-based protocol [8], tags share between them some long-term partial secret keys so as to speed up the authentication. Two protocols [18, 38] use key-update mechanisms to increase the privacy level in case of tag corruption. In particular, the second one [18] provides mutual authentication in order to be undesynchronizable. The last analyzed protocol [22] is based on public-key cryptography. Due to their differences, these protocols may thus ensure different privacy levels. However, we will show in this section that some models assign the same privacy level to some protocols while other models clearly differentiate them, for example, by taking into account an attack which cannot be modeled in other models.In the following, a tag𝒯 has a unique identifier ID𝒯 and should be authenticated by a legitimate reader ℛ.


### 11.1. Analyzed Protocols

The five RFID protocols chosen for this study are sketched in the following. Their complete descriptions and whole privacy analyses are detailed in AppendixB.


#### 11.1.1. SK-Based Challenge/Response Authentication Protocol

The first studied protocol is the ISO/IEC 9798-2 Mechanism 2 [37] based on a PRF with an additional nonce chosen by the tag. A tag 𝒯 has a unique secret key k𝒯 known by ℛ, used for the authentication. All the tags’ keys are independent.


#### 11.1.2. Tree-Based Authentication Protocol

It is based on the key-tree infrastructure given by Molnar and Wagner in [8]. Basically in a system of n tags, a key-tree is generated with βd≥n leaves, where d is its depth and β is its branching factor. Each leaf is randomly associated to a tag 𝒯 of the system, and each node is associated to a partial unique secret key ki,j where i is the depth of the node and j the branch.We define w.l.o.g.(p0,p1,p2,…,pd) the path in the tree from the root (denoted p0) to the leaf (denoted pd) that is associated to the tag 𝒯. At the setup of the system, 𝒯 is initialized with a set of partial keys {kp1,kp2,…,kpd}, where each kpi is the secret key attached to its path node pi (except the root). ℛ knows the entire tree arrangement, and thus all the keys associated to all the nodes.The protocol is carried out ind rounds. For each round, ℛ and 𝒯 perform a challenge/response authentication as described in Figure 2 of Appendix  B.2. If 𝒯 answers correctly at each round, then ℛ successfully authenticates 𝒯 at the end of the last round.


#### 11.1.3. OSK-Based Authentication Protocol

The original OSK protocol [38] is an identification protocol, where there is no proof of the tag identity. At the setup, 𝒯 is initialized with a unique secret key k𝒯 shared with ℛ. All the tags’ keys are independent. 𝒯 just sends the result of a pseudorandom function done on its key. The main feature of OSK is that 𝒯 and ℛ update the shared key after each complete protocol execution.The OSK protocol has been introduced to ensure theforward security property, that is, data sent by a given tag 𝒯 today will still be secure even if 𝒯’s secret is disclosed by tampering this tag in the future, contrary to the SK-based protocol. The protocol presented here (proposed in [22]) is slightly different from OSK as ℛ additionally sends a nonce to 𝒯 in order to prevent replay attacks, as described in [6]. The resulting protocol ensures tag authentication rather than tag identification.


#### 11.1.4. O-FRAP Authentication Protocol

Many undesynchronizable authentication protocols [18, 24, 39] have been proposed to counter the main drawback of OSK, that is the desynchronization attack. Here, we analyze O-FRAP, introduced by van Le et al. in [18].At the setup,𝒯 is initialized with a couple containing a secret key and a nonce (k𝒯,n𝒯), such that all the couples of tags are independent. (k𝒯,n𝒯) is stored by ℛ as the current secrets cur𝒯 of 𝒯. Then a mutual authentication between ℛ and 𝒯 is performed, where 𝒯’s key and/or nonce are updated at the end of the protocol execution by both entities. The main difference with OSK is that the tag always updates at least one value, even when the protocol is incomplete (in this case the random n𝒯).


#### 11.1.5. PK-Based Challenge/Response Authentication Protocol

It is one of the protocols given by Vaudenay in [22]. ℛ has a pair of public/private keys (KP,KS), and a tag 𝒯 has a unique secret key k𝒯 known by ℛ. All the tags’ keys are independent. The encryption scheme (Enc/Dec) is considered to be either IND-CPA (indistinguishable under chosen-plaintext attack) or IND-CCA (indistinguishable under chosen-ciphertext attack) secure.


### 11.2. Analysis Comparison

Table1 sums up the security analysis of the studied protocols regarding each privacy model.Table 1
Analysis summary of the protocols. “✗” means no privacy. For the PK-based protocol, a property followed by “*” means that it is at least achieved with IND-CPA-security. For the sake of clarity, we denote “N” and “DESTR” as being, respectively, “NARROW” and “DESTRUCTIVE.”
Model
Protocol
SK based [37]
Tree based [8]
OSK based [22]
O FRAP [18]
PK based [22]
Avoine
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE*
F
o
r
w
a
r
d
-
U
N
T
-RTEC
F
o
r
w
a
r
d
-
U
N
T
-RTEC
F
o
r
w
a
r
d
-
U
N
T
-RTEC*
JW
(
ρ
,
σ
,
τ
)-privacy
✗
✗
(
ρ
,
σ
,
τ
)-privacy
F
o
r
w
a
r
d
-
(
ρ
,
σ
,
τ
)-privacy
Vaudenay
W
E
A
K
-privacy
W
E
A
K
-privacy
N
-
D
E
S
T
R
-privacy
W
E
A
K
-privacy
N
-
S
T
R
O
N
G
-privacy*
F
O
R
W
A
D
-privacy
LBM
✗
✗
✗
F
o
r
w
a
r
d
-security
F
o
r
w
a
r
d
-security
DMR
Untraceability
✗
Untraceability
Untraceability
Untraceability*
CCEG
S
t
a
n
d
a
r
d
-untraceability
S
t
a
n
d
a
r
d
-untraceability
✗
S
t
a
n
d
a
r
d
-untraceability
F
u
t
u
r
e
-untraceability
DLYZ
Z
K
-privacy
✗
✗
Z
K
-privacy
B
a
c
k
w
a
r
d
-
Z
K
-privacy
HPVP
W
E
A
K
-privacy
W
E
A
K
-privacy
N
-
D
E
S
T
R
-privacy
W
E
A
K
-privacy
N
-
S
T
R
O
N
G
-privacy*
S
T
R
O
N
G
-privacy


#### 11.2.1. The Lack of Comprehensiveness

In some models, several protocols are proved to ensure the same privacy level, because some attacks on these protocols cannot be formalized. For example in the Avoine model, OSK-based, O-FRAP, and PK-based protocols reach the same privacy (i.e.,Existential-UNT-RTE and Forward-UNT-RTEC). However as detailed in Appendix  B.3, the OSK-based protocol can be desynchronized contrary to the other two, and O-FRAP is subject to a specific attack based on tag corruption (see Appendix  B.4), while the PK-based protocol is not vulnerable to such attacks. This misevaluation of privacy happens in almost all models (e.g., {SK-based, tree-based, O-FRAP} for Vaudenay, CCEG, and HPVP, or {SK-based, OSK-based, O-FRAP} for DMR). The main drawback of this fact is that system designers unfamiliar with privacy will probably choose the cheapest protocol (regarding the computing complexity), thinking that these protocols are equivalent regarding their privacy level.


#### 11.2.2. The Case of Correlated Secrets

Nevertheless, some models have features that permit attributing different privacy levels to quite similar protocols. As an example, JW, DMR, and DLYZ point out an important characteristic of protocols based on correlated secrets: they prove that the tree-based protocol is not secure, while the SK-based one is. This comes from the fact that an adversary may know some secrets without being authorized to corrupt the challenge tags (as explained in Appendix  B.2). For instance, this adversary could be a tag owner that only knows its tags’ secrets and that is not able to corrupt other tags that it wants to trace. It is consequently normal that the SK-based protocol is more private than the tree-based one. Note that this differentiation cannot be established in the Avoine, Vaudenay, CCEG, and HPVP models because their adversary does not have the modularity to only corrupt certain tags. As a consequence, these models classify the SK-based and the tree-based protocols with the same privacy level.


#### 11.2.3. The Key-Update Mechanism Dilemma

All the models (except Avoine and LBM) give the same privacy level for the SK-based protocol and for O-FRAP. This is another obvious example about the issue related to the privacy definitions of these models. Indeed, the two protocols do not manage the tags’ secrets in the same way: a tag updates one of its secrets each time it starts an execution of O-FRAP, while a tag always keeps the same secret when it runs the SK-based protocol. For O-FRAP, the attack presented in Appendix  B.4 only permits linking a freshly corrupted tag to its last previous incomplete protocol execution. But all the previous completed ones are unlinkable. This is not the case with the SK-based protocol, where a tag corruption allows tracing the tag at any time (past or future). This obvious distinction of the two protocols is however not highlighted by most of the models.


#### 11.2.4. Accuracy Refinement of theNARROW Adversary

TheNARROW nuance provided in some models permits granting some protocols with a reasonable privacy level. For instance, Vaudenay and HPVP confer NARROW-DESTRUCTIVE-privacy on the OSK-based protocol and NARROW-STRONG-privacy on the IND-CPA-PK-based protocol, while some other models argue that the OSK-based protocol ensures no privacy at all or that the IND-CPA-PK-based protocol cannot be proved private. These last claims are highly restrictive since these two protocols are clearly more private than the dummy identification protocol where tags send their identifier in the clear.


#### 11.2.5. The Vaudenay Problem

Finally, Vaudenay proved in [22] that the highest privacy level of his model cannot be achieved. Yet, the highest privacy level of all the other seven presented models can be reached, at least with the IND-CCA-PK-based protocol. To the best of our knowledge, Ouafi is the only author who tries to explain in [20] that the Vaudenay model (i) does not reflect the exact notion of privacy that was targeted at first sight and (ii) may englobe more than only privacy. As explained in Section  5.4, Ouafi reformulates the Vaudenay model in order to achieve STRONG-privacy.


## 11.1. Analyzed Protocols

The five RFID protocols chosen for this study are sketched in the following. Their complete descriptions and whole privacy analyses are detailed in AppendixB.


### 11.1.1. SK-Based Challenge/Response Authentication Protocol

The first studied protocol is the ISO/IEC 9798-2 Mechanism 2 [37] based on a PRF with an additional nonce chosen by the tag. A tag 𝒯 has a unique secret key k𝒯 known by ℛ, used for the authentication. All the tags’ keys are independent.


### 11.1.2. Tree-Based Authentication Protocol

It is based on the key-tree infrastructure given by Molnar and Wagner in [8]. Basically in a system of n tags, a key-tree is generated with βd≥n leaves, where d is its depth and β is its branching factor. Each leaf is randomly associated to a tag 𝒯 of the system, and each node is associated to a partial unique secret key ki,j where i is the depth of the node and j the branch.We define w.l.o.g.(p0,p1,p2,…,pd) the path in the tree from the root (denoted p0) to the leaf (denoted pd) that is associated to the tag 𝒯. At the setup of the system, 𝒯 is initialized with a set of partial keys {kp1,kp2,…,kpd}, where each kpi is the secret key attached to its path node pi (except the root). ℛ knows the entire tree arrangement, and thus all the keys associated to all the nodes.The protocol is carried out ind rounds. For each round, ℛ and 𝒯 perform a challenge/response authentication as described in Figure 2 of Appendix  B.2. If 𝒯 answers correctly at each round, then ℛ successfully authenticates 𝒯 at the end of the last round.


### 11.1.3. OSK-Based Authentication Protocol

The original OSK protocol [38] is an identification protocol, where there is no proof of the tag identity. At the setup, 𝒯 is initialized with a unique secret key k𝒯 shared with ℛ. All the tags’ keys are independent. 𝒯 just sends the result of a pseudorandom function done on its key. The main feature of OSK is that 𝒯 and ℛ update the shared key after each complete protocol execution.The OSK protocol has been introduced to ensure theforward security property, that is, data sent by a given tag 𝒯 today will still be secure even if 𝒯’s secret is disclosed by tampering this tag in the future, contrary to the SK-based protocol. The protocol presented here (proposed in [22]) is slightly different from OSK as ℛ additionally sends a nonce to 𝒯 in order to prevent replay attacks, as described in [6]. The resulting protocol ensures tag authentication rather than tag identification.


### 11.1.4. O-FRAP Authentication Protocol

Many undesynchronizable authentication protocols [18, 24, 39] have been proposed to counter the main drawback of OSK, that is the desynchronization attack. Here, we analyze O-FRAP, introduced by van Le et al. in [18].At the setup,𝒯 is initialized with a couple containing a secret key and a nonce (k𝒯,n𝒯), such that all the couples of tags are independent. (k𝒯,n𝒯) is stored by ℛ as the current secrets cur𝒯 of 𝒯. Then a mutual authentication between ℛ and 𝒯 is performed, where 𝒯’s key and/or nonce are updated at the end of the protocol execution by both entities. The main difference with OSK is that the tag always updates at least one value, even when the protocol is incomplete (in this case the random n𝒯).


### 11.1.5. PK-Based Challenge/Response Authentication Protocol

It is one of the protocols given by Vaudenay in [22]. ℛ has a pair of public/private keys (KP,KS), and a tag 𝒯 has a unique secret key k𝒯 known by ℛ. All the tags’ keys are independent. The encryption scheme (Enc/Dec) is considered to be either IND-CPA (indistinguishable under chosen-plaintext attack) or IND-CCA (indistinguishable under chosen-ciphertext attack) secure.


## 11.1.1. SK-Based Challenge/Response Authentication Protocol

The first studied protocol is the ISO/IEC 9798-2 Mechanism 2 [37] based on a PRF with an additional nonce chosen by the tag. A tag 𝒯 has a unique secret key k𝒯 known by ℛ, used for the authentication. All the tags’ keys are independent.


## 11.1.2. Tree-Based Authentication Protocol

It is based on the key-tree infrastructure given by Molnar and Wagner in [8]. Basically in a system of n tags, a key-tree is generated with βd≥n leaves, where d is its depth and β is its branching factor. Each leaf is randomly associated to a tag 𝒯 of the system, and each node is associated to a partial unique secret key ki,j where i is the depth of the node and j the branch.We define w.l.o.g.(p0,p1,p2,…,pd) the path in the tree from the root (denoted p0) to the leaf (denoted pd) that is associated to the tag 𝒯. At the setup of the system, 𝒯 is initialized with a set of partial keys {kp1,kp2,…,kpd}, where each kpi is the secret key attached to its path node pi (except the root). ℛ knows the entire tree arrangement, and thus all the keys associated to all the nodes.The protocol is carried out ind rounds. For each round, ℛ and 𝒯 perform a challenge/response authentication as described in Figure 2 of Appendix  B.2. If 𝒯 answers correctly at each round, then ℛ successfully authenticates 𝒯 at the end of the last round.


## 11.1.3. OSK-Based Authentication Protocol

The original OSK protocol [38] is an identification protocol, where there is no proof of the tag identity. At the setup, 𝒯 is initialized with a unique secret key k𝒯 shared with ℛ. All the tags’ keys are independent. 𝒯 just sends the result of a pseudorandom function done on its key. The main feature of OSK is that 𝒯 and ℛ update the shared key after each complete protocol execution.The OSK protocol has been introduced to ensure theforward security property, that is, data sent by a given tag 𝒯 today will still be secure even if 𝒯’s secret is disclosed by tampering this tag in the future, contrary to the SK-based protocol. The protocol presented here (proposed in [22]) is slightly different from OSK as ℛ additionally sends a nonce to 𝒯 in order to prevent replay attacks, as described in [6]. The resulting protocol ensures tag authentication rather than tag identification.


## 11.1.4. O-FRAP Authentication Protocol

Many undesynchronizable authentication protocols [18, 24, 39] have been proposed to counter the main drawback of OSK, that is the desynchronization attack. Here, we analyze O-FRAP, introduced by van Le et al. in [18].At the setup,𝒯 is initialized with a couple containing a secret key and a nonce (k𝒯,n𝒯), such that all the couples of tags are independent. (k𝒯,n𝒯) is stored by ℛ as the current secrets cur𝒯 of 𝒯. Then a mutual authentication between ℛ and 𝒯 is performed, where 𝒯’s key and/or nonce are updated at the end of the protocol execution by both entities. The main difference with OSK is that the tag always updates at least one value, even when the protocol is incomplete (in this case the random n𝒯).


## 11.1.5. PK-Based Challenge/Response Authentication Protocol

It is one of the protocols given by Vaudenay in [22]. ℛ has a pair of public/private keys (KP,KS), and a tag 𝒯 has a unique secret key k𝒯 known by ℛ. All the tags’ keys are independent. The encryption scheme (Enc/Dec) is considered to be either IND-CPA (indistinguishable under chosen-plaintext attack) or IND-CCA (indistinguishable under chosen-ciphertext attack) secure.


## 11.2. Analysis Comparison

Table1 sums up the security analysis of the studied protocols regarding each privacy model.Table 1
Analysis summary of the protocols. “✗” means no privacy. For the PK-based protocol, a property followed by “*” means that it is at least achieved with IND-CPA-security. For the sake of clarity, we denote “N” and “DESTR” as being, respectively, “NARROW” and “DESTRUCTIVE.”
Model
Protocol
SK based [37]
Tree based [8]
OSK based [22]
O FRAP [18]
PK based [22]
Avoine
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE
E
x
i
s
t
e
n
t
i
a
l
-
U
N
T
-RTE*
F
o
r
w
a
r
d
-
U
N
T
-RTEC
F
o
r
w
a
r
d
-
U
N
T
-RTEC
F
o
r
w
a
r
d
-
U
N
T
-RTEC*
JW
(
ρ
,
σ
,
τ
)-privacy
✗
✗
(
ρ
,
σ
,
τ
)-privacy
F
o
r
w
a
r
d
-
(
ρ
,
σ
,
τ
)-privacy
Vaudenay
W
E
A
K
-privacy
W
E
A
K
-privacy
N
-
D
E
S
T
R
-privacy
W
E
A
K
-privacy
N
-
S
T
R
O
N
G
-privacy*
F
O
R
W
A
D
-privacy
LBM
✗
✗
✗
F
o
r
w
a
r
d
-security
F
o
r
w
a
r
d
-security
DMR
Untraceability
✗
Untraceability
Untraceability
Untraceability*
CCEG
S
t
a
n
d
a
r
d
-untraceability
S
t
a
n
d
a
r
d
-untraceability
✗
S
t
a
n
d
a
r
d
-untraceability
F
u
t
u
r
e
-untraceability
DLYZ
Z
K
-privacy
✗
✗
Z
K
-privacy
B
a
c
k
w
a
r
d
-
Z
K
-privacy
HPVP
W
E
A
K
-privacy
W
E
A
K
-privacy
N
-
D
E
S
T
R
-privacy
W
E
A
K
-privacy
N
-
S
T
R
O
N
G
-privacy*
S
T
R
O
N
G
-privacy


### 11.2.1. The Lack of Comprehensiveness

In some models, several protocols are proved to ensure the same privacy level, because some attacks on these protocols cannot be formalized. For example in the Avoine model, OSK-based, O-FRAP, and PK-based protocols reach the same privacy (i.e.,Existential-UNT-RTE and Forward-UNT-RTEC). However as detailed in Appendix  B.3, the OSK-based protocol can be desynchronized contrary to the other two, and O-FRAP is subject to a specific attack based on tag corruption (see Appendix  B.4), while the PK-based protocol is not vulnerable to such attacks. This misevaluation of privacy happens in almost all models (e.g., {SK-based, tree-based, O-FRAP} for Vaudenay, CCEG, and HPVP, or {SK-based, OSK-based, O-FRAP} for DMR). The main drawback of this fact is that system designers unfamiliar with privacy will probably choose the cheapest protocol (regarding the computing complexity), thinking that these protocols are equivalent regarding their privacy level.


### 11.2.2. The Case of Correlated Secrets

Nevertheless, some models have features that permit attributing different privacy levels to quite similar protocols. As an example, JW, DMR, and DLYZ point out an important characteristic of protocols based on correlated secrets: they prove that the tree-based protocol is not secure, while the SK-based one is. This comes from the fact that an adversary may know some secrets without being authorized to corrupt the challenge tags (as explained in Appendix  B.2). For instance, this adversary could be a tag owner that only knows its tags’ secrets and that is not able to corrupt other tags that it wants to trace. It is consequently normal that the SK-based protocol is more private than the tree-based one. Note that this differentiation cannot be established in the Avoine, Vaudenay, CCEG, and HPVP models because their adversary does not have the modularity to only corrupt certain tags. As a consequence, these models classify the SK-based and the tree-based protocols with the same privacy level.


### 11.2.3. The Key-Update Mechanism Dilemma

All the models (except Avoine and LBM) give the same privacy level for the SK-based protocol and for O-FRAP. This is another obvious example about the issue related to the privacy definitions of these models. Indeed, the two protocols do not manage the tags’ secrets in the same way: a tag updates one of its secrets each time it starts an execution of O-FRAP, while a tag always keeps the same secret when it runs the SK-based protocol. For O-FRAP, the attack presented in Appendix  B.4 only permits linking a freshly corrupted tag to its last previous incomplete protocol execution. But all the previous completed ones are unlinkable. This is not the case with the SK-based protocol, where a tag corruption allows tracing the tag at any time (past or future). This obvious distinction of the two protocols is however not highlighted by most of the models.


### 11.2.4. Accuracy Refinement of theNARROW Adversary

TheNARROW nuance provided in some models permits granting some protocols with a reasonable privacy level. For instance, Vaudenay and HPVP confer NARROW-DESTRUCTIVE-privacy on the OSK-based protocol and NARROW-STRONG-privacy on the IND-CPA-PK-based protocol, while some other models argue that the OSK-based protocol ensures no privacy at all or that the IND-CPA-PK-based protocol cannot be proved private. These last claims are highly restrictive since these two protocols are clearly more private than the dummy identification protocol where tags send their identifier in the clear.


### 11.2.5. The Vaudenay Problem

Finally, Vaudenay proved in [22] that the highest privacy level of his model cannot be achieved. Yet, the highest privacy level of all the other seven presented models can be reached, at least with the IND-CCA-PK-based protocol. To the best of our knowledge, Ouafi is the only author who tries to explain in [20] that the Vaudenay model (i) does not reflect the exact notion of privacy that was targeted at first sight and (ii) may englobe more than only privacy. As explained in Section  5.4, Ouafi reformulates the Vaudenay model in order to achieve STRONG-privacy.


## 11.2.1. The Lack of Comprehensiveness

In some models, several protocols are proved to ensure the same privacy level, because some attacks on these protocols cannot be formalized. For example in the Avoine model, OSK-based, O-FRAP, and PK-based protocols reach the same privacy (i.e.,Existential-UNT-RTE and Forward-UNT-RTEC). However as detailed in Appendix  B.3, the OSK-based protocol can be desynchronized contrary to the other two, and O-FRAP is subject to a specific attack based on tag corruption (see Appendix  B.4), while the PK-based protocol is not vulnerable to such attacks. This misevaluation of privacy happens in almost all models (e.g., {SK-based, tree-based, O-FRAP} for Vaudenay, CCEG, and HPVP, or {SK-based, OSK-based, O-FRAP} for DMR). The main drawback of this fact is that system designers unfamiliar with privacy will probably choose the cheapest protocol (regarding the computing complexity), thinking that these protocols are equivalent regarding their privacy level.


## 11.2.2. The Case of Correlated Secrets

Nevertheless, some models have features that permit attributing different privacy levels to quite similar protocols. As an example, JW, DMR, and DLYZ point out an important characteristic of protocols based on correlated secrets: they prove that the tree-based protocol is not secure, while the SK-based one is. This comes from the fact that an adversary may know some secrets without being authorized to corrupt the challenge tags (as explained in Appendix  B.2). For instance, this adversary could be a tag owner that only knows its tags’ secrets and that is not able to corrupt other tags that it wants to trace. It is consequently normal that the SK-based protocol is more private than the tree-based one. Note that this differentiation cannot be established in the Avoine, Vaudenay, CCEG, and HPVP models because their adversary does not have the modularity to only corrupt certain tags. As a consequence, these models classify the SK-based and the tree-based protocols with the same privacy level.


## 11.2.3. The Key-Update Mechanism Dilemma

All the models (except Avoine and LBM) give the same privacy level for the SK-based protocol and for O-FRAP. This is another obvious example about the issue related to the privacy definitions of these models. Indeed, the two protocols do not manage the tags’ secrets in the same way: a tag updates one of its secrets each time it starts an execution of O-FRAP, while a tag always keeps the same secret when it runs the SK-based protocol. For O-FRAP, the attack presented in Appendix  B.4 only permits linking a freshly corrupted tag to its last previous incomplete protocol execution. But all the previous completed ones are unlinkable. This is not the case with the SK-based protocol, where a tag corruption allows tracing the tag at any time (past or future). This obvious distinction of the two protocols is however not highlighted by most of the models.


## 11.2.4. Accuracy Refinement of theNARROW Adversary

TheNARROW nuance provided in some models permits granting some protocols with a reasonable privacy level. For instance, Vaudenay and HPVP confer NARROW-DESTRUCTIVE-privacy on the OSK-based protocol and NARROW-STRONG-privacy on the IND-CPA-PK-based protocol, while some other models argue that the OSK-based protocol ensures no privacy at all or that the IND-CPA-PK-based protocol cannot be proved private. These last claims are highly restrictive since these two protocols are clearly more private than the dummy identification protocol where tags send their identifier in the clear.


## 11.2.5. The Vaudenay Problem

Finally, Vaudenay proved in [22] that the highest privacy level of his model cannot be achieved. Yet, the highest privacy level of all the other seven presented models can be reached, at least with the IND-CCA-PK-based protocol. To the best of our knowledge, Ouafi is the only author who tries to explain in [20] that the Vaudenay model (i) does not reflect the exact notion of privacy that was targeted at first sight and (ii) may englobe more than only privacy. As explained in Section  5.4, Ouafi reformulates the Vaudenay model in order to achieve STRONG-privacy.


## 12. Classification of the Models

In this section, we compare the different features of all the privacy models presented in this paper. We point out which model(s) is(are) the most appropriate to use according to whether one of these features is wished or not. Table2 sums up the features that are achieved by each model.Table 2
Comparison of the presented privacy models. “✓” (resp., “✗”) means that the feature is (resp., is not) given to the adversary 𝒜. “N/A” means that the feature is not applicable in the model.
Feature
Model
Avoine
JW
Vaudenay
LBM
DMR
CCEG
DLYZ
HPVP
Interaction with all the tags
Only 2 tags
not𝒯b⊕1*
✓
✓
not corrupted agents
✓
not all clean tags
all-but-one
Choice of the challenge tags
✗
✓
✓
✓
✓
✓
✓
✓
Attack on incomplete executions
Both
✓
✓
✗
✓
✓
✓
✓
Corrupt challenge tags
Only𝒯
Only𝒯b*
✓
✓
✗
✓
✗
✓
Corrupt nonchallenge tags
N/A
✓
N/A
N/A
✓
N/A
✓
N/A
Corrupt any tag
✗
✗
✓
✓
✗
✓
✗
✓
N
A
R
R
O
W/WIDE
N
A
R
R
O
W
W
I
D
E
both
W
I
D
E
N
A
R
R
O
W
W
I
D
E
W
I
D
E
Both
Channels asymmetry
✓
✗
✗
✗
✗
✗
✗
✗
Protocols analyzable
3-pass with independent secrets
SK based
all
all
all
all
(
2
γ
+
1
)-pass
All
Tag-init protocols analyzable
✗
✓
✗
✗
✓
✗
✗
✗Note that “protocols” (resp., “tag-init protocols”) refer to authentication/identification protocols where the reader (resp., tag) is the only entity that can start a protocol execution.


### 12.1. Adversary Experiment

Privacy models can be compared according to the similarities and differences of their experiment. To do so, we first need to define the notion ofchallenge tags in some models. Indeed, Vaudenay, LBM, DMR, CCEG, and HPVP do not stipulate this specific notion in their experiment. However, since their adversary must use some tags for its attack, we consider that all the tags are challenge ones. Note that the agents that can be corrupted before 𝒜’s attack in the DMR model are considered as nonchallenge tags.


#### 12.1.1. Number of Tags Allowed in the Experiment

Vaudenay, LBM, and CCEG are the only models where the adversary𝒜 is free to play with all the tags of the system at the same time during its attack.At one moment of their experiment, JW and HPVP can only play with at most(n-1) tags (where n is the total number of tags of the studied system). For the DLYZ model, the adversary cannot play with the set of clean tags it chose, except with the challenge tag 𝒯c picked at random in this set. If this set contains only two tags, it can however play with at most (n-1) tags. Then, DMR’s adversary cannot play with the agents that were corrupted before the beginning of its attack. Finally, the Avoine model is the most limiting one, since 𝒜 can only play with two tags. This fact prevents the Avoine model from analyzing protocols with correlated secrets, which is not the case for all the other models.Therefore, if𝒜 is allowed to play with all the tags of the system, then it is preferable to use the Vaudenay, LBM, and CCEG models for the privacy analysis.


#### 12.1.2. Choice of the Challenge Tags

All the models (except the Avoine one) allow𝒜 to choose the challenge tags of its attack. In the Avoine model, the challenger 𝒞 is the entity that performs this task, choosing 𝒯, 𝒯0, and 𝒯1 (such that 𝒯=𝒯0 or 𝒯1). 𝒜 has no option on the tags used for its attack: it is weaker than the adversaries of the other models. Thus, if it is considered that 𝒜 has the possibility to choose the challenge tags, protocol should be analyzed with all the models except the Avoine one.


#### 12.1.3. Attack on Incomplete Protocol Executions

In the JW, Vaudenay, DMR, CCEG, DLYZ, and HPVP models,𝒜 is allowed to perform its attack on incomplete protocol executions. As illustrated in Appendix  B.4, it can start an execution with a tag and not finish it. Afterward, it can use this tag during its game to break its privacy. If 𝒜 succeeds to do so, then the protocol is not considered as private.For LBM, such an attack is not taken into account.ℱaauth is designed such that all the successfully completed protocol executions of a tag are protected against corruption. In other words, 𝒜 cannot learn any information about these previous executions, and thus the privacy of a tag is ensured. However, it is authorized to link the previous incomplete executions of a corrupted tag up to the last completed one without compromising the security.For the Avoine model, both scenarios are allowed. During theExistential game, 𝒜 chooses the intervals I0 and I1 of the challenge tags that help it the most to perform its attack. It can choose I0 and I1 such that these intervals are directly consecutive to I (the interval of the targeted tag 𝒯). In that case, nothing prevents 𝒜 from using incomplete protocol executions during the experiment. For the Universal game, the challenger 𝒞 is the one that chooses I0 and I1 that help 𝒜 the less, contrary to the Existential game. If 𝒜 uses incomplete protocol executions, then 𝒞 can choose nonconsecutive intervals such that the incomplete executions remain meaningless to 𝒜 (as for LBM). For instance, some completed executions may separate the executions (completed or not) performed within the intervals.Therefore, if a protocol must be protected against this attack, then Avoine, JW, Vaudenay, DMR, CCEG, DLYZ, and HPVP are the most appropriate models to study its privacy. If such a feature is not wished, then it can be analyzed with the Avoine and LBM models. Note that the Avoine model is the most flexible one since it can handle both scenarios.


### 12.2. Tag Corruption

The tamper resistance of RFID tags is a highly questionable assumption. Fortunately, all the models are flexible regarding the capacity of an adversary to corrupt tags. The two extreme cases are the impossibility to corrupt tags or the possibility to perform this action without restrictions. Yet, as detailed in the previous sections, intermediate levels of corruption have been introduced. To have an overall view of these levels, the models are gathered below based on their similarities from the weakest corruption level to the strongest one.


#### 12.2.1. Weak Adversary

Obviously the weakest corruption level is when𝒜 is not allowed to corrupt tags. This feature is present in the Avoine, Vaudenay, LBM, CCEG and HPVP models. It permits formalizing the assumption of tags tamper resistance.Although the JW, DMR and DLYZ models consider that it is always possible to corrupt non-challenge tags, they also define a weak level of corruption where𝒜 is not able to corrupt the challenge tags. This adversary, called insider adversary in [40], may be a tag owner that only knows its tags’ secrets and that wants to break the privacy of other tags. As explained in Section  11.2 and in Appendix  B.2, this subtle adversary can be used to perform a dedicated attack on a system with correlated secrets. However, even if this attack can be caught in other models by an overpowerful adversary (e.g., Vaudenay’s FORWARD adversary), the Vaudenay, LBM, CCEG, and HPVP models are unable to precisely formalize such an intermediate adversary, since these models allow 𝒜 to corrupt either every tag or any tag at all.Therefore on the one hand, if it is assumed that𝒜 can never corrupt a tag, then the Avoine, Vaudenay, LBM, CCEG, and HPVP models should be chosen for a protocol analysis. On the other hand, if it is assumed that only the nonchallenge tags can be corrupted, then the most appropriate and fair models to use are JW, DMR, and DLYZ.


#### 12.2.2. Nonadaptive Adversary

A higher level of corruption consists in authorizing𝒜 to only corrupt tags at the end of the experiment. It corresponds to the FORWARD adversary of Vaudenay and HPVP and to the Forward-UNT notion of Avoine. It can be viewed as a nonadaptive corruption ability as, except other corruptions, 𝒜 cannot adapt its attack according to the corruption result.Theforward-ZK-privacy of DLYZ is close to this property since the last key of the challenge tag is given to the distinguisher at the end of the experiment. Yet in this case, 𝒜 is still allowed to adaptively corrupt the nonchallenge tags during the experiment without stopping it. This fact slightly increases the strength of DLYZ’s adversary.


#### 12.2.3. Destructive Adversary

To increase the adversary power, some models give𝒜 the ability to pursue its attack after a corruption, leading to adaptive attacks regarding corruption. However, some constraints are still put into place in some models. In fact, the JW model considers that the challenge tags may be corrupted in the forward-(ρ,σ,τ)-privacy, but only during the challenge phase. In other words, a tag corruption can only be used to trace its previous interactions. It is thus possible to establish a parallel between this constraint and the destructive corruption ability defined in other models (i.e., the DESTRUCTIVE adversary of Vaudenay, CCEG and HPVP, and the forward-security of LBM). Indeed, the key material obtained through a tag corruption may allow tracing its previous interactions but not the future ones as the tag is destroyed.


#### 12.2.4. Strong Adversary

The strongest level that can be defined is obviously when𝒜 has no restriction regarding tag corruption. This corresponds to the STRONG adversary defined in the Vaudenay, CCEG, and HPVP models. A relatively similar notion is also defined by DLYZ, namely, the backward-ZK-privacy. However, as for the forward-ZK-privacy, while every nonchallenge tag may be corrupted during the experiment, the challenge tag cannot, and its initial key is only revealed at the end of the experiment. It may still help to distinguish the following interactions of this tag, but 𝒜 cannot adapt its attack to this result. This consequently leads to a nonadaptive adversary that may be useful in some cases. Nevertheless, one may prefer the Vaudenay, CCEG, and HPVP models to catch the strongest adversary definition regarding corruption ability.As a conclusion, the Vaudenay, CCEG, and HPVP models offer a wider adversary granularity regarding tag corruption. (Note that the CCEG's authors consider thatFORWARD and DESTRUCTIVE adversaries (in Vaudenay's sense) are equivalent in their experiment: both are able to output a standard or past NOL, but not a future NOL. Therefore, a FORWARD adversary is useless in their model.) Only these three models take into account the strongest adversary which can corrupt with no restriction. Nevertheless, they do not consider the insider adversary that represents a relevant assumption and affords, to our mind, an interesting granularity for some analyses. In this case, protocols may thus be studied with a more appropriate model, namely, either JW, or DMR, or DLYZ.


### 12.3. Other Features

The remaining features of Table2 are discussed in the following.


#### 12.3.1.NARROW/WIDE Adversaries

As previously said, an adversary𝒜 is said to be NARROW (resp., WIDE) when it does not (resp., does) receive the result of a protocol execution. Several models restrict their adversary with one of these features.Avoine does not define a Result oracle, and there is no equivalence of such an oracle in DMR (since𝒜 does not know if a protocol between two agents succeeds). Both models only consider NARROW adversaries.On the contrary, the adversaries of JW, LBM, CCEG, and DLYZ are onlyWIDE ones. For JW, there is no Result oracle defined in the model, but the adversary is forced to obtain the result of a protocol execution via the output of each SendReader. The DLYZ’s adversary has the same behavior: it is forced to know this result information since oℛsid and o𝒯sid are public. In the LBM model, the output tape of each party is always available to 𝒵. Additionally, the adversary may also learn it as 𝒵 can communicate arbitrarily with it. Thus, it is impossible to model a NARROW adversary since the distinguisher may always know the result of a protocol execution. For CCEG, no NARROW adversary can be used for the untraceability experiment. Yet, as stressed in OSK’s analysis given in Appendix  B.3, this voluntary restriction implies that this kind of protocols with decent security features are not considered private.The Vaudenay and HPVP models are the most flexible ones since it is possible to choose either aNARROW or a WIDE adversary. Note that the other models can however be (more or less easily) adapted to provide both adversary classes.


#### 12.3.2. Channels Asymmetry

As already explained in Section3, the forward channel (reader to tag) has a longer communication range than the backward channel (tag to reader). This characteristic is of interest as it has been shown in [41] that the former can be more easily eavesdropped than the latter in practice. Yet, the Avoine model is the only one that formalizes this feature through the Execute* oracle: 𝒜 may only obtain the messages sent by ℛ on the forward channel.All the other models (as a matter of fact, created after the Avoine one) lost this feature and cannot represent this kind of weaker but realistic adversary. Thus, assuming that𝒜 is only able to get the messages sent from ℛ, the analysis must be performed with the Avoine model.


#### 12.3.3. Analyzable Protocols

Some models are designed “by default” to analyze specific identification/authentication protocols. In the Avoine model, the oracles to interact with the system can only be used for 3-pass protocols. Then, JW’s authors only aim to analyze protocols based on symmetric-key cryptography. Finally, DLYZ can only analyze(2γ+1)-pass protocols with γ≥1.On the contrary, Vaudenay, LBM, DMR, CCEG, and HPVP can analyze any identification/authentication protocol. Some of the restrictive models can nevertheless be adapted to analyze most existing protocols. For instance, the Avoine model can be slightly modified to analyze 2-pass classical challenge-response protocols, and the JW model does not forbid the analysis of protocols with public-key cryptography.Finally, considering protocols where the tag starts an execution, JW and DMR are the only models that are not restricted by default to analyze such protocols.


## 12.1. Adversary Experiment

Privacy models can be compared according to the similarities and differences of their experiment. To do so, we first need to define the notion ofchallenge tags in some models. Indeed, Vaudenay, LBM, DMR, CCEG, and HPVP do not stipulate this specific notion in their experiment. However, since their adversary must use some tags for its attack, we consider that all the tags are challenge ones. Note that the agents that can be corrupted before 𝒜’s attack in the DMR model are considered as nonchallenge tags.


### 12.1.1. Number of Tags Allowed in the Experiment

Vaudenay, LBM, and CCEG are the only models where the adversary𝒜 is free to play with all the tags of the system at the same time during its attack.At one moment of their experiment, JW and HPVP can only play with at most(n-1) tags (where n is the total number of tags of the studied system). For the DLYZ model, the adversary cannot play with the set of clean tags it chose, except with the challenge tag 𝒯c picked at random in this set. If this set contains only two tags, it can however play with at most (n-1) tags. Then, DMR’s adversary cannot play with the agents that were corrupted before the beginning of its attack. Finally, the Avoine model is the most limiting one, since 𝒜 can only play with two tags. This fact prevents the Avoine model from analyzing protocols with correlated secrets, which is not the case for all the other models.Therefore, if𝒜 is allowed to play with all the tags of the system, then it is preferable to use the Vaudenay, LBM, and CCEG models for the privacy analysis.


### 12.1.2. Choice of the Challenge Tags

All the models (except the Avoine one) allow𝒜 to choose the challenge tags of its attack. In the Avoine model, the challenger 𝒞 is the entity that performs this task, choosing 𝒯, 𝒯0, and 𝒯1 (such that 𝒯=𝒯0 or 𝒯1). 𝒜 has no option on the tags used for its attack: it is weaker than the adversaries of the other models. Thus, if it is considered that 𝒜 has the possibility to choose the challenge tags, protocol should be analyzed with all the models except the Avoine one.


### 12.1.3. Attack on Incomplete Protocol Executions

In the JW, Vaudenay, DMR, CCEG, DLYZ, and HPVP models,𝒜 is allowed to perform its attack on incomplete protocol executions. As illustrated in Appendix  B.4, it can start an execution with a tag and not finish it. Afterward, it can use this tag during its game to break its privacy. If 𝒜 succeeds to do so, then the protocol is not considered as private.For LBM, such an attack is not taken into account.ℱaauth is designed such that all the successfully completed protocol executions of a tag are protected against corruption. In other words, 𝒜 cannot learn any information about these previous executions, and thus the privacy of a tag is ensured. However, it is authorized to link the previous incomplete executions of a corrupted tag up to the last completed one without compromising the security.For the Avoine model, both scenarios are allowed. During theExistential game, 𝒜 chooses the intervals I0 and I1 of the challenge tags that help it the most to perform its attack. It can choose I0 and I1 such that these intervals are directly consecutive to I (the interval of the targeted tag 𝒯). In that case, nothing prevents 𝒜 from using incomplete protocol executions during the experiment. For the Universal game, the challenger 𝒞 is the one that chooses I0 and I1 that help 𝒜 the less, contrary to the Existential game. If 𝒜 uses incomplete protocol executions, then 𝒞 can choose nonconsecutive intervals such that the incomplete executions remain meaningless to 𝒜 (as for LBM). For instance, some completed executions may separate the executions (completed or not) performed within the intervals.Therefore, if a protocol must be protected against this attack, then Avoine, JW, Vaudenay, DMR, CCEG, DLYZ, and HPVP are the most appropriate models to study its privacy. If such a feature is not wished, then it can be analyzed with the Avoine and LBM models. Note that the Avoine model is the most flexible one since it can handle both scenarios.


## 12.1.1. Number of Tags Allowed in the Experiment

Vaudenay, LBM, and CCEG are the only models where the adversary𝒜 is free to play with all the tags of the system at the same time during its attack.At one moment of their experiment, JW and HPVP can only play with at most(n-1) tags (where n is the total number of tags of the studied system). For the DLYZ model, the adversary cannot play with the set of clean tags it chose, except with the challenge tag 𝒯c picked at random in this set. If this set contains only two tags, it can however play with at most (n-1) tags. Then, DMR’s adversary cannot play with the agents that were corrupted before the beginning of its attack. Finally, the Avoine model is the most limiting one, since 𝒜 can only play with two tags. This fact prevents the Avoine model from analyzing protocols with correlated secrets, which is not the case for all the other models.Therefore, if𝒜 is allowed to play with all the tags of the system, then it is preferable to use the Vaudenay, LBM, and CCEG models for the privacy analysis.


## 12.1.2. Choice of the Challenge Tags

All the models (except the Avoine one) allow𝒜 to choose the challenge tags of its attack. In the Avoine model, the challenger 𝒞 is the entity that performs this task, choosing 𝒯, 𝒯0, and 𝒯1 (such that 𝒯=𝒯0 or 𝒯1). 𝒜 has no option on the tags used for its attack: it is weaker than the adversaries of the other models. Thus, if it is considered that 𝒜 has the possibility to choose the challenge tags, protocol should be analyzed with all the models except the Avoine one.


## 12.1.3. Attack on Incomplete Protocol Executions

In the JW, Vaudenay, DMR, CCEG, DLYZ, and HPVP models,𝒜 is allowed to perform its attack on incomplete protocol executions. As illustrated in Appendix  B.4, it can start an execution with a tag and not finish it. Afterward, it can use this tag during its game to break its privacy. If 𝒜 succeeds to do so, then the protocol is not considered as private.For LBM, such an attack is not taken into account.ℱaauth is designed such that all the successfully completed protocol executions of a tag are protected against corruption. In other words, 𝒜 cannot learn any information about these previous executions, and thus the privacy of a tag is ensured. However, it is authorized to link the previous incomplete executions of a corrupted tag up to the last completed one without compromising the security.For the Avoine model, both scenarios are allowed. During theExistential game, 𝒜 chooses the intervals I0 and I1 of the challenge tags that help it the most to perform its attack. It can choose I0 and I1 such that these intervals are directly consecutive to I (the interval of the targeted tag 𝒯). In that case, nothing prevents 𝒜 from using incomplete protocol executions during the experiment. For the Universal game, the challenger 𝒞 is the one that chooses I0 and I1 that help 𝒜 the less, contrary to the Existential game. If 𝒜 uses incomplete protocol executions, then 𝒞 can choose nonconsecutive intervals such that the incomplete executions remain meaningless to 𝒜 (as for LBM). For instance, some completed executions may separate the executions (completed or not) performed within the intervals.Therefore, if a protocol must be protected against this attack, then Avoine, JW, Vaudenay, DMR, CCEG, DLYZ, and HPVP are the most appropriate models to study its privacy. If such a feature is not wished, then it can be analyzed with the Avoine and LBM models. Note that the Avoine model is the most flexible one since it can handle both scenarios.


## 12.2. Tag Corruption

The tamper resistance of RFID tags is a highly questionable assumption. Fortunately, all the models are flexible regarding the capacity of an adversary to corrupt tags. The two extreme cases are the impossibility to corrupt tags or the possibility to perform this action without restrictions. Yet, as detailed in the previous sections, intermediate levels of corruption have been introduced. To have an overall view of these levels, the models are gathered below based on their similarities from the weakest corruption level to the strongest one.


### 12.2.1. Weak Adversary

Obviously the weakest corruption level is when𝒜 is not allowed to corrupt tags. This feature is present in the Avoine, Vaudenay, LBM, CCEG and HPVP models. It permits formalizing the assumption of tags tamper resistance.Although the JW, DMR and DLYZ models consider that it is always possible to corrupt non-challenge tags, they also define a weak level of corruption where𝒜 is not able to corrupt the challenge tags. This adversary, called insider adversary in [40], may be a tag owner that only knows its tags’ secrets and that wants to break the privacy of other tags. As explained in Section  11.2 and in Appendix  B.2, this subtle adversary can be used to perform a dedicated attack on a system with correlated secrets. However, even if this attack can be caught in other models by an overpowerful adversary (e.g., Vaudenay’s FORWARD adversary), the Vaudenay, LBM, CCEG, and HPVP models are unable to precisely formalize such an intermediate adversary, since these models allow 𝒜 to corrupt either every tag or any tag at all.Therefore on the one hand, if it is assumed that𝒜 can never corrupt a tag, then the Avoine, Vaudenay, LBM, CCEG, and HPVP models should be chosen for a protocol analysis. On the other hand, if it is assumed that only the nonchallenge tags can be corrupted, then the most appropriate and fair models to use are JW, DMR, and DLYZ.


### 12.2.2. Nonadaptive Adversary

A higher level of corruption consists in authorizing𝒜 to only corrupt tags at the end of the experiment. It corresponds to the FORWARD adversary of Vaudenay and HPVP and to the Forward-UNT notion of Avoine. It can be viewed as a nonadaptive corruption ability as, except other corruptions, 𝒜 cannot adapt its attack according to the corruption result.Theforward-ZK-privacy of DLYZ is close to this property since the last key of the challenge tag is given to the distinguisher at the end of the experiment. Yet in this case, 𝒜 is still allowed to adaptively corrupt the nonchallenge tags during the experiment without stopping it. This fact slightly increases the strength of DLYZ’s adversary.


### 12.2.3. Destructive Adversary

To increase the adversary power, some models give𝒜 the ability to pursue its attack after a corruption, leading to adaptive attacks regarding corruption. However, some constraints are still put into place in some models. In fact, the JW model considers that the challenge tags may be corrupted in the forward-(ρ,σ,τ)-privacy, but only during the challenge phase. In other words, a tag corruption can only be used to trace its previous interactions. It is thus possible to establish a parallel between this constraint and the destructive corruption ability defined in other models (i.e., the DESTRUCTIVE adversary of Vaudenay, CCEG and HPVP, and the forward-security of LBM). Indeed, the key material obtained through a tag corruption may allow tracing its previous interactions but not the future ones as the tag is destroyed.


### 12.2.4. Strong Adversary

The strongest level that can be defined is obviously when𝒜 has no restriction regarding tag corruption. This corresponds to the STRONG adversary defined in the Vaudenay, CCEG, and HPVP models. A relatively similar notion is also defined by DLYZ, namely, the backward-ZK-privacy. However, as for the forward-ZK-privacy, while every nonchallenge tag may be corrupted during the experiment, the challenge tag cannot, and its initial key is only revealed at the end of the experiment. It may still help to distinguish the following interactions of this tag, but 𝒜 cannot adapt its attack to this result. This consequently leads to a nonadaptive adversary that may be useful in some cases. Nevertheless, one may prefer the Vaudenay, CCEG, and HPVP models to catch the strongest adversary definition regarding corruption ability.As a conclusion, the Vaudenay, CCEG, and HPVP models offer a wider adversary granularity regarding tag corruption. (Note that the CCEG's authors consider thatFORWARD and DESTRUCTIVE adversaries (in Vaudenay's sense) are equivalent in their experiment: both are able to output a standard or past NOL, but not a future NOL. Therefore, a FORWARD adversary is useless in their model.) Only these three models take into account the strongest adversary which can corrupt with no restriction. Nevertheless, they do not consider the insider adversary that represents a relevant assumption and affords, to our mind, an interesting granularity for some analyses. In this case, protocols may thus be studied with a more appropriate model, namely, either JW, or DMR, or DLYZ.


## 12.2.1. Weak Adversary

Obviously the weakest corruption level is when𝒜 is not allowed to corrupt tags. This feature is present in the Avoine, Vaudenay, LBM, CCEG and HPVP models. It permits formalizing the assumption of tags tamper resistance.Although the JW, DMR and DLYZ models consider that it is always possible to corrupt non-challenge tags, they also define a weak level of corruption where𝒜 is not able to corrupt the challenge tags. This adversary, called insider adversary in [40], may be a tag owner that only knows its tags’ secrets and that wants to break the privacy of other tags. As explained in Section  11.2 and in Appendix  B.2, this subtle adversary can be used to perform a dedicated attack on a system with correlated secrets. However, even if this attack can be caught in other models by an overpowerful adversary (e.g., Vaudenay’s FORWARD adversary), the Vaudenay, LBM, CCEG, and HPVP models are unable to precisely formalize such an intermediate adversary, since these models allow 𝒜 to corrupt either every tag or any tag at all.Therefore on the one hand, if it is assumed that𝒜 can never corrupt a tag, then the Avoine, Vaudenay, LBM, CCEG, and HPVP models should be chosen for a protocol analysis. On the other hand, if it is assumed that only the nonchallenge tags can be corrupted, then the most appropriate and fair models to use are JW, DMR, and DLYZ.


## 12.2.2. Nonadaptive Adversary

A higher level of corruption consists in authorizing𝒜 to only corrupt tags at the end of the experiment. It corresponds to the FORWARD adversary of Vaudenay and HPVP and to the Forward-UNT notion of Avoine. It can be viewed as a nonadaptive corruption ability as, except other corruptions, 𝒜 cannot adapt its attack according to the corruption result.Theforward-ZK-privacy of DLYZ is close to this property since the last key of the challenge tag is given to the distinguisher at the end of the experiment. Yet in this case, 𝒜 is still allowed to adaptively corrupt the nonchallenge tags during the experiment without stopping it. This fact slightly increases the strength of DLYZ’s adversary.


## 12.2.3. Destructive Adversary

To increase the adversary power, some models give𝒜 the ability to pursue its attack after a corruption, leading to adaptive attacks regarding corruption. However, some constraints are still put into place in some models. In fact, the JW model considers that the challenge tags may be corrupted in the forward-(ρ,σ,τ)-privacy, but only during the challenge phase. In other words, a tag corruption can only be used to trace its previous interactions. It is thus possible to establish a parallel between this constraint and the destructive corruption ability defined in other models (i.e., the DESTRUCTIVE adversary of Vaudenay, CCEG and HPVP, and the forward-security of LBM). Indeed, the key material obtained through a tag corruption may allow tracing its previous interactions but not the future ones as the tag is destroyed.


## 12.2.4. Strong Adversary

The strongest level that can be defined is obviously when𝒜 has no restriction regarding tag corruption. This corresponds to the STRONG adversary defined in the Vaudenay, CCEG, and HPVP models. A relatively similar notion is also defined by DLYZ, namely, the backward-ZK-privacy. However, as for the forward-ZK-privacy, while every nonchallenge tag may be corrupted during the experiment, the challenge tag cannot, and its initial key is only revealed at the end of the experiment. It may still help to distinguish the following interactions of this tag, but 𝒜 cannot adapt its attack to this result. This consequently leads to a nonadaptive adversary that may be useful in some cases. Nevertheless, one may prefer the Vaudenay, CCEG, and HPVP models to catch the strongest adversary definition regarding corruption ability.As a conclusion, the Vaudenay, CCEG, and HPVP models offer a wider adversary granularity regarding tag corruption. (Note that the CCEG's authors consider thatFORWARD and DESTRUCTIVE adversaries (in Vaudenay's sense) are equivalent in their experiment: both are able to output a standard or past NOL, but not a future NOL. Therefore, a FORWARD adversary is useless in their model.) Only these three models take into account the strongest adversary which can corrupt with no restriction. Nevertheless, they do not consider the insider adversary that represents a relevant assumption and affords, to our mind, an interesting granularity for some analyses. In this case, protocols may thus be studied with a more appropriate model, namely, either JW, or DMR, or DLYZ.


## 12.3. Other Features

The remaining features of Table2 are discussed in the following.


### 12.3.1.NARROW/WIDE Adversaries

As previously said, an adversary𝒜 is said to be NARROW (resp., WIDE) when it does not (resp., does) receive the result of a protocol execution. Several models restrict their adversary with one of these features.Avoine does not define a Result oracle, and there is no equivalence of such an oracle in DMR (since𝒜 does not know if a protocol between two agents succeeds). Both models only consider NARROW adversaries.On the contrary, the adversaries of JW, LBM, CCEG, and DLYZ are onlyWIDE ones. For JW, there is no Result oracle defined in the model, but the adversary is forced to obtain the result of a protocol execution via the output of each SendReader. The DLYZ’s adversary has the same behavior: it is forced to know this result information since oℛsid and o𝒯sid are public. In the LBM model, the output tape of each party is always available to 𝒵. Additionally, the adversary may also learn it as 𝒵 can communicate arbitrarily with it. Thus, it is impossible to model a NARROW adversary since the distinguisher may always know the result of a protocol execution. For CCEG, no NARROW adversary can be used for the untraceability experiment. Yet, as stressed in OSK’s analysis given in Appendix  B.3, this voluntary restriction implies that this kind of protocols with decent security features are not considered private.The Vaudenay and HPVP models are the most flexible ones since it is possible to choose either aNARROW or a WIDE adversary. Note that the other models can however be (more or less easily) adapted to provide both adversary classes.


### 12.3.2. Channels Asymmetry

As already explained in Section3, the forward channel (reader to tag) has a longer communication range than the backward channel (tag to reader). This characteristic is of interest as it has been shown in [41] that the former can be more easily eavesdropped than the latter in practice. Yet, the Avoine model is the only one that formalizes this feature through the Execute* oracle: 𝒜 may only obtain the messages sent by ℛ on the forward channel.All the other models (as a matter of fact, created after the Avoine one) lost this feature and cannot represent this kind of weaker but realistic adversary. Thus, assuming that𝒜 is only able to get the messages sent from ℛ, the analysis must be performed with the Avoine model.


### 12.3.3. Analyzable Protocols

Some models are designed “by default” to analyze specific identification/authentication protocols. In the Avoine model, the oracles to interact with the system can only be used for 3-pass protocols. Then, JW’s authors only aim to analyze protocols based on symmetric-key cryptography. Finally, DLYZ can only analyze(2γ+1)-pass protocols with γ≥1.On the contrary, Vaudenay, LBM, DMR, CCEG, and HPVP can analyze any identification/authentication protocol. Some of the restrictive models can nevertheless be adapted to analyze most existing protocols. For instance, the Avoine model can be slightly modified to analyze 2-pass classical challenge-response protocols, and the JW model does not forbid the analysis of protocols with public-key cryptography.Finally, considering protocols where the tag starts an execution, JW and DMR are the only models that are not restricted by default to analyze such protocols.


## 12.3.1.NARROW/WIDE Adversaries

As previously said, an adversary𝒜 is said to be NARROW (resp., WIDE) when it does not (resp., does) receive the result of a protocol execution. Several models restrict their adversary with one of these features.Avoine does not define a Result oracle, and there is no equivalence of such an oracle in DMR (since𝒜 does not know if a protocol between two agents succeeds). Both models only consider NARROW adversaries.On the contrary, the adversaries of JW, LBM, CCEG, and DLYZ are onlyWIDE ones. For JW, there is no Result oracle defined in the model, but the adversary is forced to obtain the result of a protocol execution via the output of each SendReader. The DLYZ’s adversary has the same behavior: it is forced to know this result information since oℛsid and o𝒯sid are public. In the LBM model, the output tape of each party is always available to 𝒵. Additionally, the adversary may also learn it as 𝒵 can communicate arbitrarily with it. Thus, it is impossible to model a NARROW adversary since the distinguisher may always know the result of a protocol execution. For CCEG, no NARROW adversary can be used for the untraceability experiment. Yet, as stressed in OSK’s analysis given in Appendix  B.3, this voluntary restriction implies that this kind of protocols with decent security features are not considered private.The Vaudenay and HPVP models are the most flexible ones since it is possible to choose either aNARROW or a WIDE adversary. Note that the other models can however be (more or less easily) adapted to provide both adversary classes.


## 12.3.2. Channels Asymmetry

As already explained in Section3, the forward channel (reader to tag) has a longer communication range than the backward channel (tag to reader). This characteristic is of interest as it has been shown in [41] that the former can be more easily eavesdropped than the latter in practice. Yet, the Avoine model is the only one that formalizes this feature through the Execute* oracle: 𝒜 may only obtain the messages sent by ℛ on the forward channel.All the other models (as a matter of fact, created after the Avoine one) lost this feature and cannot represent this kind of weaker but realistic adversary. Thus, assuming that𝒜 is only able to get the messages sent from ℛ, the analysis must be performed with the Avoine model.


## 12.3.3. Analyzable Protocols

Some models are designed “by default” to analyze specific identification/authentication protocols. In the Avoine model, the oracles to interact with the system can only be used for 3-pass protocols. Then, JW’s authors only aim to analyze protocols based on symmetric-key cryptography. Finally, DLYZ can only analyze(2γ+1)-pass protocols with γ≥1.On the contrary, Vaudenay, LBM, DMR, CCEG, and HPVP can analyze any identification/authentication protocol. Some of the restrictive models can nevertheless be adapted to analyze most existing protocols. For instance, the Avoine model can be slightly modified to analyze 2-pass classical challenge-response protocols, and the JW model does not forbid the analysis of protocols with public-key cryptography.Finally, considering protocols where the tag starts an execution, JW and DMR are the only models that are not restricted by default to analyze such protocols.


## 13. Privacy Properties

In the previous section, we discussed the features that are present (or not) in each of the studied models. To conclude the investigation, we go a step further and compare the privacy properties between them.This task is not an easy one as the different features of each model make it tough to compare them in some cases. Indeed in the following section, we highlight the fact that, when a privacy property of a given model is said to be “stronger” than the one of another model, the “weaker” model may present some features that are not present in the “stronger” one. We assume that system designers are aware of this fact and that, in this special case, they may thus prefer to use the weaker model for their privacy analysis. Except when this fact must be highlighted, we will not detail it in each comparison.


### 13.1. Indistinguishability of Tags

Regarding only the privacy notions, the Avoine and JW models are really close. Indeed, they both define privacy as the unfeasibility for an adversary to recognize one tag among two. The JW model has been designed after the Avoine one, as an improved model since it takes into account several flaws of the Avoine model. It can be easily proved that JW’s(ρ,σ,τ)-privacy (resp., forward-(ρ,σ,τ)-privacy) implies Avoine’s Existential-UNT (resp., Forward-UNT): the goal is the same and any request of an Avoine’s adversary can be performed by a JW’s adversary.In the DMR model, the privacy property corresponds to the unfeasibility to link twotraces that are produced by the same agent (in our case, a tag). This notion is also really close to the one defined in the JW model. Clearly for JW, the adversary capacity to retrieve the tag associated to the bit b permits linking two traces and reciprocally. However, as the DMR model only defines a nonadaptive adversary regarding corruption, JW’s (ρ,σ,τ)-privacy is obviously stronger than DMR’s untraceability.Largely inspired by the design of the Vaudenay model (on which we will come back later), the CCEG and HPVP models offer a comprehensive list of oracles that permit any JW’s adversary to be represented in their models. Regarding the privacy definition, it is obvious that the output of a JW’s adversary is exactly a CCEG’s nonobvious link (standard or past) and can thus be directly exploited by a CCEG’s adversary. As a consequence, CCEG’s standard-untraceability (resp., past-untraceability) property obviously implies JW’s (ρ,σ,τ)-privacy (resp., forward-(ρ,σ,τ)-privacy). The reciprocal does not lead to a tight reduction. Indeed, a CCEG’s adversary may shuffle the tags’ pseudonyms several times (by performing successive DrawTag and Free queries), which are hard to simulate in the JW model.The HPVP model defines privacy using the well-known “left-or-right” paradigm. As detailed in Section10, it splits the tags space into two worlds. Nevertheless, a JW’s adversary can be simulated in this model. First the HPVP’s adversary draws each tag of the system. (A single tag can be given as the two inputs of the DrawTag oracle.) Then, the two selected challenge tags of JW are freed and given as input of the DrawTag oracle. If the JW’s adversary is able to recognize the outputted tag, then it may be used by an HPVP’s adversary to output the guessed bit. Here again, the reciprocal is not true for the same reasons as for the CCEG model.As a conclusion, assuming that privacy is defined as indistinguishability of tags, the most comprehensive models are HPVP and CCEG. Intuitively, these two models have equivalent privacy notions. Indeed, an adversary that succeeds in the HPVP experiment can easily output a nonobvious link. On the opposite, a nonobvious link permits distinguishing one tag from the others and can thus be used in the “left-or-right” paradigm. However, it is not obvious to formally prove this equivalence result due to the following facts. Firstly, at one moment of the HPVP experiment, the adversary must use (at least once) the DrawTag oracle on two different tags in order to obtain information about the challenge bit. At that moment, this adversary can no longer interact with all the tags whereas a CCEG’s adversary can always interact with all the tags if it wants to. Secondly, a CCEG’s adversary may draw more than one tag in a DrawTag request (e.g., three tags out of four). If an HPVP’s adversary wants to use such an adversary as a subroutine to succeed in the HPVP experiment, the simulation of this fact entails that some choices are mandatory and thus leads to a nontight reduction.


### 13.2. Real World versus Simulated World

The last three models (i.e., Vaudenay, LBM, and DLYZ) define privacy as, in a nutshell, the unfeasibility to distinguish the interactions of an adversary against the real system from the interactions of a simulated adversary against a simulated world. In this second world, the simulator does not know the keys of the system. Nevertheless, when a tag corruption is asked, the tag’s real secret key is returned. The idea behind this privacy notion is that, if there exists a distinction between these two worlds, then some information must leak from the messages of the real world (which contains the real keys of the system).The most adaptive and comprehensive model using this principle is clearly the Vaudenay model. First, this model offers the widest range of adversaries. Then, these adversaries can be adaptive, contrary to the ones of DLYZ. Finally, as explained in Section  12.1, the LBM model only ensures the privacy of authentications prior to the last complete one, while the Vaudenay model considers privacy of all the possible authentications. As a consequence, for equivalent adversary classes, the Vaudenay model is stronger than LBM and DLYZ.From another point of view, the UC framework is generally used to analyze protocols that are not run alone, but in parallel/concurrency with other protocols. Here, the interesting feature is that the environment𝒵 can interact with the system and thus may help 𝒜 to perform its attack, while Vaudenay’s adversary is on its own. This fact has been frequently used in the UC literature to prove that some “considered secure” constructions are indeed not. As a consequence, if the protocol to analyze is designed to belong to a complex system, its privacy may be studied in the LBM model. Nevertheless, if a strong privacy property is wished, the protocol should also be analyzed in the Vaudenay model.


### 13.3. Between the Two Families

The oracles description of the CCEG model is really close to the one of Vaudenay. The authors of the former describe their model as a restriction of the Vaudenay one, mainly on the experiment. Indeed, CCEG’s adversary is required to output a nonobvious link, while any adversary assumption can be output in the Vaudenay model. Consequently, CCEG’s privacy notion is intuitively weaker than Vaudenay’s one (for equivalent adversary). Nevertheless, as proved in [11], CCEG’s future-untraceability is a reachable property while Vaudenay’s STRONG-privacy is impossible. Furthermore, to increase their result, CCEG’s authors also prove with a “toy scheme” that their future-untraceability considers attacks that are not taken into account in the two “highest” reachable privacy levels of Vaudenay (i.e., the NARROW-STRONG and DESTRUCTIVE-privacy). As a consequence, the CCEG model defines a potentially weaker privacy notion, but, under this framework, protocol privacy can be studied against a stronger adversary than in the Vaudenay model.Similar results may be proved for the HPVP model. First, its authors exhibit in their paper a protocol that ensuresSTRONG-privacy in their model. Then, using the “toy scheme” defined in [11], it can be proved that the same attacks (highlighted by CCEG) are also taken into account in HPVP’s STRONG-privacy, which are again not considered in the reachable privacy levels of Vaudenay. However, as for the CCEG model, it can be proved that Vaudenay’s privacy implies HPVP’s one for equivalent adversary class. As this final result is not intuitive, we prove it in Appendix C.To conclude this discussion, we highlight some existing results about the DLYZ model. The authors of the original paper argue that JW’s(ρ,σ,τ)-privacy does not imply ZK-privacy and used several schemes to illustrate their claim. One example is a system composed of only one tag. Clearly, such a scheme cannot be analyzed in the JW model since it requires at least two tags in the experiment. Thus, their claim that the proposed scheme is (ρ,σ,τ)-private is doubtful. Additionally, the argument claiming that this scheme is not ZK-private is also not considered as acceptable, according to the authors of [42]. Furthermore, in such a special case of single-tag systems, DLYZ’s authors say that ZK-privacy is reduced to the basic zero-knowledge definition which, according to them, provides a reasonable privacy. However in practice, each time this lonely tag is accepted by a reader, a WIDE adversary is obviously able to link this authentication to the previous ones. To our mind this is obviously a breach of privacy. Finally, the authors of [42] go one step beyond and formally prove that JW’s (ρ,σ,τ)-privacy is equivalent to ZK-privacy (Theorem 1 of [42]).


## 13.1. Indistinguishability of Tags

Regarding only the privacy notions, the Avoine and JW models are really close. Indeed, they both define privacy as the unfeasibility for an adversary to recognize one tag among two. The JW model has been designed after the Avoine one, as an improved model since it takes into account several flaws of the Avoine model. It can be easily proved that JW’s(ρ,σ,τ)-privacy (resp., forward-(ρ,σ,τ)-privacy) implies Avoine’s Existential-UNT (resp., Forward-UNT): the goal is the same and any request of an Avoine’s adversary can be performed by a JW’s adversary.In the DMR model, the privacy property corresponds to the unfeasibility to link twotraces that are produced by the same agent (in our case, a tag). This notion is also really close to the one defined in the JW model. Clearly for JW, the adversary capacity to retrieve the tag associated to the bit b permits linking two traces and reciprocally. However, as the DMR model only defines a nonadaptive adversary regarding corruption, JW’s (ρ,σ,τ)-privacy is obviously stronger than DMR’s untraceability.Largely inspired by the design of the Vaudenay model (on which we will come back later), the CCEG and HPVP models offer a comprehensive list of oracles that permit any JW’s adversary to be represented in their models. Regarding the privacy definition, it is obvious that the output of a JW’s adversary is exactly a CCEG’s nonobvious link (standard or past) and can thus be directly exploited by a CCEG’s adversary. As a consequence, CCEG’s standard-untraceability (resp., past-untraceability) property obviously implies JW’s (ρ,σ,τ)-privacy (resp., forward-(ρ,σ,τ)-privacy). The reciprocal does not lead to a tight reduction. Indeed, a CCEG’s adversary may shuffle the tags’ pseudonyms several times (by performing successive DrawTag and Free queries), which are hard to simulate in the JW model.The HPVP model defines privacy using the well-known “left-or-right” paradigm. As detailed in Section10, it splits the tags space into two worlds. Nevertheless, a JW’s adversary can be simulated in this model. First the HPVP’s adversary draws each tag of the system. (A single tag can be given as the two inputs of the DrawTag oracle.) Then, the two selected challenge tags of JW are freed and given as input of the DrawTag oracle. If the JW’s adversary is able to recognize the outputted tag, then it may be used by an HPVP’s adversary to output the guessed bit. Here again, the reciprocal is not true for the same reasons as for the CCEG model.As a conclusion, assuming that privacy is defined as indistinguishability of tags, the most comprehensive models are HPVP and CCEG. Intuitively, these two models have equivalent privacy notions. Indeed, an adversary that succeeds in the HPVP experiment can easily output a nonobvious link. On the opposite, a nonobvious link permits distinguishing one tag from the others and can thus be used in the “left-or-right” paradigm. However, it is not obvious to formally prove this equivalence result due to the following facts. Firstly, at one moment of the HPVP experiment, the adversary must use (at least once) the DrawTag oracle on two different tags in order to obtain information about the challenge bit. At that moment, this adversary can no longer interact with all the tags whereas a CCEG’s adversary can always interact with all the tags if it wants to. Secondly, a CCEG’s adversary may draw more than one tag in a DrawTag request (e.g., three tags out of four). If an HPVP’s adversary wants to use such an adversary as a subroutine to succeed in the HPVP experiment, the simulation of this fact entails that some choices are mandatory and thus leads to a nontight reduction.


## 13.2. Real World versus Simulated World

The last three models (i.e., Vaudenay, LBM, and DLYZ) define privacy as, in a nutshell, the unfeasibility to distinguish the interactions of an adversary against the real system from the interactions of a simulated adversary against a simulated world. In this second world, the simulator does not know the keys of the system. Nevertheless, when a tag corruption is asked, the tag’s real secret key is returned. The idea behind this privacy notion is that, if there exists a distinction between these two worlds, then some information must leak from the messages of the real world (which contains the real keys of the system).The most adaptive and comprehensive model using this principle is clearly the Vaudenay model. First, this model offers the widest range of adversaries. Then, these adversaries can be adaptive, contrary to the ones of DLYZ. Finally, as explained in Section  12.1, the LBM model only ensures the privacy of authentications prior to the last complete one, while the Vaudenay model considers privacy of all the possible authentications. As a consequence, for equivalent adversary classes, the Vaudenay model is stronger than LBM and DLYZ.From another point of view, the UC framework is generally used to analyze protocols that are not run alone, but in parallel/concurrency with other protocols. Here, the interesting feature is that the environment𝒵 can interact with the system and thus may help 𝒜 to perform its attack, while Vaudenay’s adversary is on its own. This fact has been frequently used in the UC literature to prove that some “considered secure” constructions are indeed not. As a consequence, if the protocol to analyze is designed to belong to a complex system, its privacy may be studied in the LBM model. Nevertheless, if a strong privacy property is wished, the protocol should also be analyzed in the Vaudenay model.


## 13.3. Between the Two Families

The oracles description of the CCEG model is really close to the one of Vaudenay. The authors of the former describe their model as a restriction of the Vaudenay one, mainly on the experiment. Indeed, CCEG’s adversary is required to output a nonobvious link, while any adversary assumption can be output in the Vaudenay model. Consequently, CCEG’s privacy notion is intuitively weaker than Vaudenay’s one (for equivalent adversary). Nevertheless, as proved in [11], CCEG’s future-untraceability is a reachable property while Vaudenay’s STRONG-privacy is impossible. Furthermore, to increase their result, CCEG’s authors also prove with a “toy scheme” that their future-untraceability considers attacks that are not taken into account in the two “highest” reachable privacy levels of Vaudenay (i.e., the NARROW-STRONG and DESTRUCTIVE-privacy). As a consequence, the CCEG model defines a potentially weaker privacy notion, but, under this framework, protocol privacy can be studied against a stronger adversary than in the Vaudenay model.Similar results may be proved for the HPVP model. First, its authors exhibit in their paper a protocol that ensuresSTRONG-privacy in their model. Then, using the “toy scheme” defined in [11], it can be proved that the same attacks (highlighted by CCEG) are also taken into account in HPVP’s STRONG-privacy, which are again not considered in the reachable privacy levels of Vaudenay. However, as for the CCEG model, it can be proved that Vaudenay’s privacy implies HPVP’s one for equivalent adversary class. As this final result is not intuitive, we prove it in Appendix C.To conclude this discussion, we highlight some existing results about the DLYZ model. The authors of the original paper argue that JW’s(ρ,σ,τ)-privacy does not imply ZK-privacy and used several schemes to illustrate their claim. One example is a system composed of only one tag. Clearly, such a scheme cannot be analyzed in the JW model since it requires at least two tags in the experiment. Thus, their claim that the proposed scheme is (ρ,σ,τ)-private is doubtful. Additionally, the argument claiming that this scheme is not ZK-private is also not considered as acceptable, according to the authors of [42]. Furthermore, in such a special case of single-tag systems, DLYZ’s authors say that ZK-privacy is reduced to the basic zero-knowledge definition which, according to them, provides a reasonable privacy. However in practice, each time this lonely tag is accepted by a reader, a WIDE adversary is obviously able to link this authentication to the previous ones. To our mind this is obviously a breach of privacy. Finally, the authors of [42] go one step beyond and formally prove that JW’s (ρ,σ,τ)-privacy is equivalent to ZK-privacy (Theorem 1 of [42]).


## 14. Conclusion

In this paper, we first presented eight of the most well-known existing privacy models for RFID in details. We exhibited and discussed the differences between these models regarding their features and their privacy notions. As a preliminary conclusion, none of the existing models encompass all the others. The first reason is that no model offers enough granularity to provide all the features detailed previously. Even if it is sometime possible to extend an existing model to take into account a new property or a new assumption, it is not always a trivial task to add all of them.Throughout our study, it appears that the Vaudenay model is the one that integrates the greatest number of features and which defines the strongest privacy notion. As a default choice, the Vaudenay model is probably the best one. Nevertheless, some drawbacks have been highlighted. Firstly, the strongest privacy property of this model cannot be ensured by any protocol. To study the security of a protocol against the strongest (known) adversary, one may thus prefer the CCEG of the HPVP model. Secondly, the Vaudenay model (as other ones) considers that tracing a tag after an incomplete protocol execution compromises the privacy. On the one hand, this is a relevant consideration that ensures a strong privacy level. On the other hand, relaxing this constraint helps to design more efficient protocols with a still reasonable privacy level using the Avoine and LBM models. Finally, the lack of granularity of all the models involves difficulties to fairly distinguish, in a given model, protocols with different security levels.If system designers have precisely defined the requested properties of their application and the assumptions regarding potential adversaries, then they might use our results to select the most appropriate model. Thereby, they can design or select the most adapted and efficient protocol for their needs. Nevertheless, we are convinced that unifying and simplifying the models would help the community to design and compare protocols meaningfully.



---

*Source: 710275-2013-02-11.xml*