# The Lightweight RFID Grouping-Proof Protocols with Identity Authentication and Forward Security

Authors: Zhicai Shi; Xiaomei Zhang; Jin Liu
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

In many fields, multiple RFID tags are often combined into a group to identify an object. An RFID grouping-proof protocol is utilized to prove the simultaneous existence of a group of tags. However, many current grouping-proof protocols cannot simultaneously provide privacy preserving, forward security, and the authentication between reader/verifier and tags, which are vulnerable to trace attack, privacy leakage, and desynchronization attack. To improve the secure performance of the current grouping-proof protocols, we propose two provable lightweight grouping-proof protocols that provide forward security, identity authentication, and privacy preserving. Our protocols involve a trusted reader and an untrusted reader, respectively. In order to avoid verifying some invalid evidences, our protocols complete the authentication of the verifier to the trusted reader and the verified tags before the verifier verifies the grouping-proof evidence. Each tag uses parallel mode to complete its signature to improve the efficiency of the protocols. Moreover, the activate-sleep mechanism and the filtering operation are proposed to effectively reduce the collision probability and computing load of tags. Our protocols complete the authentication to tags twice by a verifier and a trusted reader, respectively. They can resist various attacks such as eavesdropping, replay, trace, and desynchronization. The protocols are proven to be secure, flexible, and efficient. They only utilize some lightweight operations. Therefore, they are very suitable to the low-cost RFID systems.


---

## Body

## 1. Introduction

As an important sensing method of Internet of Things (IoTs), Radio Frequency IDentification (RFID) has become a pervasive technology and it has been successfully applied to mobile payment, healthcare, supply chain management, transportation, and other fields [1]. A typical RFID deployment is called an RFID system, which has three main components: Radio Frequency (RF) tags, a reader, and a backend server. A backend server is also called a verifier. Tags are some electronic devices and they are usually used to identify some objects. Tags are usually divided into active tags and passive tags. The current popular tags are passive. They are very simple and cheap. They have no internal power source. When these tags communicate with a reader, they are powered with their on-chip antenna coil, which is activated by the RF signal from the reader. Thus, their computation and communication capabilities are very limited. A tag is usually used to identify an object. However, under many circumstances, multiple tags are combined into a group to identify several related objects or different parts of an object. Therefore, it is necessary to read several tags simultaneously and to prove their coexistence.In 2004, Juels [2] proposed the first application of a group of tags. He combined two tags into a group to identify the container of the medication and the leaflet, respectively. The leaflet describes the side effects of the medication. He proposed a grouping-proof protocol to verify whether each container was dispensed with its leaflet. Another example is that the manufacturer of aircraft equipment uses two tags to identify a certain part and its safety cap. A grouping-proof protocol is utilized to verify whether a part leaves the factory with its safety cap. For the circumstances described above, some grouping-proof protocols have been proposed to prove the coexistence of multiple tags. Due to the hardware resource limitation of tags, the grouping-proof protocols only use some lightweight cryptographic functions. Hence, the secure level of the current grouping-proof protocols is very limited. The majority of existing protocols do not protect the privacy of the tag and cannot provide forward security [3, 4]. Some grouping-proof protocols usually use serial signature mode so that they need more time to collect the grouping-proof evidence. In order to overcome the flaws above, we propose two novel grouping-proof protocols. These protocols only utilize some lightweight functions to ensure the security and privacy of an RFID system.The main contributions of our work can be summarized as follows:(1)
We proposed two grouping-proof protocols. These protocols involve a reader and multiple tag groups. The reader may be trusted or untrusted. It is used to collect the grouping-proof evidence. The protocols complete both the mutual authentication between the verifier and the trusted reader and the one-way authentication of the reader/verifier to tags. One of our protocols completes the authentication to tags twice by the verifier and the trusted reader, respectively, which enhances the security level of the protocols.(2)
The protocols ensure the privacy of the RFID system by utilizing some one-way lightweight functions to generate sessions between reader and tags.(3)
The protocols provide forward security by means of secrecy updating. When the secrecy is updated, the old secrecy is reserved in the verifier so that the protocols can resist desynchronization attack.(4)
In order to reduce the collision probability and computation load of tags, a novel activate-sleep mechanism is proposed. The mechanism makes the related tags activated and other tags sleep during the grouping-proof period. When the reader communicates with tags, only the activated tags give their response. Therefore the collision probability and computation load of tags are remarkably reduced.(5)
The protocols utilize the mechanism based on MAC layer protocol of Ethernet. The message broadcasted by a reader is only received by a certain tag and other unrelated tags do not participate in the interaction of the protocols, which is called the filtering operation. Therefore our protocols use a broadcast RF channel to complete the peer-to-peer communication between a reader and a certain tag, which further reduces the computation load of tags and the collision probability between them.The rest of this paper is organized as follows. In Section2, we briefly review some typical grouping-proof protocols and analyze their security. In Section 3, we describe the RFID system under the grouping-proof mode and propose its security model. In Section 4, we propose two novel grouping-proof protocols by utilizing parallel communication mode, the activate-sleep mechanism, and the filtering operation. We describe the detail process of the protocols. In Section 5, we prove the security of our protocols. We analyze their security performance and compare them with some typical grouping-proof protocols. Finally, we give the conclusions in Section 6.


## 2. Some Typical RFID Grouping-Proof Protocols

