{'fraction_non_alphanumeric': 0.032658569500674764, 'fraction_numerical': 0.00935672514619883, 'mean_word_length': 4.0250904159132, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cyclic group based mutual authentication protocol for RFID system

Widespread deployment of RFID system arises security and privacy concerns of users. There are several proposals are in the literature to avoid these concerns, but most of them provides reasonable privacy at the cost of search complexity on the server side. The search complexity increases linearly with the number of tags in the system. Some schemes use a group based approach to solve the search complexity problem. In this paper, we proposed a group based authentication protocol for RFID system which is based on some characteristics of cyclic groups. The scheme uses only bitwise XOR and mod operation for the computational work. Also, the scheme does not use any pseudo-number generator on the tag-side. We use two benchmark metric based on anonymity set to measure the privacy level of the system when some tags are compromised by an adversary. We present some simulation results which show that the scheme preserves high level of privacy and discloses very less amount of information when some tags are compromised. Furthermore, it's formal and informal analysis shows that our scheme preserves information privacy as well as un-traceability and also withstand against various well known attacks.

With the widespread adoption of RFID system in our daily life, security and privacy concerns are also arise critically [2] [6] [18]. We can use cryptography tool to avoid these concerns but the main obstacle to deploy these tools in RFID system is tight constraints on power, memory and computational capability on the tags.
To enhance the security and privacy of the RFID system and reduce the computational complexity, researchers have been proposed a large number of authentication schemes. Here, we describe some tree-based and group-based authentication schemes related to RFID system. In 2004, Molnar and Wagner [12] proposed a tree-based approach for symmetric key authentication scheme. The scheme reduces its identification complexity from linear to logarithmic. However, it violates the privacy of the other tags when some tags are compromised by an adversary. In 2005, Nohara et al. [13] proposed a similar kind of authentication scheme. The scheme provides higher privacy than [12] in case of one tag is compromised. Buttyán et al. [3] proposed an optimal key trees for tree-based private authentication scheme in 2006. They used different branching factors at different levels of the tree to enhancing the privacy level of the scheme. Also, they introduce a benchmark metric for measuring privacy level of the system when some tags are compromised. In 2007, Avoine et al. [1] developed a group based symmetric key authentication scheme. They improve the trade-off between scalability and privacy by dividing the tags into a number of groups. Also, they analyze the privacy level of the system by using privacy metric when a single tag is compromised as well as any number of tags are compromised. The main draw back of the scheme is to decrease the privacy level when more tags are compromised. In 2017, Rahman et al. [16] developed a secure anonymous private authentication scheme which is similar to [1] except that the scheme used different technique to provide better privacy and ensure more security. They used privacy metric same as in [1] to measure the privacy level of the system. Also, the scheme used information leakage metric based on shannon information theory [17] to measure the information leakage in bits of the system when some tags are compromised.
After reviewing the work done, we would like to propose a similar kind of group based authentication scheme. The scheme uses some different kind of techniques to improve privacy and minimize computational cost.
Rest of the paper is organized as follows: In Section 2, we discuss preliminaries and details of our system model. We present adversary model in Section 3. Group based authentication scheme for RFID system is proposed in Section 4. The formal and informal analysis are given in Section 5. Section 6 illustrates the performance of the proposed scheme. In Section 7, we measure the level of privacy of the system when some tags are compromised by an adversary. We discuss simulation results in Section 8. Finally, conclusions are made in Section 9.

Preliminaries and System Model
In this section, we give brief overview of a cyclic group [10] and using it's properties, we develop our RFID system model. In this system model, we assume that a reader and the server communicate with each other via a secure communication channel. For simplicity, we assume that the reader and the server are combined into one entity, called reader.
Suppose G be a nonempty set together with an operation * that combines any two elements of G is in G. The set G together with this operation is a group if it holds group's law. The order of a group G is the total number of elements in the group. It is denoted by |G|. Let H be a subset of a group G. We say that H is a subgroup of G if it is itself a group under the operation of G.
Definition 2.01 A group G is called cyclic if there exists an element a ∈ G such that G =< a >= {a n | n ∈ Z}. The element a is called a generator of G.
Some important characteristics of cyclic groups are as follows: 1. Suppose G =< a > be a cyclic group of order n. Then G =< a k > iff gcd(k, n) = 1. 2. Every subgroup of a cyclic group is cyclic. 3. Suppose G =< a > be a cyclic group of order n. The order of any subgroup of G is a divisor of n. 4. For each positive divisor k of n, the group G has exactly one subgroup of order k denoted by < a n/k >.

Table 1
The server look-up table We construct a system model for RFID system with the help of above mentioned characteristics of cyclic groups. For this, we choose a cyclic group G =< a > of order n and find its some subgroups H i =< a i >, i = 1, 2, . . . , where a i = a n/k for some positive divisor k, according to our requirement using characteristics 4. According to characteristics 4, if a i and a j are generators of two different subgroups H i and H j respectively, then a i and a j are distinct elements in G. For the system model, with each element of H i except the identity element, we assign a tag together with some secret parameters. Additionally, if H p is the highest order subgroup (say, |H p | = P ) and H p−1 is the second highest order subgroup (say, |H p−1 | = Q) in the system. Then we utilize only Q number of elements of H p to assign tags in such a way so that the value of i (which is used as an index in server look-up table) is same in both the subgroups.
We made a look-up table for the server which is shown in Table 1. From the Table 1, we can see that with each element a i j in H j =< a j >, a tag T ji is assigned and i is used as a index in the look-up table for the tag T ji . The server stores a unique identification number ID ji and a secret key K ji to the tag T ji . It also shows that two nonce r ji old and r jinew are associated with the tag T ji . Initially, we take r ji old = 0 and r jinew be a nonce.
For each tag T ji which is associated with an element a i j in H j , we store inverse of a i j in H j , i.e. (a i j ) −1 , and i in the tag's internal memory. We also store a unique identification number ID ji , a secret key K ji , and a nonce R 4 inside the tag's memory. Initially, R 4 is same as r jinew which is stored in the server's look-up table for tag T ji .

Adversary Model
In this section, we present the ability of an adversary A . The adversary is capable to interact with the RFID system S and also, eavesdrops, intercepts, and modifies any transmitted message between any reader and any tag in the system. Our adversarial model is similar to the model proposed by Juels and Weis [11] with some modifications to meet our requirement. A is also able to send the following queries to an oracle.
The adversary A may send a message m to the tag T ji which responds with message m ′ . 2. SendReader(m, R) → m ′ A can intract with a reader R by sending a message m. The reader R responds with message m ′ .

DrawTags(S)
The adversary has access to a set of tags at any time from the system with this oracle query.

Corrupt(T ji )
A is able to access the volatile memory as well as non volatile memory of a tag T ji .
We also bound the adversary A to use SendTag and SendReader queries by r and t respectively. A can performs s number of computational steps. At a time, A is able to send Corrupt message to atmost (n − 2) number of tags where n is the total number of tags obtained from DrawTags query.

Privacy Experiment
We denote privacy experiment for an RFID system S by EXP priv A ,S [k, n, r, s, t], where r, s, and t represent the capability of an adversary to use SendTag, computations steps and SendReader respectively. Also, k represents a security parameter. An RFID authentication protocol is considered to be private if no adversary has significant advantage in this experiment.
The main goal of the adversary in the experiment is to distinguish between two different tags with in its computational and interaction limits. The experiment is composed in three phases as follows: 1. Learning Phase: The adversary A interacts with the system S and inqueries oracle queries without exceeding its bound and analyze them. 2. Challenging Phase: A selects two uncorrupted tags from the pool obtained by Drawtags oracle.
A randomly selects any one from them. The adversary evaluates oracles on that particular tag. 3. Guessing Phase: A outputs a guess bit b. A is expected to produce 1 if he succeeds, otherwise 0.

Privacy Definition [(r, s, t)-privacy]
According to Juels and Weis [11], an RFID authentication protocol with security parameter k is where poly(k) is any polynomial function of k.

Process
In this section, we propose a group based authentication protocol which works under all circumstances required for RFID systems. Used notations in this protocol are given in Table 2, and proposed protocol is shown in Figure 1. The work flow of the proposed scheme is as follows: Nonce generated by the reader.

K ji
Secret key of a tag T ji associated with the i th element of a subgroup H j . ID ji Unique identification number of the tag T ji . ⊕ Exclusive-or operation. Table 2 Notations and symbols used in proposed scheme Reader Tag Extracts R 1 and R 2 from received β and γ respectively. It computes Extracts R 3 from recevied ζ and computes η ′ , and checks η ′ ≈ η. If holds, updates R 4 = R 3 .

Authentication success
Authentication failure Y With the help of received i and stored database, the server computes α ′ and checks α ′ ≈ α for each subgroup until it gets the right tag.
Generates two nonce R 1 and R 2 , and computes β = R 1 ⊕ K, γ = R 2 ⊕ K. After receiving the tag's request message msg 1 , the reader uses i as an index (as in Table 1) to performs the following steps for all the subgroups until it finds the right tag: (a) It calculates the inverse of a i k in H k , where a k is the generator of subgroup H k . (b) The reader computes α ′ = (a i k ) −1 ⊕ r ki old /r kinew and checks whether α ′ is equal to the received α or not. If so, it gets the right tag T ki (say) inside the subgroup H k . If fails, the reader terminates the protocol. (c) The reader generates two nonce R 1 and R 2 , and computes β = R 1 ⊕K ki , γ = R 2 ⊕K ki , where K ki is the secret key of the tag T ki . The reader forms a response message msg 2 = {β, γ} and transmits it to the tag.
3. msg 3 : T ki → R : {δ} Upon receiving the response message msg 2 , the tag T ki extracts R 1 and R 2 from β and γ respectively with the help of its secret key K ki . It computes δ = (ID ki ⊕ R 1 ) mod ((a i k ) −1 ⊕ R 2 ) and send δ inside the response message msg 3 = {δ} to the reader. 4. msg 4 : R → T ki : {ζ, η} After receiving message msg 3 from the tag T ki , the reader calculates δ ′ = (ID ki ⊕R 1 ) mod ((a i k ) −1 ⊕ R 2 ) for the tag T ki and checks whether δ ′ is equal to the received δ or not. If it holds, the reader authenticates the tag T ki otherwise terminates the session. If tag's authentication succeed, the reader generates a nonce R 3 and assigns r ki old = r kinew , and r kinew = R 3 . Simultaneously, also computes ζ = R 3 ⊕ K ki , η = (ID ki ⊕ R 3 ) mod ((a i k ) −1 ⊕ R 1 ) and forms a response message msg 4 = {ζ, η}. It sends msg 4 to the tag T ki . 5. Upon receiving message msg 4 , the tag T ki extracts R 3 from ζ and calculates η ′ = (ID ki ⊕ R 3 ) mod ((a i k ) −1 ⊕ R 1 ). The tag checks whether η ′ is equal to the received η or not. If so, the tag authenticates the reader and updates R 4 = R 3 for further communication.

Security and Privacy Analysis
In this section, we present formal and informal analysis of our proposed scheme with respect to above mentioned adversary model. The formal analysis shows that the proposed scheme preserves privacy and un-traceability. Also, it's informal analysis shows that the proposed scheme is secure against various well-known attacks.

Formal Security Analysis
Theorem 1 The proposed scheme attains information privacy with respect to a adversary A .
Proof We assume that the proposed scheme does not preserve information privacy. So the success probability of the adversary to win experiment is non-negligible. A 's privacy game is composed in three phases as follows: -Learning Phase: The adversary gets a set of n-tags by querying DrawTags oracle. A can send any oracle queries to a tag T i (say) without exceeding its computation bound and analyze them.
A can use Corrupt oracle to atmost n − 2 tags.
The adversary A selects two uncorrupted tags say, T i and T j , from the set of tags obtained by DrawTags query as its challenge tags. Let T * 0 = T i , T * 1 = T j , and b ∈ {0, 1}. A randomly selects T b among them and analyze all queries run on it. Note that A is not able to use Corrupt oracle on that particular tag T b .
The adversary wins the experiment if b ′ = b. It is possible only when the adversary knows all the secrets stored in T b 's internal memory as well as the mother group G. So our assumption is wrong. Hence the proposed scheme preserves the information privacy with respect to A .

Theorem 2
The proposed scheme provides un-traceability with respect to the adversary A .
Proof Let us assume that the proposed scheme is traceable. i.e. the adversary can trace a tag at any time. This means A is able to distinguish between two tags. We show that our assumption is wrong with the help of A 's privacy game which is as follows: -Learning Phase: A uses DrawTags query for the system S and gets access to n-tags. For all the tags, A sends SendTag and SendReader queries to get transmitted information among a reader and tags. The adversary analyzes all the transmitted message. The adversary can use Corrupt query for atmost n − 2 tags because the goal of the privacy game is to distinguish between two uncorrupted tags.
The adversary selects two uncorrupted tags T i and T j to which it did not send Corrupt query in the learning phase. A randomly selects T b : b ∈ {i, j} among them. The adversary queries all the oracle queries except Corrupt query to the tag T b and evaluates them. Since the message msg 1 depend upon the tag's nonce R 4 which is different in each protocol run. So our assumption is wrong. Hence the adversary is unable to trace the tag.

Replay Attack Resistance
An adversary can eavesdrops the wireless channel and keeps all the transmitted messages between a reader and a tag. The adversary uses these message into another session to disguise itself as the tag or the reader to deceive the other one. In the proposed scheme, it is infeasible for an adversary to forge messages as a valid tag/reader because each transmitted message incorporates a fresh nonce in each authentication session which can not be get by the adversary (since the nonce XOR with some other secret parameters). This makes all the replayed message by the adversary are illegal message. Thus the scheme prevents strongly the replay attack.

De-synchronization Attack Resistance
For each tag, the server stores two nonce r old and r new in its database to save the scheme from the de-synchronization attack. The server also updates these values after a successful authentication session. An adversary intercepts or modified any transmitted message in one session in such a way so that a tag does not update the value of stored nonce. The server can authenticate the legitimate tag by its old value stored in database into another session. So it is not possible for an adversary to de-synchronize the scheme.

Man-in-Middle Attack Resistance
An adversary is unable to act as a middle man in between a reader and a tag because it is infeasible for the adversary to intercepts any transmitted message without knowing the secret key, unique identification number, and knowledge about the cyclic group. The probability of guessing or calculating these values from the transmitted message is negligible because a fresh nonce is used in each transmitted message.

Performance Analysis
In this section, we present efficiency of our proposed scheme in terms of tag computation, server computation, and storage, as described in Table 3. The proposed scheme's search complexity is O(γ) which is same as in Avione et al. [1] but better than Rahman et al. [16]. During the authentication phase, the scheme performs only bit-wise XOR operation whereas schemes of Avoine et al. and Rahman et al. perform symmetric key encryption and decryption. Also, the proposed scheme does not use any pseudo number generator function for generating nonce on the tag-side. It uses nonce generated by the reader. We assume that all the parameters used in the proposed scheme are L-bits long. On the tag side, our scheme keeps five items. Thus the storage cost is 5L bits. The proposed scheme also provides mutual authentication among a reader and tags. When we compare with [1] and [16] in terms of computation, the proposed scheme performs very less computation which is optimal for the real world tiny powered tags.  In this section, we analyze the privacy level of our proposed scheme in terms of anonymity set and data leakage in bits. For the anonymity sets, we use privacy metric introdued by [3]. Also, we use another metric says information leakage for data leakage proposed by shannon [17] and used in [14] [16] to measure the information (in bits) disclosed by the proposed scheme when some tags are compromised.
Both the metric use disjoint partition sets of tags for observation. When some tags are compromised, the set of all tags are partitioned in such a way so that the adversary can not distinguish the tags that belong to the same partition but she can distinguish the tags belong to different partitions.
Here, |P i | denotes the size of such partition P i and |Pi| N is the probability that a randomly chosen tag belongs to partition P i .

Level of privacy based on anonymity set
The level of privacy ℜ based on anonymity set is characterized as average anonymity set size normalized with the total number of tags N [3] [1] [16].
In the proposed scheme, if a tag is compromised, it does not leak any information about the subgroup in which it belongs. For this reason, the adversary can not distinguish between two tags whether they belongs to same subgroup or not. So, if C is the total number of compromised tags in the whole system, we partitioned the system into C number of anonymity sets with size 1 and one another anonymity set of size (N − C). Using equation 1, the level of privacy ℜ achieved by our scheme is where N is the total number of tags in the system and C is the total number of compromised tags in the system.

Level of privacy based on information leakage in bits
According to Rahman et al. [16], if an adversary partitioned a system with N tags into k disjoint sets, then the information leakage in bits can be expressed as follows: In the proposed scheme, if C is the total number of compromised tags in the system. Then we partitioned the system with N tags into C anonymity sets of size 1 and one another anonymity set of size (N − C). According to our partitions, the information leakage in bits is as follows

Experimental Results
In this section, we compare our scheme with Avoine et al. [1] and Rahman et al. [16] using a matlab simulation. The simulation is done using the expressions (1) -(4). In the simulation, we assume that the system has N = 2 10 number of tags and all the tags are divided into 32 groups. We choose range of compromised tags from 0 to 600. In the proposed scheme, it is not necessary to take same number of tags in each groups. In the simulation, we run 100 simulations for each value of compromised tags C in the system. In each simulation run, compromised tags are chosen uniformly random from the groups of all tags. Finally, we average all the obtained values over all simulation runs. The simulation results are shown in Figure 2 and Figure 3. The simulation results of the Figure 2 shows that the privacy level achieved by the proposed scheme is 94.42% and 98.43% better than Rahman et al. and Avoine et al. respectively, when C becomes 600 in a similar setup. According to simulation result shown in Figure 3, the proposed scheme discloses 22.62% and 34.05% less information than Rahman et al. and Avoine et al. respectively when C becomes 600. Thus the proposed scheme achieves higher improvement in terms of privacy level and information leakage than the other schemes, when some tags are compromised by an adversary.

Conclusion
In this paper, we have proposed a group based authentication scheme for RFID system based on a cyclic group. The detailed formal analysis shows that it preserves information privacy and un-traceability. The informal analysis shows that the scheme resists various existing attacks. The performance analysis illustrates that the scheme uses very less resources on tags to performs computational work and storage data. The experimental results show that our scheme preserves high level privacy when some tags are compromised. Thus, the analysis and prominent features conclude that the scheme is secure and efficient for a low-cost RFID system.