In this section, we describe some typical and related grouping-proof protocols and discuss their security and vulnerability.The first grouping-proof protocol is the Yoking-proofs protocol, which is proposed by Juels [2]. This protocol only involves two tags. The protocol gives a proof that a pair of tags has been scanned simultaneously. For the minimalist version of the protocol, the identifiers of the tags are transferred in plaintext. An adversary can intercept these identifiers by eavesdropping the sessions between reader and tags. Then he can get the privacy of the RFID system. Therefore the protocol cannot resist privacy leakage. Saito and Sakurai [5] and Burmester et al. [3] analyzed the Yoking-proofs protocol. They found that it does not resist replay attack and does not check the results from other tags so that some unrelated tags can join the protocol. Another weakness is that a corrupted tag can impersonate a legal tag to generate the valid evidence. Otherwise, the protocol cannot resist interleaving attack [6].Leng et al. [7] proposed a select-response grouping-proof protocol. Instead of waiting for the computation result from the tags, their protocol allows the reader to actively select the demanded tags. Therefore their protocol can provide collision-free performance and identify the missing tags. But a malicious tag can stop a legitimate proof generation or force creating an invalid proof. So their protocol cannot resist denial of service (DoS) attack. To overcome these problems, they propose an online protocol and the verifier is involved in each step instead of waiting. Therefore, the protocol wastes the time of the verifier.Huang and Ku [8] proposed a grouping-proof protocol conforming to the Class-1 Gen-2 standard. Their protocol is used to check the correlation of drug and patient so as to enhance medication safety. Peris-Lopez et al. [4] found that the protocol uses CRC functions. These functions are some algorithms based on polynomial arithmetic in F2. They found that an attacker can exploit the linearity property of CRC functions, such as CRCa⊕b=CRCa⊕CRCb to get the private information of the tag. Then he can impersonate this tag in the future grouping-proof protocol. Otherwise, for the protocol proposed by Huang H-H et al., the target tag updates its pin once it is interrogated by an attacker. But the verifier does not know that the target tag has been interrogated and the verifier does not update its pin. Therefore the verifier and the tags own different pin and they lose their synchronization. So the protocol cannot resist desynchronization attack.Chien et al. [9] proposed two grouping-proof protocols for the EPC C1-G2 tags. Their protocols only utilize a 16-bit pseudorandom number generator and bitwise XOR operation. Peris-Lopez et al. [4] analyzed the online protocol and found a vulnerability. If an adversary detects that the tag and the reader generate the same random number he can generate a fixed session unrelated to the random number. Later he can use the session to impersonate a target tag. Therefore, the protocol cannot resist forgery attack and subset replay attack. To overcome the shortcoming of the online protocol, Chien et al. proposed an offline protocol. But their offline protocol cannot also resist subset replay attack. In addition, their protocol cannot be applied to some special scenarios where the number and type of tags are not known in advance.Like the two protocols described above, Peris-Lopez et al. [10] also proposed a grouping-proof protocol to enhance medication safety. For their protocol, the unit-dose packages can automatically match the inpatient to avoid human error. Peris-Lopez et al. claimed that the digital evidence from their protocol could be used for medication tracking and auditing. But Yen et al. [11] found that only the nurse signed the evidence. If a medication dispute occurs, the hospital can counterfeit evidence. In order to overcome the security vulnerability described above, Yen et al. proposed another solution. Their protocol involves four entities: the backend server, the nurse’s PDA, the inpatient’s wristband, and the unit-dose drug packages. However, their protocol could not resist tracing attack. If the inpatient and the unit-dose tags receive the same challenge from the nurse’s PDA many times, they will return the same message. Then an adversary can locate the inpatient and his/her unit-dose package. Therefore, it is easy to leak the privacy of the inpatient. Otherwise, the secret keys of the protocol are not updated after each grouping-proof and the protocol cannot ensure forward security.Liu et al. [12] analyzed some previous grouping-proof protocols. They found that many protocols only involve a single reader and a group of tags. Then they adopted the distributed authentication mode to propose a grouping-proof protocol. They claimed that their protocol can resist some typical attacks such as forgery, tracking, replay, and denial of proof. Later, Shen et al. [13] proposed an enhanced protocol and claimed that their protocol could preserve the privacy of the RFID system and resist replay attack. However, we found that their protocol uses the plaintext of the identifiers for communication. Moreover, these identifiers are fixed during the grouping-proof period. Hence, their protocol cannot resist trace attack and it seriously leaks the privacy of the RFID system. The grouping-proof evidence Vi of each tag is generated independently and there is not any relationship between Vm and Vnm≠n. Their grouping-proof protocol does not have any time limitation. So their grouping-proof evidence does not prove the coexistence of the related tags.By analyzing some previous grouping-proof protocols, Moriyama [14] utilized parallel signature mode to propose a two-round grouping-proof protocol. The protocol only involves two round sessions. The number of the sessions is independent of the number of tags. But the protocol can only resist impersonation attack. The timestamp is generated by the reader. If it is timeout the verifier cannot judge the validness of the grouping-proof evidence.Sundaresan et al. [15] analyzed some special requirements for a grouping-proof protocol. Then they proposed a robust grouping-proof protocol for the EPC C1-G2 tags. The protocol provides forward security. It utilizes serial signature mode to collect the grouping-proof evidence from each tag so as to degrade its efficiency. Each tag has to complete a large amount of 128-bit operations, which further reduces the efficiency of the protocol. After the ith tag generates its evidence Mi, it updates its secret VTS. If a grouping-proof collecting process is stopped or aborted the subsequent tag (e.g., the jth tag, j>i) cannot update its secret VTS. Thus some tags’ secrets are updated and other tags’ secrets are not updated. Their secrets are not synchronous. Therefore, the protocol cannot resist DoS attack. Otherwise, after a reader is only authenticated it can be authorized to complete the grouping-proof. When there are only some untrusted readers near the verifier they cannot be authorized to complete a grouping-proof.Huang and Mu [16] proposed a grouping-proof protocol that introduced a new method of the key distribution. The protocol only utilizes some lightweight functions (not hash function) to generate the sessions so as to reduce the computing cost of tags. But the protocol updates the secret key of tags twice for each grouping-proof period. After a tag completes the first updating of its secret key ci, the reader uses the previous ci to generate ci−ai+rTi and send the result to the tag. The tag cannot authenticate the reader because the secret keys ci they own are different. Hence desynchronization attack occurs and the protocol cannot resist DoS attack. For the protocol, if an adversary impersonates a reader and repeats to transmit S and a random number rR to a tag, the tag will reply the same Hbi⊕rR and kl2/kl1. The protocol also cannot resist tracing attack. kl2/kl1 is transferred in plaintext so that the protocol cannot preserve the privacy of the tags. Otherwise, the secret keys of the tags are stored in the reader. So the reader must be trusted. Any untrusted reader cannot be used to complete a grouping-proof.Shen et al. [17] only used some simple bitwise operations to propose a practical grouping-proof protocol. But their protocol utilizes serial signature mode so that it takes more time to collect a grouping-proof evidence. Otherwise, an adversary can deduce the group’s key and the tag’s sequence number by eavesdropping the sessions. Hence the protocol cannot preserve the privacy of the system. The protocol does not update the secret keys of the system after each authentication. Therefore the protocol cannot provide forward security.Hong-yan [18] analyzed the grouping-proof protocol proposed by Batina et al. [19] and he found the protocol has some security vulnerability. Then he utilized ECC mechanism to propose an improved grouping-proof protocol. But his protocol cannot provide forward security and it can only complete the grouping-proof for two tags. So it is not suitable for multiple tags.Sun and Mu [20] analyzed the protocol proposed by Liu et al. [12] and found that the attacker can easily launch some attacks such as replay, forgery, tracking, and denial of proof. Although Liu et al. claimed their protocol can resist these well-known attacks, the attacker can effectively compromise all secrets and further impersonate a legal reader or a legal tag.Zhang et al. [21] proposed a scalable grouping-proof protocol. They use the pruning query tree to reduce the collision between tags. Their protocol supposes that the reader is trusted. Before the reader collects the grouping-proof evidence the verifier firstly updates the secret key of the tag. Then the reader sends r2 to the tag. After the tag verifies r2 successfully it updates its secret key. Once r2 is tampered, the tag cannot update its secret key. But the verifier has updated the secret key of the tag and it does not reserve the old secret key of the tag. So the secret key of the tag stored in the verifier is different from the one stored in the tag. Desynchronization attack occurs. Therefore the protocol cannot resist DoS attack.Tsai et al. [22] discussed grouping-proof protocols and ownership transfer protocols, respectively. They found that no protocol has been proposed which can achieve both requirements. So they only proposed a novel ownership transfer protocol to ensure that ownership of the cargo is transferred to the new designated owner.Cherneva and Trahan [23] focus on security, privacy, and efficiency. They proposed a light, improved offline protocol: parallel-dependency grouping-proof protocol. But their protocol does not update any stored secret so as to resist desynchronization attack. So the protocol cannot provide forward security.As analyzed above, many grouping-proof protocols only involve a group of tags rather than multiple tag groups. Sometimes a tag group only contains two tags. When there only exist some untrusted readers near a verifier the grouping-proof protocol cannot be started. Many grouping-proof protocols use serial signature mode to collect a grouping-proof evidence, which remarkably reduces the efficiency of the protocols. In particular, some grouping-proof protocols cannot provide forward security and they are vulnerable to privacy leakage [24].


## 3. RFID System under the Grouping-Proof Mode and Its Security Model

Under the grouping-proof mode, an RFID system usually includes multiple tags. These tags are combined into several groups, as shown in Figure1. A grouping-proof protocol is for a reader to give the evidence that multiple RFID tags exist simultaneously within its broadcast range. There are two classification methods for the grouping-proof protocols:(1)
According to the role of the verifier during the grouping-proof period, the grouping-proof protocols are classified into two different modes: online and offline. For the first mode, the verifier involves the entire grouping-proof process. In contrast, for offline mode, the verifier can only send challenges to the reader and it does not need the persistent presence during the entire grouping-proof period. The efficiency of offline mode is greater than that of online mode. Therefore, many current grouping-proof protocols use offline mode.(2)
According to the sequence for tags to complete their signature, the grouping-proof protocols are classified into two types: serial mode and parallel mode. For the first mode, after one tag finishes its signature another tag begins to sign for generating their grouping-proof evidence. For parallel mode, all tags finish their signatures almost simultaneously. So the grouping-proof protocols under parallel mode are more efficient than those under serial mode.Figure 1
The components of an RFID system under the grouping-proof mode.For an RFID system under the grouping-proof mode, some passive tags are usually used. These tags can only perform some basic cryptographic functions such as pseudorandom number generation and hash operation. We suppose that the verifier is a unique trusted entity and it shares some secrecy with tags. The reader is a potential untrusted entity and it is used to interrogate tags to generate the grouping-proof evidence. Otherwise, we also suppose that the channel between verifier and reader is secure and the channel between reader and tags is insecure. Suppose the verifier and the reader have enough computing and storing resources to complete some advanced cryptographic operations such as asymmetric encryption. For an RFID system under the grouping-proof mode, it should ensure anonymity, confidentiality, and forward security. It can effectively resist privacy leakage, eavesdropping, trace, replay, and desynchronization attack [24].


## 4. Grouping-Proof Protocols with Identity Authentication and Forward Security

As described above, an RFID system under the grouping-proof mode includes three kinds of entities: verifier, reader, and tag. Generally, we suppose that there are a verifier, a reader, and many tags. These tags are divided into several different groups. Each tag group is only identified by its group identifier. Each tag could be represented bytmn/m∈1,2,…,p,n∈1,2,…,q, where tmn represents that the tag is the nth tag of the mth group. When we analyze the security of the protocol an adversary must be introduced. It is usually assumed that an adversary is a probabilistic polynomial time algorithm. An adversary can control each communication channel between reader and tags. He can eavesdrop, intercept, tamper, counterfeit, and replay each session between reader and tags. His main attack goal is to counterfeit a grouping-proof evidence that is verified to be valid by the verifier or to gain the secrecy of the RFID system, such as the secret key and identifier of the tag.The reader is a potential untrusted entity. It is trusted or untrusted. Now two protocols are proposed for the reader with different security level. They utilize parallel signature mode and they are independent of the sequence accessing to tags. So they are very efficient. For the first protocol, we assume that the reader is untrusted. The reader does not know any secret about tags. So the reader cannot authenticate tags. It only collects the grouping-proof evidence and sends the evidence to the verifier. For the second protocol, the reader is assumed to be trusted and it shares some secrets with the verifier and tags. After a reader is authenticated and authorized by the verifier it can begin to collect the grouping-proof evidence. Then it sends the evidence to the verifier.For our proposed protocols, each tag stores its current secret keytkinew, its current identifier tidinew, and its group identifier gid. A trusted reader stores its identifier rid and its secret key rk. rid,rk and tkinew,tidinew,tkiold,tidiold,gid are stored in the verifier. tkiold and tidiold are the last round secret key and identifier of the ith tag. Let hash:0,1d⟶0,1d be a hash function. Let prng:0,1d⟶0,1d be a pseudorandom number generator. d≥32 and it is the bit number of the secret key and the identifier. The verified process is started by the reader. The symbols used in our protocols are shown as Table 1.Table 1
The symbols used in our protocols.
Symbols
Description
gid
The identifier of a tag group
t
k
i
new, tkiold
The current and last round secret key of the tag
t
i
d
i
new, tidiold
The current and last round identifier of the tag
rk, rid
The secret key and identifier of the trusted reader
hash()
A secure hash function
prng()
A pseudorandom number generator
rv, rr, rt
i
Some pseudorandom numbers generated by the different entities
t
The timestamp of the verifier
d
The bit number of the secret key and the identifier
⊕
Bitwise XOR operation


### 4.1. Grouping-Proof Protocol with the Untrusted Reader

For this protocol, an untrusted reader is used to collect a grouping-proof evidence. When the protocol starts a grouping-proof process, the reader first sends “hello” to the verifier. The verifier sends a message to the reader and the message includes the blinded identifier of the verified tag group. Then the reader collects the coexistence evidence of the tag group and sends the evidence to the verifier. At last, the verifier verifies the validness of the evidence. Because all messages that the reader receives are blinded or encrypted, the reader does not know any secret about the tags and the tag group during the entire grouping-proof period.The protocol includes four steps as follows:(1)
A reader notifies the verifier that it will start a grouping-proof process.(2)
The verifier starts a timestamp and sends the blinded identifier of the verified tag group to the reader.(3)
The reader collects a grouping-proof evidence and sends the evidence to the verifier.(4)
If it is not timeout the verifier completes the authentication to the tags and verifies the grouping-proof evidence.The protocol is shown in Figure2 and is described as follows:(1)
The reader sends “hello” to the verifier.(2)
The verifier stores its current clock tot and starts a timestamp. It generates a pseudorandom number rv=prngt. Then it uses the verified group’s identifier gid to generate the message m1=hashgid⊕rv and sends m1rv to the reader.(3)
After the reader receivesm1rv, it broadcasts m1rv to all tags near it.(4)
After each tag receivesm1rv, it uses its gid to compute tm1=hashgid⊕rv. If tm1=m1 holds, it becomes active. Otherwise, it becomes sleep. The process described above is called the activate-sleep mechanism. Later, only the active tags respond to the reader.(5)
For theith active tag, it firstly generates a pseudorandom number rti=prngrv⊕tki. Then it uses its tki and tidi to generate m2i=hashtki⊕rti and m3i=hashtidi⊕rti, and it sends m2im3irti to the reader.(6)
After the reader receivesm2im3irti (i∈1,2,…,k) from each active tag, it calculates mp=hashm21⊕m22⊕…⊕m2k and broadcasts mp to each active tag. k is the total number of the active tags.(7)
After each active tag receivesmp, it signs mp with its secret key tki and generates tpi=hashtki⊕mp. Then it sends tpi to the reader.(8)
After the reader receivestpii∈1,2,…,k from each active tag, it calculates p=hashtp1⊕tp2⊕…⊕tpk. Then it generates the grouping-proof evidence gp=rt1,m21,m31,rt2,m22,m32,…,rtk,m2k,m3k,mp,p and sends gp to the verifier.(9)
After the verifier receivesgp, it firstly judges whether it is timeout. If it is timeout, the protocol exits. Otherwise, the protocol goes to the next step.(10)
The verifier calculatestm2i=hashtkix⊕rti and tm3i=hashtidix⊕rti for ∀x∈new,old and i∈1,2,…,k. If tm2i=m2i and tm3i=m3i hold for ∀i∈1,2,…,k, the verifier completes the authentication to each active tag and begins to verify gp. Otherwise, the protocol fails and exits.(11)
The verifier uses its stored secret information about each active tag and the receivedrti to calculate mp and p. If they equal the received values, the verifier verifies gp successfully and the protocol goes to the next step. Otherwise, the protocol fails and exits.(12)
The verifier generates the messagem4i=hashtkix⊕tidix⊕rv⊕rti. It begins to update its secrets. If x=old holds, let tkinew=prngtkiold⊕rv⊕rti and tidinew=prngtidiold⊕rv⊕rti. If x=new holds, let tkiold=tkinew and tidiold=tidinew, tkinew=prngtkinew⊕rv⊕rti, and tidinew=prngtidinew⊕rv⊕rti. Then the verifier broadcasts m4irti to each active tag by the reader. rti is used to state that m4irti is to send the ith tag and other tags do not respond to the message, although they receive the message, which is called the filtering operation.(13)
After each active tag receivesm4irti, it compares its rti with the received rti. If they are not equal, the tag discards the message. Or the tag calculates tm4=hashtki⊕tidi⊕rv⊕rti. Then it compares tm4 with m4i. If they are equal, it updates its secrets: tki=prngtki⊕rv⊕rti and tidi=prngtidi⊕rv⊕rti.Figure 2
The grouping-proof protocol with the untrusted reader.


### 4.2. Grouping-Proof Protocol with the Trusted Reader

For this protocol, a trusted reader is used to collect a grouping-proof evidence. The reader stores its identifierrid and its secret key rk, which are also stored in the verifier. When a trusted reader begins to collect a grouping-proof evidence, it first completes the mutual authentication with the verifier. If the authentication succeeds, the verifier sends the related information of the verified group to the reader and the information includes the secret key and identifier of the verified tags. Then the reader begins to collect the coexistence evidence of the tags and sends the evidence to the verifier.The protocol includes the following steps:(1)
The reader notifies the verifier and it will start a grouping-proof.(2)
The verifier completes the mutual authentication with the reader and authorizes it.(3)
The verifier starts a timestamp and sends the related information of the verified tags to the reader.(4)
The reader completes the first authentication to each verified tag, collects a grouping-proof evidence, and sends the evidence to the verifier.(5)
If it is not timeout, the verifier completes the second authentication to each verified tag. Then it begins to verify the grouping-proof evidence and updates its secrets.(6)
The verifier notifies the related tags to update their secrets.The protocol includes three phases. The first phase completes the authentication and authorization of the verifier to the reader. It is shown in Figure3 and is described as follows:(1)
The reader sends “hello” to the verifier.(2)
The verifier stores its current clock tot, starts a timestamp, and generates a pseudorandom number rv=prngt. It sends rv to the reader.(3)
The reader generates a pseudorandom numberrr=prngrv⊕rk and a message m1=hashrid⊕rr. It sends rrm1 to the verifier.(4)
The verifier usesrid, which is stored in its database, to generate tm1=hashrid⊕rr. If m1=tm1 holds, it completes the authentication to the reader. Then it generates m2=hashrk⊕rv⊕rr and sends m2 to the reader. Otherwise, the protocol fails and exits.(5)
The reader uses itsrk to generate tm2=hashrk⊕rv⊕rr and compares tm2 with m2. If they are equal, the reader completes the authentication to the verifier. Then it generates m3=hashrk⊕rr and sends m3 to the verifier. If they are unequal, the protocol fails and exits.(6)
The verifier uses itsrk, which is stored in its database, to compute tm3=hashrk⊕rr and compares tm3 with m3. If they are equal, the verifier completes the mutual authentication with the reader. If they are unequal, the protocol fails and exits.(7)
After the verifier completes the mutual authentication with the reader, it transferstkix,tidix of each verified tag and the verified group identifier gid to the reader by a secure channel or a secure cryptographic primitive, wherex∈new,old; i∈1,2,…,k, k is the total number of the verified tags. The reader is authorized to collect a grouping-proof evidence.Figure 3
The authentication and authorization of the verifier to the reader.In the second phase, the reader wakes up the related tags and completes the first authentication to each verified tag. It is shown in Figure4 and is described as follows:(1)
The reader generates the messagem4=hashgid⊕rr and broadcasts m4rrrv to each tag near it.(2)
After a tag receivesm4rrrv, it uses its gid to generate tm4=hashgid⊕rr. If m4=tm4 holds, it remains active. Otherwise, it becomes sleep.(3)
For theith active tag, it generates a pseudorandom number rti=prngtki⊕rr and two messages mk5i=hashtki⊕rti and mid5i=hashtidi⊕rti and sends mk5imid5irti to the reader.(4)
The reader uses the secret information from the verifier and calculatestmk5i=hashtkix⊕rti and tmid5i=hashtidix⊕rti, where x∈new,old and i∈1,2,…,k. If tmk5i=mk5i and tmid5i=mid5i hold for ∀i∈1,2,…,k, the reader completes the first authentication to each active tag. Otherwise, the protocol fails and exits.(5)
Once the reader completes the authentication to each active tag, it begins to collect the grouping-proof evidence and enter the verification period.Figure 4
The reader authenticates each verified tag.The third phase completes the collection and verification of the grouping-proof evidence. It is shown in Figure5 and is described as follows:(1)
The reader calculatesmp=hashmk51⊕mk52⊕…⊕mk5k and broadcasts mp to each active tag.(2)
After each active tag receivesmp, it signs mp with its secret key tki and generates tpi=hashtki⊕mp. Then it sends tpi to the reader.(3)
After the reader receives eachtpi it calculates p=hashtp1⊕tp2⊕…⊕tpk. Then it generates the grouping-proof evidence gp=rt1,mk51,mid51,…,rtk,mk5k,mid5k,mp,p and sends gp to the verifier.(4)
After the verifier receivesgp, it firstly judges whether it is timeout. If it is timeout, the protocol exits. Otherwise, the protocol goes to the next step.(5)
The verifier utilizes its stored secret information about tags and the receivedrti to calculate vmki=hashtkix⊕rti and vmidi=hashtidix⊕rti for ∀i∈1,2,…,k. If vmki=mk5i and vmidi=mid5i hold for ∀i∈1,2,…,k, the verifier completes the second authentication to the verified tags and it begins to verify gp. Otherwise, the protocol fails and exits.(6)
The verifier generatesvmp=hashvmk51⊕vmk52⊕…⊕vmk5k and calculates vtpi=hashtki⊕vmp for ∀i∈1,2,…,k. Finally it generates vp=hashvtp1⊕vtp2⊕…⊕vtpk. If vmp=mp and vp=p hold, the verifier gets a valid grouping-proof evidence.(7)
After the verifier verifiesgp successfully, it generates the message, m6i=hashtkix⊕tidix⊕rti for ∀i∈1,2,…,k, and updates its secrets. If x=old holds, let tkinew=prngtkiold⊕rv⊕rti and tidinew=prngtidiold⊕rv⊕rti. If x=new holds, let tkiold=tkinew, tidiold=tidinew, tkinew=prngtkinew⊕rv⊕rti, and tidinew=prngtidinew⊕rv⊕rti. Then the verifier broadcasts m6irti to each active tag through the reader.(8)
After an active tag receivesm6irti, it compares its rti with the received rti. If they are equal, the tag calculates tm6=hashtki⊕tidi⊕rti. If m6i=tm6 holds, it updates its secrets: tki=prngtki⊕rv⊕rti and tidi=prngtidi⊕rv⊕rti.Figure 5
The generation and verification of the grouping-proof evidence.


## 4.1. Grouping-Proof Protocol with the Untrusted Reader

For this protocol, an untrusted reader is used to collect a grouping-proof evidence. When the protocol starts a grouping-proof process, the reader first sends “hello” to the verifier. The verifier sends a message to the reader and the message includes the blinded identifier of the verified tag group. Then the reader collects the coexistence evidence of the tag group and sends the evidence to the verifier. At last, the verifier verifies the validness of the evidence. Because all messages that the reader receives are blinded or encrypted, the reader does not know any secret about the tags and the tag group during the entire grouping-proof period.The protocol includes four steps as follows:(1)
A reader notifies the verifier that it will start a grouping-proof process.(2)
The verifier starts a timestamp and sends the blinded identifier of the verified tag group to the reader.(3)
The reader collects a grouping-proof evidence and sends the evidence to the verifier.(4)
If it is not timeout the verifier completes the authentication to the tags and verifies the grouping-proof evidence.The protocol is shown in Figure2 and is described as follows:(1)
The reader sends “hello” to the verifier.(2)
The verifier stores its current clock tot and starts a timestamp. It generates a pseudorandom number rv=prngt. Then it uses the verified group’s identifier gid to generate the message m1=hashgid⊕rv and sends m1rv to the reader.(3)
After the reader receivesm1rv, it broadcasts m1rv to all tags near it.(4)
After each tag receivesm1rv, it uses its gid to compute tm1=hashgid⊕rv. If tm1=m1 holds, it becomes active. Otherwise, it becomes sleep. The process described above is called the activate-sleep mechanism. Later, only the active tags respond to the reader.(5)
For theith active tag, it firstly generates a pseudorandom number rti=prngrv⊕tki. Then it uses its tki and tidi to generate m2i=hashtki⊕rti and m3i=hashtidi⊕rti, and it sends m2im3irti to the reader.(6)
After the reader receivesm2im3irti (i∈1,2,…,k) from each active tag, it calculates mp=hashm21⊕m22⊕…⊕m2k and broadcasts mp to each active tag. k is the total number of the active tags.(7)
After each active tag receivesmp, it signs mp with its secret key tki and generates tpi=hashtki⊕mp. Then it sends tpi to the reader.(8)
After the reader receivestpii∈1,2,…,k from each active tag, it calculates p=hashtp1⊕tp2⊕…⊕tpk. Then it generates the grouping-proof evidence gp=rt1,m21,m31,rt2,m22,m32,…,rtk,m2k,m3k,mp,p and sends gp to the verifier.(9)
After the verifier receivesgp, it firstly judges whether it is timeout. If it is timeout, the protocol exits. Otherwise, the protocol goes to the next step.(10)
The verifier calculatestm2i=hashtkix⊕rti and tm3i=hashtidix⊕rti for ∀x∈new,old and i∈1,2,…,k. If tm2i=m2i and tm3i=m3i hold for ∀i∈1,2,…,k, the verifier completes the authentication to each active tag and begins to verify gp. Otherwise, the protocol fails and exits.(11)
The verifier uses its stored secret information about each active tag and the receivedrti to calculate mp and p. If they equal the received values, the verifier verifies gp successfully and the protocol goes to the next step. Otherwise, the protocol fails and exits.(12)
The verifier generates the messagem4i=hashtkix⊕tidix⊕rv⊕rti. It begins to update its secrets. If x=old holds, let tkinew=prngtkiold⊕rv⊕rti and tidinew=prngtidiold⊕rv⊕rti. If x=new holds, let tkiold=tkinew and tidiold=tidinew, tkinew=prngtkinew⊕rv⊕rti, and tidinew=prngtidinew⊕rv⊕rti. Then the verifier broadcasts m4irti to each active tag by the reader. rti is used to state that m4irti is to send the ith tag and other tags do not respond to the message, although they receive the message, which is called the filtering operation.(13)
After each active tag receivesm4irti, it compares its rti with the received rti. If they are not equal, the tag discards the message. Or the tag calculates tm4=hashtki⊕tidi⊕rv⊕rti. Then it compares tm4 with m4i. If they are equal, it updates its secrets: tki=prngtki⊕rv⊕rti and tidi=prngtidi⊕rv⊕rti.Figure 2
The grouping-proof protocol with the untrusted reader.


## 4.2. Grouping-Proof Protocol with the Trusted Reader

For this protocol, a trusted reader is used to collect a grouping-proof evidence. The reader stores its identifierrid and its secret key rk, which are also stored in the verifier. When a trusted reader begins to collect a grouping-proof evidence, it first completes the mutual authentication with the verifier. If the authentication succeeds, the verifier sends the related information of the verified group to the reader and the information includes the secret key and identifier of the verified tags. Then the reader begins to collect the coexistence evidence of the tags and sends the evidence to the verifier.The protocol includes the following steps:(1)
The reader notifies the verifier and it will start a grouping-proof.(2)
The verifier completes the mutual authentication with the reader and authorizes it.(3)
The verifier starts a timestamp and sends the related information of the verified tags to the reader.(4)
The reader completes the first authentication to each verified tag, collects a grouping-proof evidence, and sends the evidence to the verifier.(5)
If it is not timeout, the verifier completes the second authentication to each verified tag. Then it begins to verify the grouping-proof evidence and updates its secrets.(6)
The verifier notifies the related tags to update their secrets.The protocol includes three phases. The first phase completes the authentication and authorization of the verifier to the reader. It is shown in Figure3 and is described as follows:(1)
The reader sends “hello” to the verifier.(2)
The verifier stores its current clock tot, starts a timestamp, and generates a pseudorandom number rv=prngt. It sends rv to the reader.(3)
The reader generates a pseudorandom numberrr=prngrv⊕rk and a message m1=hashrid⊕rr. It sends rrm1 to the verifier.(4)
The verifier usesrid, which is stored in its database, to generate tm1=hashrid⊕rr. If m1=tm1 holds, it completes the authentication to the reader. Then it generates m2=hashrk⊕rv⊕rr and sends m2 to the reader. Otherwise, the protocol fails and exits.(5)
The reader uses itsrk to generate tm2=hashrk⊕rv⊕rr and compares tm2 with m2. If they are equal, the reader completes the authentication to the verifier. Then it generates m3=hashrk⊕rr and sends m3 to the verifier. If they are unequal, the protocol fails and exits.(6)
The verifier uses itsrk, which is stored in its database, to compute tm3=hashrk⊕rr and compares tm3 with m3. If they are equal, the verifier completes the mutual authentication with the reader. If they are unequal, the protocol fails and exits.(7)
After the verifier completes the mutual authentication with the reader, it transferstkix,tidix of each verified tag and the verified group identifier gid to the reader by a secure channel or a secure cryptographic primitive, wherex∈new,old; i∈1,2,…,k, k is the total number of the verified tags. The reader is authorized to collect a grouping-proof evidence.Figure 3
The authentication and authorization of the verifier to the reader.In the second phase, the reader wakes up the related tags and completes the first authentication to each verified tag. It is shown in Figure4 and is described as follows:(1)
The reader generates the messagem4=hashgid⊕rr and broadcasts m4rrrv to each tag near it.(2)
After a tag receivesm4rrrv, it uses its gid to generate tm4=hashgid⊕rr. If m4=tm4 holds, it remains active. Otherwise, it becomes sleep.(3)
For theith active tag, it generates a pseudorandom number rti=prngtki⊕rr and two messages mk5i=hashtki⊕rti and mid5i=hashtidi⊕rti and sends mk5imid5irti to the reader.(4)
The reader uses the secret information from the verifier and calculatestmk5i=hashtkix⊕rti and tmid5i=hashtidix⊕rti, where x∈new,old and i∈1,2,…,k. If tmk5i=mk5i and tmid5i=mid5i hold for ∀i∈1,2,…,k, the reader completes the first authentication to each active tag. Otherwise, the protocol fails and exits.(5)
Once the reader completes the authentication to each active tag, it begins to collect the grouping-proof evidence and enter the verification period.Figure 4
The reader authenticates each verified tag.The third phase completes the collection and verification of the grouping-proof evidence. It is shown in Figure5 and is described as follows:(1)
The reader calculatesmp=hashmk51⊕mk52⊕…⊕mk5k and broadcasts mp to each active tag.(2)
After each active tag receivesmp, it signs mp with its secret key tki and generates tpi=hashtki⊕mp. Then it sends tpi to the reader.(3)
After the reader receives eachtpi it calculates p=hashtp1⊕tp2⊕…⊕tpk. Then it generates the grouping-proof evidence gp=rt1,mk51,mid51,…,rtk,mk5k,mid5k,mp,p and sends gp to the verifier.(4)
After the verifier receivesgp, it firstly judges whether it is timeout. If it is timeout, the protocol exits. Otherwise, the protocol goes to the next step.(5)
The verifier utilizes its stored secret information about tags and the receivedrti to calculate vmki=hashtkix⊕rti and vmidi=hashtidix⊕rti for ∀i∈1,2,…,k. If vmki=mk5i and vmidi=mid5i hold for ∀i∈1,2,…,k, the verifier completes the second authentication to the verified tags and it begins to verify gp. Otherwise, the protocol fails and exits.(6)
The verifier generatesvmp=hashvmk51⊕vmk52⊕…⊕vmk5k and calculates vtpi=hashtki⊕vmp for ∀i∈1,2,…,k. Finally it generates vp=hashvtp1⊕vtp2⊕…⊕vtpk. If vmp=mp and vp=p hold, the verifier gets a valid grouping-proof evidence.(7)
After the verifier verifiesgp successfully, it generates the message, m6i=hashtkix⊕tidix⊕rti for ∀i∈1,2,…,k, and updates its secrets. If x=old holds, let tkinew=prngtkiold⊕rv⊕rti and tidinew=prngtidiold⊕rv⊕rti. If x=new holds, let tkiold=tkinew, tidiold=tidinew, tkinew=prngtkinew⊕rv⊕rti, and tidinew=prngtidinew⊕rv⊕rti. Then the verifier broadcasts m6irti to each active tag through the reader.(8)
After an active tag receivesm6irti, it compares its rti with the received rti. If they are equal, the tag calculates tm6=hashtki⊕tidi⊕rti. If m6i=tm6 holds, it updates its secrets: tki=prngtki⊕rv⊕rti and tidi=prngtidi⊕rv⊕rti.Figure 5
The generation and verification of the grouping-proof evidence.


## 5. Security and Efficiency Analysis of Our Proposed Protocols

For an RFID system under the grouping-proof mode, A is assumed to be a probabilistic polynomial time adversary. He can eavesdrop, intercept, tamper, counterfeit, and replay each session between reader and tags. He can counterfeit a grouping-proof evidence and transfer it to the verifier in limited time. If the evidence is successfully verified by the verifier, adversary A is considered to win.Definition 1.
Adversary A can continuously issue the oracle queries toprng and hash. The output of prng and hash is d bits. Let σ denote the probability that the adversary guesses successfully the output of the functions. Then we have σ≤2−d.Definition 2.
For a probabilistic polynomial time adversary A, letσ be the probability that he reveals the secret information of an RFID system. If σ is negligible the grouping-proof protocol is considered to be privacy-secure.Definition 3.
For a probabilistic polynomial time adversary A, letσ denote the probability that he distinguishes two different tags. σ is defined as follows:(1)σ=2Prtidm=tidn−1where m≠n. If σ is negligible, the grouping-proof protocol is considered to be indistinguishable-secure.Definition 4.
For a probabilistic polynomial time adversary A, a grouping-proof protocol is defined to be forward-secure if and only if he cannot decrypt any previous session, although he has acquired the current secret key of the RFID system. Letσ denote the probability that he could derive the previous secret key from the current secret key of the protocol. If σ is negligible and the adversary cannot decrypt the previous sessions, the grouping-proof protocol is considered to be forward-secure.


### 5.1. Security Analysis to the Grouping-Proof Protocol with the Untrusted Reader

For the first grouping-proof protocol proposed by us, an untrusted reader is involved. We assume that an adversary A easily disguises a legal reader to communicate with the verifier or the tags. He can intercept each session from the RFID system, such asm2im3irti, tpi and m4irti. On the one hand, m2i, rti, tpi, and m4i are four messages that include the secret key tki of the ith tag. Suppose adversary A intercepts these messages. Let ε1 denote the probability that adversary A guesses tki from the messages. We have ε1≤2−32×4=2−30. On the other hand, m3i and m4i are two messages that include the identifier tidi of the ith tag. Let ε2 denote the probability that adversary A guesses tidi from the messages. We have ε2≤2−32×2=2−31. It is obvious that ε1 and ε2 are negligible. It means that it is very difficult for the adversary to guess any secret information from the intercepted sessions. Therefore the protocol is privacy-secure.For a probabilistic polynomial time adversary A, we assume that he can intercept each session from tags. Suppose the adversary interceptsm3m and m3n from the mth and nth tag, where m,n∈1,2,…,k and m≠n. If the adversary can distinguish these two tags, his successful probability can be defined as follows [25]:(2)Prtidm=tidn=2−1+εwhere ε is the probability that the adversary can guess tidm and tidn simultaneously. By Definition 1, we have ε≤2−d×2−d. When d≥32, we have ε≤2−64. By Definition 3, we have σ=2Prtidm=tidn−1=2ε≤2−63. Therefore σ is negligible. The grouping-proof protocol is indistinguishable-secure.For our proposed grouping-proof protocol with an untrusted reader,m2i, rti, tpi, and m4i are four messages that include the secret key tki of the ith tag. Suppose adversary A intercepts these messages. Let ε1 denote the probability that adversary A guesses tki successfully from the messages. We have ε1≤2−32×4=2−30. After each successful grouping-proof, the secret key of each tag is updated by tkinew=prngtkinew⊕rv⊕rti. If the adversary wants to get the last round secret key it has to issue the oracle query to prng. Suppose the adversary can deduce the last round secret key from the current secret key by querying prng. His successful probability is ε2. Then we have ε2≤2−32. There are two cases:(1)
The adversary does not corrupt theith tag and it does not know the current secret key tki. Firstly, the adversary has to guess the current secret key from the intercepted sessions. Then he guesses the previous secret key from the guessed current secret key by issuing the random queries to prng. Let σ1 be the probability that the adversary guesses the last round secret key. We have σ1=ε1×ε2≤2−30×2−32=2−62.(2)
The adversary corrupts theith tag and it gets the current secret key tki; he can guess the last round secret key only by issuing the oracle queries to prng. Let σ2 be the probability that the adversary wins. Then we have σ2=ε2≤2−32.It is obvious thatσ1 and σ2 are negligible. The adversary cannot guess the last round secret key from the current secret key. So he cannot reveal the previous sessions and the grouping-proof protocol is forward-secure.


### 5.2. Security Analysis to the Grouping-Proof Protocol with the Trusted Reader

The second grouping-proof protocol proposed by us involves a trusted reader. Under this circumstance, the verifier and the reader can use some complicated cryptographic primitives to ensure the confidential communication between them. So we assume that the communication between verifier and reader is secure. An adversary can only intercept sessions between reader and tags. If adversary A wants to guess the secret key and identifier of tags from the intercepted sessions it has to issue the oracle queries tohash and prng. On the one hand, rti, mk5i, tpi, and m6i include the secret key tki of the ith tag. Let σ denote the probability that an adversary successfully guesses the secret key of the tag from these sessions and we have σ≤4×2−32=2−30. It is obvious that σ is negligible. On the other hand, only mid5i and m6i include the identifier tidi of the ith tag. Suppose an adversary can guess the identifier by issuing the oracle queries to hash. Let σ be the probability that he wins by querying mid5i and m6i. Then we have σ≤2×2−32=2−31. It is obvious that σ is also negligible. So our proposed protocol is privacy-secure.Adversary A can distinguish two different tags by intercepting some sessions that include the identifier of these tags. We assume that adversary A interceptsmid5m and mid5n from the mth and nth tag, where m,n∈1,2,…,k and m≠n. If A can distinguish these two tags, his successful probability is defined by equation (2). As discussed in the last subsection, we have ε≤2−d×2−d. When d≥32, we have ε≤2−64. By Definition 3, we have σ=2Prtidm=tidn−1=2ε≤2−63. So σ is negligible and our grouping-proof protocol is indistinguishable-secure.Now we discuss the forward security of the protocol. For our proposed grouping-proof protocol with the trusted reader,rti, mk5i, tpi, and m6i are some sessions that include the secret key tki to the ith tag. Suppose adversary A can intercept these sessions. He can issue any oracle query to hash and prng. ε1 is the probability that he can guess tki from the messages described above. We have ε1≤4×2−32=2−30. After each successful grouping-proof, the secret key to each tag is updated by tkinew=prngtkinew⊕rv⊕rti. If the adversary wants to get the last round secret key he has to issue the oracle query to prng. Let ε2 denote the probability that the adversary guesses the last round secret key from the current secret key by issuing the random queries to prng. We have ε2≤2−32. There exist two cases as described in the last subsection. The probability that the adversary gains the last round secret key from the current secret key is negligible. The adversary cannot guess the previous secret key from the current secret key. So he cannot decrypt the previous sessions and the grouping-proof protocol is forward-secure.


### 5.3. Resistance to Other Attacks

In addition to resisting the attacks described above, our proposed grouping-proof protocols can also resist eavesdropping attack, replay attack, and desynchronized attack.(i)
Eavesdropping: during the grouping-proof period, all session messages, which include the secret information of the RFID system, are generated byhash or randomized by prng. An adversary can intercept each session from the protocol. But he cannot reveal any secret information about the tag and the tag group from the intercepted sessions. Eavesdropping to the communication channels is invalid.(ii)
Interleaving and replay attack: this type of attack means that an adversary replays the grouping-proof evidence that he intercepted and the replayed evidence can be successfully verified by the verifier. The intercepted evidence may be from the same or different grouping-proof process. In order to prevent interleaving and replay attack, the clock of the verifier is utilized as timestamp and seed to generate some pseudorandom numbers. These pseudorandom numbers are different for different grouping-proof processes and they are utilized to randomize the sessions between reader and tags. On the one hand, the sessions from the same grouping-proof process can be replayed later. But they are timeout and they cannot be verified successfully. So our protocols can resist replay attack. On the other hand, the sessions from the different grouping-proof processes include the different timestamps. So they cannot be combined to construct any valid grouping-proof evidence. Hence our protocols can resist interleaving attack.(iii)
Desynchronization: in order to resist desynchronization attack, our protocols reserve the last round secrecy and the current secrecy in the verifier when the secrecy of the RFID system is updated. An adversary can tamper or blockm6i||rti so that the tag cannot update its current secrecy. But the verifier reserves the last round secrecy and it can use this secrecy to communicate with tags. So our protocols can complete the grouping-proof regardless of whether the tag updates its current secrecy. The protocol can avoid desynchronization attack.


### 5.4. Analysis to the Efficiency of Our Proposed Protocols

In order to avoid the collision between tags and reduce the computing load of the RFID system, the novel activate-sleep mechanism and the special filtering operation are proposed for our grouping-proof protocols.(i)
The activate-sleep mechanism: for our protocols, maybe there exist many tag groups. Each tag group is only identified by its group identifiergid. Before our protocols begin to authenticate tags and generate the grouping-proof evidence, the reader sends the message m1 or m4 to each tag group so that the tags with other group identifiers become sleep. During the later period of the protocol, only the tags with the group identifier gid can communicate with the reader. When there exist many tag groups, the collision probability between tags is reduced remarkably. Otherwise, the reader only receives the messages from the objective group and other tag groups do not send any message to it. Its processing load is reduced efficiently.(ii)
The filtering operation: the computing ability of tags is very limited. So it is necessary to reduce the computing load of tags. For our grouping-proof protocols, the reader uses the broadcast channel to communicate with tags. But sometimes the reader sends a message only to one tag (e.g.,m6irti in Figure 5). In order to complete the peer-to-peer communication through the RFID broadcast channel, the theorem of the data link layer of Ethernet is utilized. rti is defined as MAC address of the ith tag. The message that is only sent to the ith tag is attached with rti. After a tag receives the messages, it first recognizes whether the received rti equals its stored rti. After the tag is sure that the received message is sent to it, it calls hash to calculate m6i. Therefore the computing load of the tag is reduced remarkably.The comparison of our proposed protocols with some typical grouping-proof protocols is shown in Table2.Table 2
The comparison of some typical grouping-proof protocols with our protocols.
Protocols
Privacy
Anonymity
Trace attack
Replay attack
Forward security
DoS attack
The number of tag groups
Ref. [2]
✕
✕
✕
✕
✕
—
One (only two tags)
Ref. [15]
✓
✓
✓
✓
✓
✕
One
Ref. [16]
✕
✕
✕
✓
✓
✕
Multiple
Ref. [18]
✓
✓
✓
✓
✕
—
One (only two tags)
Ref. [19]
✓
✓
✕
✓
✕
—
One (only two tags)
Ours
✓
✓
✓
✓
✓
✓
Multiple


## 5.1. Security Analysis to the Grouping-Proof Protocol with the Untrusted Reader

For the first grouping-proof protocol proposed by us, an untrusted reader is involved. We assume that an adversary A easily disguises a legal reader to communicate with the verifier or the tags. He can intercept each session from the RFID system, such asm2im3irti, tpi and m4irti. On the one hand, m2i, rti, tpi, and m4i are four messages that include the secret key tki of the ith tag. Suppose adversary A intercepts these messages. Let ε1 denote the probability that adversary A guesses tki from the messages. We have ε1≤2−32×4=2−30. On the other hand, m3i and m4i are two messages that include the identifier tidi of the ith tag. Let ε2 denote the probability that adversary A guesses tidi from the messages. We have ε2≤2−32×2=2−31. It is obvious that ε1 and ε2 are negligible. It means that it is very difficult for the adversary to guess any secret information from the intercepted sessions. Therefore the protocol is privacy-secure.For a probabilistic polynomial time adversary A, we assume that he can intercept each session from tags. Suppose the adversary interceptsm3m and m3n from the mth and nth tag, where m,n∈1,2,…,k and m≠n. If the adversary can distinguish these two tags, his successful probability can be defined as follows [25]:(2)Prtidm=tidn=2−1+εwhere ε is the probability that the adversary can guess tidm and tidn simultaneously. By Definition 1, we have ε≤2−d×2−d. When d≥32, we have ε≤2−64. By Definition 3, we have σ=2Prtidm=tidn−1=2ε≤2−63. Therefore σ is negligible. The grouping-proof protocol is indistinguishable-secure.For our proposed grouping-proof protocol with an untrusted reader,m2i, rti, tpi, and m4i are four messages that include the secret key tki of the ith tag. Suppose adversary A intercepts these messages. Let ε1 denote the probability that adversary A guesses tki successfully from the messages. We have ε1≤2−32×4=2−30. After each successful grouping-proof, the secret key of each tag is updated by tkinew=prngtkinew⊕rv⊕rti. If the adversary wants to get the last round secret key it has to issue the oracle query to prng. Suppose the adversary can deduce the last round secret key from the current secret key by querying prng. His successful probability is ε2. Then we have ε2≤2−32. There are two cases:(1)
The adversary does not corrupt theith tag and it does not know the current secret key tki. Firstly, the adversary has to guess the current secret key from the intercepted sessions. Then he guesses the previous secret key from the guessed current secret key by issuing the random queries to prng. Let σ1 be the probability that the adversary guesses the last round secret key. We have σ1=ε1×ε2≤2−30×2−32=2−62.(2)
The adversary corrupts theith tag and it gets the current secret key tki; he can guess the last round secret key only by issuing the oracle queries to prng. Let σ2 be the probability that the adversary wins. Then we have σ2=ε2≤2−32.It is obvious thatσ1 and σ2 are negligible. The adversary cannot guess the last round secret key from the current secret key. So he cannot reveal the previous sessions and the grouping-proof protocol is forward-secure.


## 5.2. Security Analysis to the Grouping-Proof Protocol with the Trusted Reader

The second grouping-proof protocol proposed by us involves a trusted reader. Under this circumstance, the verifier and the reader can use some complicated cryptographic primitives to ensure the confidential communication between them. So we assume that the communication between verifier and reader is secure. An adversary can only intercept sessions between reader and tags. If adversary A wants to guess the secret key and identifier of tags from the intercepted sessions it has to issue the oracle queries tohash and prng. On the one hand, rti, mk5i, tpi, and m6i include the secret key tki of the ith tag. Let σ denote the probability that an adversary successfully guesses the secret key of the tag from these sessions and we have σ≤4×2−32=2−30. It is obvious that σ is negligible. On the other hand, only mid5i and m6i include the identifier tidi of the ith tag. Suppose an adversary can guess the identifier by issuing the oracle queries to hash. Let σ be the probability that he wins by querying mid5i and m6i. Then we have σ≤2×2−32=2−31. It is obvious that σ is also negligible. So our proposed protocol is privacy-secure.Adversary A can distinguish two different tags by intercepting some sessions that include the identifier of these tags. We assume that adversary A interceptsmid5m and mid5n from the mth and nth tag, where m,n∈1,2,…,k and m≠n. If A can distinguish these two tags, his successful probability is defined by equation (2). As discussed in the last subsection, we have ε≤2−d×2−d. When d≥32, we have ε≤2−64. By Definition 3, we have σ=2Prtidm=tidn−1=2ε≤2−63. So σ is negligible and our grouping-proof protocol is indistinguishable-secure.Now we discuss the forward security of the protocol. For our proposed grouping-proof protocol with the trusted reader,rti, mk5i, tpi, and m6i are some sessions that include the secret key tki to the ith tag. Suppose adversary A can intercept these sessions. He can issue any oracle query to hash and prng. ε1 is the probability that he can guess tki from the messages described above. We have ε1≤4×2−32=2−30. After each successful grouping-proof, the secret key to each tag is updated by tkinew=prngtkinew⊕rv⊕rti. If the adversary wants to get the last round secret key he has to issue the oracle query to prng. Let ε2 denote the probability that the adversary guesses the last round secret key from the current secret key by issuing the random queries to prng. We have ε2≤2−32. There exist two cases as described in the last subsection. The probability that the adversary gains the last round secret key from the current secret key is negligible. The adversary cannot guess the previous secret key from the current secret key. So he cannot decrypt the previous sessions and the grouping-proof protocol is forward-secure.


## 5.3. Resistance to Other Attacks

In addition to resisting the attacks described above, our proposed grouping-proof protocols can also resist eavesdropping attack, replay attack, and desynchronized attack.(i)
Eavesdropping: during the grouping-proof period, all session messages, which include the secret information of the RFID system, are generated byhash or randomized by prng. An adversary can intercept each session from the protocol. But he cannot reveal any secret information about the tag and the tag group from the intercepted sessions. Eavesdropping to the communication channels is invalid.(ii)
Interleaving and replay attack: this type of attack means that an adversary replays the grouping-proof evidence that he intercepted and the replayed evidence can be successfully verified by the verifier. The intercepted evidence may be from the same or different grouping-proof process. In order to prevent interleaving and replay attack, the clock of the verifier is utilized as timestamp and seed to generate some pseudorandom numbers. These pseudorandom numbers are different for different grouping-proof processes and they are utilized to randomize the sessions between reader and tags. On the one hand, the sessions from the same grouping-proof process can be replayed later. But they are timeout and they cannot be verified successfully. So our protocols can resist replay attack. On the other hand, the sessions from the different grouping-proof processes include the different timestamps. So they cannot be combined to construct any valid grouping-proof evidence. Hence our protocols can resist interleaving attack.(iii)
Desynchronization: in order to resist desynchronization attack, our protocols reserve the last round secrecy and the current secrecy in the verifier when the secrecy of the RFID system is updated. An adversary can tamper or blockm6i||rti so that the tag cannot update its current secrecy. But the verifier reserves the last round secrecy and it can use this secrecy to communicate with tags. So our protocols can complete the grouping-proof regardless of whether the tag updates its current secrecy. The protocol can avoid desynchronization attack.


## 5.4. Analysis to the Efficiency of Our Proposed Protocols

In order to avoid the collision between tags and reduce the computing load of the RFID system, the novel activate-sleep mechanism and the special filtering operation are proposed for our grouping-proof protocols.(i)
The activate-sleep mechanism: for our protocols, maybe there exist many tag groups. Each tag group is only identified by its group identifiergid. Before our protocols begin to authenticate tags and generate the grouping-proof evidence, the reader sends the message m1 or m4 to each tag group so that the tags with other group identifiers become sleep. During the later period of the protocol, only the tags with the group identifier gid can communicate with the reader. When there exist many tag groups, the collision probability between tags is reduced remarkably. Otherwise, the reader only receives the messages from the objective group and other tag groups do not send any message to it. Its processing load is reduced efficiently.(ii)
The filtering operation: the computing ability of tags is very limited. So it is necessary to reduce the computing load of tags. For our grouping-proof protocols, the reader uses the broadcast channel to communicate with tags. But sometimes the reader sends a message only to one tag (e.g.,m6irti in Figure 5). In order to complete the peer-to-peer communication through the RFID broadcast channel, the theorem of the data link layer of Ethernet is utilized. rti is defined as MAC address of the ith tag. The message that is only sent to the ith tag is attached with rti. After a tag receives the messages, it first recognizes whether the received rti equals its stored rti. After the tag is sure that the received message is sent to it, it calls hash to calculate m6i. Therefore the computing load of the tag is reduced remarkably.The comparison of our proposed protocols with some typical grouping-proof protocols is shown in Table2.Table 2
The comparison of some typical grouping-proof protocols with our protocols.
Protocols
Privacy
Anonymity
Trace attack
Replay attack
Forward security
DoS attack
The number of tag groups
Ref. [2]
✕
✕
✕
✕
✕
—
One (only two tags)
Ref. [15]
✓
✓
✓
✓
✓
✕
One
Ref. [16]
✕
✕
✕
✓
✓
✕
Multiple
Ref. [18]
✓
✓
✓
✓
✕
—
One (only two tags)
Ref. [19]
✓
✓
✕
✓
✕
—
One (only two tags)
Ours
✓
✓
✓
✓
✓
✓
Multiple


## 6. Conclusions

For some RFID applications, multiple tags are often combined together to identify a group of different objects or different parts of an object. Therefore, it is necessary to acquire the coexistence evidence of a group of tags. As an important component of an RFID system, the tags usually are some passive ones and they only have some very limited computing and memory resources. It is difficult for these tags to complete some advanced cryptographic operations. Therefore, we only use some lightweight functions and bitwise operation to propose two grouping-proof protocols. These protocols involve multiple tag groups. They efficiently use the activate-sleep mechanism and the filtering operation to reduce the collision between tags and the computing load of the RFID system. They only utilize a hash function and a pseudorandom number generator to encrypt all sessions transferred between reader and tags. This ensures the confidentiality and privacy of the RFID system. Meanwhile, our protocols use pseudorandom numbers to randomize each session of the protocols so as to resist trace attack and replay attack. After each grouping-proof, the secrecy of tags is updated and the last round secrecy of tags is preserved. Therefore, our proposed protocols provide forward security and resist desynchronization attack. Otherwise, our protocol can complete a grouping-proof regardless of whether the reader is untrusted or trusted.



---

*Source: 8436917-2020-03-18.xml*