# Cryptanalysis and Improvement of a Group Authentication Scheme with Multiple Trials and Multiple Authentications

Authors: Zhe Xia; Yining Liu; Ching-Fang Hsu; Chin-Chen Chang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Authentication is one of the most fundamental services in cryptography and information security. Compared with the traditional authentication methods, group authentication allows a group of users to be authenticated at once rather than authenticating each of these users individually. Therefore, it is more desirable in the group oriented environment, such as multicast/conference communications. In this paper, we first demonstrate that a recent group authentication scheme by Chien (Security and Communication Networks, 2017) suffers some security flaws, i.e. an adversary in the asynchronous communication model can pretend to be a legitimate group member without being detected. We then use the Anonymous Veto Networks (AV-net) to patch Chien’s scheme, so that its security can be rigorously proved in a well-defined security model.


---

## Body

## 1. Introduction

Authentication confirms whether some entity is who or what it claims to be. It is an important security service in cryptography and information security. Traditionally, the authentication process is carried out between two parties. The prover proves its identity to the verifier using a single or some combination of the following methods: something it has, something it knows, or something it is. The verifier will accept the proof if the prover, indeed, possesses the credential. However, this one-to-one authentication approach is inefficient in the group oriented environment, e.g., multicast/conference communications and broadroom elections [1, 2]. If each user needs to authenticate every user’s identity, a large number of authentication operations (quadratic to the number of users) need to be performed across the entire group. To address this problem, group authentication [3] has been proposed recently, so that instead of authenticating each user individually, all users in the group can be authenticated at once. If all users are legitimate group members, the group authentication is sufficient to prove that they all belong to the same group. Even if there exist some nonmembers, the group authentication still can be used as a preprocessing step before applying some traditional authentication techniques to identify those nonmembers.In general, a group authentication scheme consists of two phases. In theinitialization phase, the group manager (GM) generates a credential for each group member, and these credentials are sent through some secure networks. In the authentication phase, each player uses her credential to compute a token and broadcasts it. As follows, every user can use the revealed information to verify whether all these users are belonging to the same group. Two security requirements are fundamental for group authentication schemes. One is that if all users are legitimate group members, the authentication will always be successful. The other is that any nonmember with no valid credential cannot pretend to be a group member without being detected. Moreover, two other requirements are also highly desirable for group authentication schemes: (1) reuse of the credentials in multiple authentication sessions; (2) allowance of players to broadcast their tokens through asynchronous networks. Note that the first requirement helps to avoid the cumbersome processes of distributing credentials for every authentication session, and the asynchronous networks are easier to be established than the synchronous ones, especially in the distributed environment.


### 1.1. Our Contributions

In his work [4], Chien has proposed a group authentication scheme, claiming to satisfy the abovementioned requirements. In this paper, we first demonstrate that Chien’s scheme fails to achieve its claimed security in the asynchronous networks. In particular, an adversary in the asynchronous communication model can always wait until the other legitimate users having revealed their tokens and then fabricate a valid token using the revealed ones. We then use a novel technique, called Anonymous Veto Networks (AV-net), to patch Chien’s scheme. To avoid the “design-break-patch loop,” our proposed scheme is rigorously analyzed in a well-defined security model [5].


### 1.2. Organization of the Paper

The rest of the paper is organized as follows. In Section2, we briefly review some related works in the literature. Chien’s scheme is described and analyzed in Section 3. In Section 4, we outline some preliminaries, including notations, building blocks, and security models. In Section 5, we introduce our improvement of Chien’s scheme and analyze it with respect to security and efficiency. Finally, we conclude in Section 6.


## 1.1. Our Contributions

In his work [4], Chien has proposed a group authentication scheme, claiming to satisfy the abovementioned requirements. In this paper, we first demonstrate that Chien’s scheme fails to achieve its claimed security in the asynchronous networks. In particular, an adversary in the asynchronous communication model can always wait until the other legitimate users having revealed their tokens and then fabricate a valid token using the revealed ones. We then use a novel technique, called Anonymous Veto Networks (AV-net), to patch Chien’s scheme. To avoid the “design-break-patch loop,” our proposed scheme is rigorously analyzed in a well-defined security model [5].


## 1.2. Organization of the Paper

The rest of the paper is organized as follows. In Section2, we briefly review some related works in the literature. Chien’s scheme is described and analyzed in Section 3. In Section 4, we outline some preliminaries, including notations, building blocks, and security models. In Section 5, we introduce our improvement of Chien’s scheme and analyze it with respect to security and efficiency. Finally, we conclude in Section 6.


## 2. Related Works

After the concept being initially introduced by Harn [3], group authentication has been widely accepted as a useful tool in cryptography to simultaneously prove that a group of users are all legitimate members [6]. Recently, a number of group authentication schemes have been proposed in the literature. For example, Chien [4] used a different mathematical structure to renovate Harn’s scheme, with the purpose of allowing the credentials to be used in multiple trials in asynchronous networks. Liu et al. [7] considered the resource restrained environment and proposed a lightweight group authentication scheme in which the authentication is executed by checking whether the interpolation of the credentials returns a polynomial with the expected degree. Mahalle et al. [8] used the threshold Paillier cipher to design a group authentication scheme for the Internet of Things. Li et al. [9] extended the functionalities of group authentication so that not only the group members can be authenticated at once but also pairwise keys can be established among the group members. Guo et al. [10] and Elmouaatamid et al. [11] independently explored how to further trace the nonmembers if the group authentication fails.However, a common drawback of these existing works is that their security is only justified using heuristic arguments rather than formal security proofs, and several of these schemes have already been found to contain security flaws. For example, Ahmadian and Jamshidpour [12] showed that Harn’s scheme is insecure because an adversary in the asynchronous networks can impersonate a group member without being detected. In paper [3], Harn simply conjectured that the adversary needs to reconstruct all the polynomials to fabricate a valid token. But, this adversary may use a very novel method, called the linear subspace attack, to fabricate a valid token without recovering any of the polynomials. In their work [5], Xia et al. proposed a formal security model for group authentication that captures the main security requirements. This work has also improved Harn’s scheme so that the modified scheme can be rigorously proved to achieve the desirable security properties.In this paper, we first demonstrate that Chien’s scheme is also insecure in the asynchronous networks. We then propose an improvement of Chien’s scheme and prove its security using the security model in paper [5].


## 3. Analysis of Chien’s Scheme

### 3.1. Description

Note that our description here is slightly different from Chien’s original scheme [4]. We use a symmetric bilinear map in order to simplify the description, while Chien uses an asymmetric bilinear map. It is well known that compared with the symmetric bilinear map, the asymmetric one has advantages in security and bandwidth, but our attack against Chien’s scheme also works when an asymmetric bilinear map is used instead.We denoteG1 and G2 as two finite cyclic groups of order q for some large prime q. A bilinear map e^:G1×G1⟶G2 is defined between these two groups, satisfying the following properties:(i)
Bilinear: the mape^:G1×G1⟶G2 is said to be bilinear if e^aP,bQ=e^P,Qab for all P,Q∈G1 and all a,b∈ℤq(ii)
Nondegenerate: the mape^ does not send all pairs in G1×G1 to the identity in G2(iii)
Computable: there exists an efficient algorithm to computee^P,Q for any P,Q∈G1Chien’s multiple group authentication scheme works as follows:(i)
Init: GM first selects two finite cyclic groupsG1 and G2 with prime order q and a bilinear map e^:G1×G1⟶G2. Denote P as a generator of G1. GM then selects a secret Ri←Rℤq and sets Q=sP. GM selects l values Ri←RG1 for i∈ℤl. GM associates the pairwise different integers w1,w2,…,wn with the group members. Finally, GM outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist: GM selects a random polynomialfx=a0+a1x+⋯+at−1xt−1 over ℤq with degree t−1, such that a0=s. GM, then computes the credentials si=fwi, and sends them to the group members through the secure channel.(iii)
Comp: in theσ-th session (σϵ1,2,…,l), every participating user in ΩΩ≥t computes her token ci=siℒiRσ and broadcasts it, where ℒi=∏jεΩ,j≠iwj/wj−wi is the Lagrange coefficient.(iv)
Auth: in theσ-th session, every user can verify whether all the users are legitimate group members by checking:(1)e^∑t∈Ωci,P=e^Rσ,Q.Note that if all players are legitimate group members, we have∑t∈Ωci=sRσ. Also, thanks to the bilinear property, this further implies that the abovementioned equation holds. But, if there exist some nonmembers, the relation ∑t∈Ωci=sRσ can only satisfy with negligible probability. Therefore, the abovementioned equation can be used to check whether a group authentication is successful.


### 3.2. Analysis

Now, we demonstrate that, in the asynchronous communication model, an adversaryA who has no valid credential can pretend to be a legitimate group member without being detected. Without loss of generality, suppose that A attends the σ-th group authentication session together with t legitimate group members U1,U2,…,Ut and A would like to impersonate the group member Ut+1. The attack works as follows:(i)
Each legitimate group memberUi computes and broadcasts her token ci=siℒiRσ, where ℒi=∏j=1,j≠t+1t+1wj/wj−wi is the Lagrange coefficient.(ii)
After receiving these tokens,A modifies them as ci′=ci⋅ℒi−1=siRσ for iε1,2,…,t and interpolates st+1Rσ=∑i=1tci′ℒi′wt+1, where(2)ℒi′wt+1=∏j=1,j≠itwt+1−wjwi−wj.(i)
Finally,A computes the token ct+1=st+1ℒt+1Rσ, where ℒt+1=∏j=1,j≠t+1t+1wj/wj−wt+1, and broadcasts ct+1.At this time, the group authentication will be successful because∑i=1t+1ci=sRσ. The consequence is that the adversary A has impersonated the group member Ut+1 without being detected. The main reason for this attack is that since the Lagrange coefficients can be publicly computed, A can remove them from the revealed tokens and then uses the modified tokens to interpolate a new valid token. To solve this problem, we need to disable A’s ability of removing the Lagrange coefficients from the revealed tokens.


## 3.1. Description

Note that our description here is slightly different from Chien’s original scheme [4]. We use a symmetric bilinear map in order to simplify the description, while Chien uses an asymmetric bilinear map. It is well known that compared with the symmetric bilinear map, the asymmetric one has advantages in security and bandwidth, but our attack against Chien’s scheme also works when an asymmetric bilinear map is used instead.We denoteG1 and G2 as two finite cyclic groups of order q for some large prime q. A bilinear map e^:G1×G1⟶G2 is defined between these two groups, satisfying the following properties:(i)
Bilinear: the mape^:G1×G1⟶G2 is said to be bilinear if e^aP,bQ=e^P,Qab for all P,Q∈G1 and all a,b∈ℤq(ii)
Nondegenerate: the mape^ does not send all pairs in G1×G1 to the identity in G2(iii)
Computable: there exists an efficient algorithm to computee^P,Q for any P,Q∈G1Chien’s multiple group authentication scheme works as follows:(i)
Init: GM first selects two finite cyclic groupsG1 and G2 with prime order q and a bilinear map e^:G1×G1⟶G2. Denote P as a generator of G1. GM then selects a secret Ri←Rℤq and sets Q=sP. GM selects l values Ri←RG1 for i∈ℤl. GM associates the pairwise different integers w1,w2,…,wn with the group members. Finally, GM outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist: GM selects a random polynomialfx=a0+a1x+⋯+at−1xt−1 over ℤq with degree t−1, such that a0=s. GM, then computes the credentials si=fwi, and sends them to the group members through the secure channel.(iii)
Comp: in theσ-th session (σϵ1,2,…,l), every participating user in ΩΩ≥t computes her token ci=siℒiRσ and broadcasts it, where ℒi=∏jεΩ,j≠iwj/wj−wi is the Lagrange coefficient.(iv)
Auth: in theσ-th session, every user can verify whether all the users are legitimate group members by checking:(1)e^∑t∈Ωci,P=e^Rσ,Q.Note that if all players are legitimate group members, we have∑t∈Ωci=sRσ. Also, thanks to the bilinear property, this further implies that the abovementioned equation holds. But, if there exist some nonmembers, the relation ∑t∈Ωci=sRσ can only satisfy with negligible probability. Therefore, the abovementioned equation can be used to check whether a group authentication is successful.


## 3.2. Analysis

Now, we demonstrate that, in the asynchronous communication model, an adversaryA who has no valid credential can pretend to be a legitimate group member without being detected. Without loss of generality, suppose that A attends the σ-th group authentication session together with t legitimate group members U1,U2,…,Ut and A would like to impersonate the group member Ut+1. The attack works as follows:(i)
Each legitimate group memberUi computes and broadcasts her token ci=siℒiRσ, where ℒi=∏j=1,j≠t+1t+1wj/wj−wi is the Lagrange coefficient.(ii)
After receiving these tokens,A modifies them as ci′=ci⋅ℒi−1=siRσ for iε1,2,…,t and interpolates st+1Rσ=∑i=1tci′ℒi′wt+1, where(2)ℒi′wt+1=∏j=1,j≠itwt+1−wjwi−wj.(i)
Finally,A computes the token ct+1=st+1ℒt+1Rσ, where ℒt+1=∏j=1,j≠t+1t+1wj/wj−wt+1, and broadcasts ct+1.At this time, the group authentication will be successful because∑i=1t+1ci=sRσ. The consequence is that the adversary A has impersonated the group member Ut+1 without being detected. The main reason for this attack is that since the Lagrange coefficients can be publicly computed, A can remove them from the revealed tokens and then uses the modified tokens to interpolate a new valid token. To solve this problem, we need to disable A’s ability of removing the Lagrange coefficients from the revealed tokens.


## 4. Preliminaries

### 4.1. Notations

We assume that all players are probabilistic polynomial time (PPT) algorithms with respect to the security parameterλ. Standard notations are used for probabilistic algorithms and experiments. For example, if A is a probabilistic algorithm, then Ax1,x2,… denotes the result of running A on inputs x1,x2, and so on. We denote y←Ax1,x2,… as the experiment of assigning y as Ax1,x2,…. If S is a finite set, then we denote x←RS as the operation of picking an element uniformly from S. Moreover, Prx←S;y←T;⋯:px,y,… denotes the probability that the predicate px,y,… will be true after the ordered execution of the algorithms x←S;y←T, and so on. A function εk:ℕ⟶ℝ+ is called negligible if for all c>0, there exists a k0 such that εk<1/kc for all k>k0.


### 4.2. Building Blocks

Shamir secret sharing [13]: it shares the secret value sεℤq among n users, so that any t or more users can work together to recover the secret, but less than t users cannot get any information of the secret. In the sharing phase, the dealer first selects a random polynomial fx=a0+a1x+⋯+at−1xt−1 over ℤq with degree t−1, where a0=s. Then, the dealer computes the shares si=fwi and sends them to each user through the secure channel. Here, w1,w2,…,wn are public parameters associated with the users that are pairwise different. In the reconstruction phase, any subset Ω (where Ω≥t) of these users can reconstruct the secret s by Lagrange interpolation: s=∑i∈Ωsiℒi, where ℒi=∏jεΩ,j≠iwj/wj−wi is called the Lagrange coefficient.Anonymous veto networks (AV-nets) [14]: they assume that there exist broadcast channels, and all the messages are exchanged through these channels. Suppose n users are involved, and then the protocol works as follows:(i)
Round 1: each userUi selects a value xi←Rℤq and broadcasts gxi. Ui also proves that she has the knowledge of xi without revealing it, e.g., using the Schnorr identification technique [15]. When this round finishes, every user computes gyi=∏j=1i−1gxj/∏j=i+1ngxj.(ii)
Round 2: every user broadcasts a valuegxiyi and proves the knowledge of xi within gxiyi without revealing it. Now, we have(3)∏i=1ngxiyi=1.To see that the abovementioned property always holds, by definition,yi=∑j<ixj−∑j>ixj; hence, we have(4)∑ixiyi=∑i∑j<ixiyj−∑i∑j>ixiyj,=∑∑j<ixiyj−∑∑i<jxiyj,=∑∑j<ixiyj−∑∑j<ixjyi,=0.


### 4.3. Security model

We adapt the models and definitions in paper [5] and prove our proposed scheme using this security model.The participants: there are four types of participants in group authentication schemes:(i)
Group manager (GM): the GM initializes the protocol and generates credentials for the users. In any authentication protocol, the user needs to possess some secret that is unknown to the others.(ii)
Users: each of then users will receive a credential from the GM, and they will use their credentials to participate in the group authentication.(iii)
Inside adversary: the inside adversaryAI controls at most t−1 users, where t is the threshold such that t>n/2. AI can obtain these users’ internal states. AI’s purpose is to learn some secret information or to pass the group authentication by herself.(iv)
Outside adversary: the outside adversaryAO does not own any valid credential generated by the GM, but her purpose is to impersonate a group member in the group authentication without being detected.Communication model: we assume that there exists a secure channel between the GM and every user, so that the credentials can be distributed securely. Moreover, we assume that every participant is connected to a broadcast channel, where any message sent through this channel can be heard by the other participants within some specified time bound. Note that the broadcast channel is only assumed to be asynchronous, such that messages sent from the uncorrupted users to the corrupted ones can be delivered relatively fast, the case in which the adversary can wait for the messages of the uncorrupted users to arrive, then decide on her computation and communication, and still get her messages delivered to the honest users on time. In comparison, all the users need to send their messages simultaneously in the synchronous networks. Therefore, adversaries in an asynchronous network are more powerful as they could obtain more information to assist their attacks.System model: the group authentication scheme is specified by the following four randomized algorithms:Init, Dist, Comp, and Auth.(i)
The initialization algorithmInit is run by the GM. Init takes as inputs the security parameter λ; it outputs the system parameters params.(ii)
The distribution algorithmDist is run by the GM. Dist takes as inputs the system parameters params and the number of users n; it outputs a set of credentials s1,s2,…,sn. These credentials are sent to U through the secure channel, where U denotes the set of all legitimate group members.(iii)
The computation algorithmComp is run by every user. Comp takes as inputs the system parameters params, the session index σ, the set of participated users Ω, and a credential si; it outputs a token ci through the broadcast channel.(iv)
The group authentication algorithmAuth is run by the participated users. Auth takes as inputs the system parameters params, the session index σ and a set of tokens ciiεΩ; it outputs 1 if Ω≥t and Ω only contains legitimate group members, and it outputs 0 otherwise.Security Model: the following security properties are considered in the security model.Definition 1.
(correctness). If a setΩ (Ω≥t) of users are participating in the group authentication and they are all legitimate group members, then the group authentication will be successful. Formally, a group authentication scheme is said to have the correctness property if we have(5)Prparams⟵Initλ;siiεΩ⟵″Dist″params,n″;″ci⟵Compparams,σ,Ω,siiεΩ;″Auth″params,σ,ciiεΩ″=1″=1.
In the abovementioned expression,Ω⊆U and Ω≥t.Definition 2.
(secrecy). The inside adversaryAI cannot learn any secret information in the group authentication process. Formally, a group authentication scheme is said to have the secrecy property if we have(6)ViewAIReal∏λ,params≅cViewAISIMSλ,params.
In the abovementioned expression,ViewAIReal∏λ,params is denoted as AI’s view in the real run of the protocol ∏, ≅c means computationally indistinguishable, and ViewAISIMSλ,params is denoted as AI’s view of the transcripts simulated by a PPT simulator S with only public information as inputs.Definition 3.
(no forgery). The inside adversaryAI cannot pass the group authentication by herself. Formally, a group authentication scheme is said to have the no forgery property if we have(7)Prparams⟵Initλ;siiϵU⟵″Dist″params,n″;″T⟵AIOparams,σ,Ω,sii∈UA;″σ∉″∑∧″Auth″params,σ,T″=1″<ελ.
In the abovementioned expression,UA denotes the users that are controlled by AI, such that UA⊂U and UA≤t−1. Ω denotes an oracle that is used to query the group authentication service, and Σ records all the session indexes which have been queried.Definition 4.
(no impersonation). The outside adversaryAO cannot impersonate a group member without being detected. Formally, a group authentication scheme is said to have the no impersonation property if we have(8)Prparams⟵Initλ;siiεU⟵″Dist″params,n″;″ci⟵Compparams,σ,Ω∪μ,siiεΩ;cμ⟵AOparams,σ,Ω∪μ,cii∈Ω;″Auth″params,σ,cii∈Ω∪μ″=1″<ελ.
In the abovementioned expression,AO is assumed to impersonate the user Uμ, where μ∉Ω.
Computational assumptions: we assume that the following assumptions hold against any PPT algorithm.Definition 5.
(discrete logarithm (DL) assumption). The description of the finite cyclic groupG is given, where G|≥q and g is a generator of G. The discrete logarithm assumption implies that there exists a negligible function ε⋅ such that for all PPT adversaries ADL, we have(9)Prx←Rℤq;x∗←ADLG,q,g,gx:x∗=x<ελ.Definition 6.
(computational Diffie–Hellman (CDH) assumption). The description of the finite cyclic groupG given, where G≥q and g is a generator of G. The computational Diffie–Hellman assumption implies that there exists a negligible function ε⋅ such that for all PPT adversaries ACDH, we have Prx←Rℤq;y←Rℤq;R←ACDHG,q,g,gx,gy:R=gxy<ελ.


## 4.1. Notations

We assume that all players are probabilistic polynomial time (PPT) algorithms with respect to the security parameterλ. Standard notations are used for probabilistic algorithms and experiments. For example, if A is a probabilistic algorithm, then Ax1,x2,… denotes the result of running A on inputs x1,x2, and so on. We denote y←Ax1,x2,… as the experiment of assigning y as Ax1,x2,…. If S is a finite set, then we denote x←RS as the operation of picking an element uniformly from S. Moreover, Prx←S;y←T;⋯:px,y,… denotes the probability that the predicate px,y,… will be true after the ordered execution of the algorithms x←S;y←T, and so on. A function εk:ℕ⟶ℝ+ is called negligible if for all c>0, there exists a k0 such that εk<1/kc for all k>k0.


## 4.2. Building Blocks

Shamir secret sharing [13]: it shares the secret value sεℤq among n users, so that any t or more users can work together to recover the secret, but less than t users cannot get any information of the secret. In the sharing phase, the dealer first selects a random polynomial fx=a0+a1x+⋯+at−1xt−1 over ℤq with degree t−1, where a0=s. Then, the dealer computes the shares si=fwi and sends them to each user through the secure channel. Here, w1,w2,…,wn are public parameters associated with the users that are pairwise different. In the reconstruction phase, any subset Ω (where Ω≥t) of these users can reconstruct the secret s by Lagrange interpolation: s=∑i∈Ωsiℒi, where ℒi=∏jεΩ,j≠iwj/wj−wi is called the Lagrange coefficient.Anonymous veto networks (AV-nets) [14]: they assume that there exist broadcast channels, and all the messages are exchanged through these channels. Suppose n users are involved, and then the protocol works as follows:(i)
Round 1: each userUi selects a value xi←Rℤq and broadcasts gxi. Ui also proves that she has the knowledge of xi without revealing it, e.g., using the Schnorr identification technique [15]. When this round finishes, every user computes gyi=∏j=1i−1gxj/∏j=i+1ngxj.(ii)
Round 2: every user broadcasts a valuegxiyi and proves the knowledge of xi within gxiyi without revealing it. Now, we have(3)∏i=1ngxiyi=1.To see that the abovementioned property always holds, by definition,yi=∑j<ixj−∑j>ixj; hence, we have(4)∑ixiyi=∑i∑j<ixiyj−∑i∑j>ixiyj,=∑∑j<ixiyj−∑∑i<jxiyj,=∑∑j<ixiyj−∑∑j<ixjyi,=0.


## 4.3. Security model

We adapt the models and definitions in paper [5] and prove our proposed scheme using this security model.The participants: there are four types of participants in group authentication schemes:(i)
Group manager (GM): the GM initializes the protocol and generates credentials for the users. In any authentication protocol, the user needs to possess some secret that is unknown to the others.(ii)
Users: each of then users will receive a credential from the GM, and they will use their credentials to participate in the group authentication.(iii)
Inside adversary: the inside adversaryAI controls at most t−1 users, where t is the threshold such that t>n/2. AI can obtain these users’ internal states. AI’s purpose is to learn some secret information or to pass the group authentication by herself.(iv)
Outside adversary: the outside adversaryAO does not own any valid credential generated by the GM, but her purpose is to impersonate a group member in the group authentication without being detected.Communication model: we assume that there exists a secure channel between the GM and every user, so that the credentials can be distributed securely. Moreover, we assume that every participant is connected to a broadcast channel, where any message sent through this channel can be heard by the other participants within some specified time bound. Note that the broadcast channel is only assumed to be asynchronous, such that messages sent from the uncorrupted users to the corrupted ones can be delivered relatively fast, the case in which the adversary can wait for the messages of the uncorrupted users to arrive, then decide on her computation and communication, and still get her messages delivered to the honest users on time. In comparison, all the users need to send their messages simultaneously in the synchronous networks. Therefore, adversaries in an asynchronous network are more powerful as they could obtain more information to assist their attacks.System model: the group authentication scheme is specified by the following four randomized algorithms:Init, Dist, Comp, and Auth.(i)
The initialization algorithmInit is run by the GM. Init takes as inputs the security parameter λ; it outputs the system parameters params.(ii)
The distribution algorithmDist is run by the GM. Dist takes as inputs the system parameters params and the number of users n; it outputs a set of credentials s1,s2,…,sn. These credentials are sent to U through the secure channel, where U denotes the set of all legitimate group members.(iii)
The computation algorithmComp is run by every user. Comp takes as inputs the system parameters params, the session index σ, the set of participated users Ω, and a credential si; it outputs a token ci through the broadcast channel.(iv)
The group authentication algorithmAuth is run by the participated users. Auth takes as inputs the system parameters params, the session index σ and a set of tokens ciiεΩ; it outputs 1 if Ω≥t and Ω only contains legitimate group members, and it outputs 0 otherwise.Security Model: the following security properties are considered in the security model.Definition 1.
(correctness). If a setΩ (Ω≥t) of users are participating in the group authentication and they are all legitimate group members, then the group authentication will be successful. Formally, a group authentication scheme is said to have the correctness property if we have(5)Prparams⟵Initλ;siiεΩ⟵″Dist″params,n″;″ci⟵Compparams,σ,Ω,siiεΩ;″Auth″params,σ,ciiεΩ″=1″=1.
In the abovementioned expression,Ω⊆U and Ω≥t.Definition 2.
(secrecy). The inside adversaryAI cannot learn any secret information in the group authentication process. Formally, a group authentication scheme is said to have the secrecy property if we have(6)ViewAIReal∏λ,params≅cViewAISIMSλ,params.
In the abovementioned expression,ViewAIReal∏λ,params is denoted as AI’s view in the real run of the protocol ∏, ≅c means computationally indistinguishable, and ViewAISIMSλ,params is denoted as AI’s view of the transcripts simulated by a PPT simulator S with only public information as inputs.Definition 3.
(no forgery). The inside adversaryAI cannot pass the group authentication by herself. Formally, a group authentication scheme is said to have the no forgery property if we have(7)Prparams⟵Initλ;siiϵU⟵″Dist″params,n″;″T⟵AIOparams,σ,Ω,sii∈UA;″σ∉″∑∧″Auth″params,σ,T″=1″<ελ.
In the abovementioned expression,UA denotes the users that are controlled by AI, such that UA⊂U and UA≤t−1. Ω denotes an oracle that is used to query the group authentication service, and Σ records all the session indexes which have been queried.Definition 4.
(no impersonation). The outside adversaryAO cannot impersonate a group member without being detected. Formally, a group authentication scheme is said to have the no impersonation property if we have(8)Prparams⟵Initλ;siiεU⟵″Dist″params,n″;″ci⟵Compparams,σ,Ω∪μ,siiεΩ;cμ⟵AOparams,σ,Ω∪μ,cii∈Ω;″Auth″params,σ,cii∈Ω∪μ″=1″<ελ.
In the abovementioned expression,AO is assumed to impersonate the user Uμ, where μ∉Ω.
Computational assumptions: we assume that the following assumptions hold against any PPT algorithm.Definition 5.
(discrete logarithm (DL) assumption). The description of the finite cyclic groupG is given, where G|≥q and g is a generator of G. The discrete logarithm assumption implies that there exists a negligible function ε⋅ such that for all PPT adversaries ADL, we have(9)Prx←Rℤq;x∗←ADLG,q,g,gx:x∗=x<ελ.Definition 6.
(computational Diffie–Hellman (CDH) assumption). The description of the finite cyclic groupG given, where G≥q and g is a generator of G. The computational Diffie–Hellman assumption implies that there exists a negligible function ε⋅ such that for all PPT adversaries ACDH, we have Prx←Rℤq;y←Rℤq;R←ACDHG,q,g,gx,gy:R=gxy<ελ.


## 5. An Improvement of Chien’s Scheme

### 5.1. The Proposed Scheme

The improved multiple group authentication scheme in the asynchronous communication model works as follows:(i)
Init: GM first selects two finite cyclic groupsG1 and G2 with prime order q, and a bilinear map e^:G1×G1⟶G2. P is denoted as a generator of G1. GM then selects a secret s←Rℤq and sets Q=sP. GM selects l values Ri←RG1 for i∈ℤl. GM associates the pairwise different integers w1,w2,…,wn with the group members. Finally, GM outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist.: GM selects a random polynomialfx=a0+a1x+⋯+at−1xt−1 over ℤq with degree t−1, such that a0=s. GM, then computes the credentials si=fwi, and sends them to the group members through the secure channel.(iii)
Comp: in theσ-th session, every participating user in Ω first selects ui←Rℤq and broadcasts uiRσ. Then, each user computes viRσ=∑j∈Ω,j<iujRσ−∑j∈Ω,j>iujRσ. As follows, every user computes and broadcasts her token as(10)ci=siℒiRσ+uiviRσ,whereℒi=∏jεΩ,j≠iwj/wj−wi is the Lagrange coefficient.(iv)
Auth: In theσ-th session, every user can verify whether all the users are legitimate group members by checking:(11)e^∑i∈Ωci,P=e^Rσ,Q.


### 5.2. Security Analysis

Theorem 1.
Our modified group authentication scheme satisfies the correctness property.Proof.
IfΩ⊆U and Ω≥t, the Lagrange interpolation implies that s=∑i∈Ωsiℒi, where ℒi=∏j∈Ω,j≠iwj/wj−wi is the Lagrange coefficient. Moreover, because the AV-nets have the property that ∑i∈ΩuiviRσ=0, we have(12)∑i∈Ωci=∑i∈ΩsiℒiRσ+∑i∈ΩuiviRσ,=∑i∈ΩsiℒiRσ,=sRσ.
Therefore, the equatione^∑t∈Ωci,P=e^Rσ,Q will hold, and the authentication will be successful.Theorem 2.
Our modified group authentication scheme satisfies the secrecy property, assuming that the DL problem holds inG1.Proof.
We denoteReal∏λ,params as the real run of the protocol ∏ and SIMSλ,params as the protocol simulated by a PPT simulator S with only public information as inputs.
Real∏λ,params:(i)
Init:GM generates and outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist:GM computes the credentials si=fwi and sends them to the group members through the secret channel. Without loss of generality, we assume that the credentials s1,s2,…,st−1 are learnt by the inside adversary AI.(iii)
Comp: in theσ-th session, every participating user in Ω selects ui←Rℤq and broadcasts uiRσ. Then, each user computes viRσ=∑j∈Ω,j<iujRσ−∑j∈Ω,j>iujRσ and broadcasts her token as ci=siℒiRσ+uiviRσ. In this step, AI learns u1,u2,…,ut−1 which are possessed by the corrupted users and all the broadcast values.(iv)
Auth: in theσ-th session, everyone verifies whether e^∑i∈Ωci,P=e^Rσ,Q.
SIMSλ,params:(i)
Init: the simulatorS outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist:S sends the credentials s1,s2,…,st−1 to the inside adversary AI.(iii)
Comp: We denotek=Ω. In the σ-th session, S randomly selects k values u1′,u2′,…,uk′ from ℤq and broadcasts ui′Rσ for i∈1,2,…,k. S sends u1′,u2′,…,ut−1′ to AI. S, then, randomly selects k−1 values c1′,c2′,…,ck−1′ from G1 and computes ck′=∑i∈Ωci−∑i=1k−1ci′. Then, S broadcasts the tokens c1′,c2′,…,ck′.(iv)
Auth: in theσ-th session, everyone verifies whether e^∑i∈Ωci′,P=e^Rσ,Q.
We now prove that it is infeasible for the inside adversaryAI to distinguish these two protocols. In the Init algorithm, the same public parameters params are published in both protocols. In the Dist algorithm, the same credentials s1,s2,…,st−1 are learnt by AI in both protocols. In the Comp algorithm, both sets u1,u2,…,ut−1 and u1′,u2′,…,ut−1′ are randomly distributed in ℤq, and all the broadcast values are randomly distributed in G1. In Auth, the algorithm will be successful in both protocols. Therefore, AI cannot distinguish between Real∏λ,params and SIMSλ,params because all these algorithms in AI’s view are indistinguishable. In other words, we have(13)ViewAIReal∏λ,params≅cViewAISIMSλ,params.
Moreover, based on the DL assumption,AI cannot learn any secret information of s from the public information Q=sP or ∑i∈Ωci=sRσ. Hence, our modified scheme satisfies the secrecy property.Theorem 3.
Our modified group authentication scheme satisfies the no forgery property, assuming that the CDH problem holds inG1.Proof.
We denoteX as the event that AI can predict the value sRσ from the public parameters params and Y as the event that AI has learnt some secret information through querying the oracle Ω. We denote F as the event that AI outputs a successful forgery. Then, we have(14)PrF=PrF|X∨Y⋅PrX∨Y+PrF|X¯∧Y¯⋅PrX¯∧Y¯≤PrX∨Y+PrFX¯∧Y¯≤PrX+PrY+PrFX¯∧Y¯.
In the abovementioned expression,X¯ and Y¯ denote the complements of X and Y, respectively.
Firstly, we prove thatPrX is negligible. Assume that the inside adversary AO can predict the value sRσ from the public parameters params with nonnegligible probability, e.g., AI derives sRσ from the equation e^sRσ,P=e^Rσ,Q. Then, we show that there exists another adversary ℬ who can use AI as a subroutine to break the CDH problem in G1 with nonnegligible probability. The reduction works as follows: suppose ℬ is given the description of G1 with prime order q and P is a generator of G1. Moreover, ℬ is given two random values Q=sP and Rσ=xP in G1, and ℬ’s task is to compute sRσ=sxP. In the Init algorithm, B simulates the public parameters params by selecting another cyclic group G2 with order q, a bilinear map e^:G1×G1⟶G2, as well as l−1 random values Rii∈1,2,…,l\δ in G1. B, then, sends params to AI. In the Dist algorithm, B selects t−1 random values s1,s2,…,st−1 in ℤq and sends them to AI. In the Comp algorithm, B selects t−1 random values u1,u2,…,ut−1 in ℤq and sends them to AI. B also broadcasts the required number of random values in G1. Note that the abovementioned steps generate a simulated environment for AI that is indistinguishable from a real run of our modified scheme Π. If AI outputs her predict of sRσ, B uses it to solve the CDH problem. Because it is assumed that the CDH assumption holds in G1, our hypothesis that AI can predicate the value sRσ from params with nonnegligible probability must be false. Hence, we have PrX<ε1λ for some negligible function ε1⋅.
Secondly, Theorem2 implies that the real run of our modified scheme Π does not leak any secret information to AI, based on the DL assumption in G1. Also, the hybrid argument [16] further implies that AI does not learn any secret information even if she has queried the oracle Ο polynomial number of times. Hence, we have PrY<ε2λ for some negligible function ε2⋅.
Finally, we analyze the probabilityPrFX¯∧Y¯. In this case, AI needs to guess the value sRσ. Because s is randomly distributed in ℤq and AI only controls at most t−1 group members, the probability of guessing sRσ correct in each trial is exactly 1/q. Recall that AI can try polynomial number of times, and we have PrFX¯∧Y¯=Q/q, where Q denotes the number of trials AI has made.
Putting the abovementioned analyses together, assuming that the CDH assumption holds inG1, we have(15)PrF≤PrX+PrY+PrFX¯∧Y¯<ε1λ+ε2λ+Qq≤ελ,for some negligible function ε⋅. Therefore, our modified scheme satisfies the no forgery property.Theorem 4.
Our modified group authentication scheme satisfies the no impersonation property, assuming that theCDH problem holds in G1.Proof.
DenoteX as the event that AO can predict the value sRσ from the public parameters params and F as the event that AO can impersonate a group member without being detected. Then, we have(16)PrF=PrFXPrX+PrFX¯PrX¯≤PrX+PrFX¯.
Firstly, we prove thatPrX is negligible. Assume that the outside adversary AO can predict the value sRσ from params with nonnegligible probability. Then, one can prove that there exists another adversary B who can use AO as a subroutine to break the CDH problem in G1 with nonnegligible probability. The reduction is very similar as in Theorem 3. The main difference is that B does not need to send any user’s internal states to AO. Hence, we have PrX<ελ for some negligible function ε⋅.
Next, we analyze the probabilityPrFX¯. In this case, AO needs to output a token ct+1, such that the equation ∑i=1t+1ci=sRσ holds, where the set c1,c2,…,ct denotes the other users’ tokens that AO has already learnt. Because s is randomly selected in ℤq, the value sRσ is randomly distributed in G1. Moreover, because the value sRσ is unpredictable, the probability that AO outputs a valid token is exactly 1/q. Recall that AO can try polynomial number of times, and we have PrFX¯=Q/q, where Q denotes the number of trials AO has made.
Putting the abovementioned analysis together, we conclude thatPrF<ελ+Q/q, which is negligible. Therefore, our modified scheme satisfies the no impersonation property assuming that the CDH assumption holds in G1.


### 5.3. Efficiency Analysis

We now give a brief efficiency analysis of our modified scheme. In theInit algorithm, GM selects the system parameters, including two finite cyclic group G1 and G2, a bilinear map e^ between these two groups, and some random values in G1. The computation of Q=sP takes 1 multiplication in G1. In the Dist algorithm, GM selects a random polynomial fx over ℤq with degree t−1 and evaluates this polynomial at n different points. When using Horner’s rule, each evaluation of fx takes t−1 multiplications and t additions in ℤq, and each credential is a value in ℤq. In the Comp algorithm, each user broadcasts 2 values in G1 in two individual rounds. The total computations for each user require at most n+2 multiplications and n additions in G1. Note that, in this step, the Lagrange coefficients can be precomputed beforehand. In the Auth algorithm, each user performs at most n additions in G1 and 2 bilinear maps.An efficiency comparison between our proposed scheme and Chien’s scheme [4] is given in Table 1. Denote the symbols +G1, ×G1, +ℤq, ×ℤq and ⟶ as the computations of addition in G1, multiplication in G1, addition in ℤq, multiplication in ℤq, and bilinear pairing G1×G1⟶G2, respectively. Also, we ignore the other calculations, i.e., select a random element from a group, since their costs are negligible compared with the abovementioned computations.Table 1
Comparison between our scheme and Chien’s scheme.
InitDistCompAuthChien’s scheme1×G1t−1×ℤq, t+ℤq1×G1n+G1,1⟶Our scheme1×G1t−1×ℤq, t+ℤqn+2×G1,n+G1n+G1,1⟶


## 5.1. The Proposed Scheme

The improved multiple group authentication scheme in the asynchronous communication model works as follows:(i)
Init: GM first selects two finite cyclic groupsG1 and G2 with prime order q, and a bilinear map e^:G1×G1⟶G2. P is denoted as a generator of G1. GM then selects a secret s←Rℤq and sets Q=sP. GM selects l values Ri←RG1 for i∈ℤl. GM associates the pairwise different integers w1,w2,…,wn with the group members. Finally, GM outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist.: GM selects a random polynomialfx=a0+a1x+⋯+at−1xt−1 over ℤq with degree t−1, such that a0=s. GM, then computes the credentials si=fwi, and sends them to the group members through the secure channel.(iii)
Comp: in theσ-th session, every participating user in Ω first selects ui←Rℤq and broadcasts uiRσ. Then, each user computes viRσ=∑j∈Ω,j<iujRσ−∑j∈Ω,j>iujRσ. As follows, every user computes and broadcasts her token as(10)ci=siℒiRσ+uiviRσ,whereℒi=∏jεΩ,j≠iwj/wj−wi is the Lagrange coefficient.(iv)
Auth: In theσ-th session, every user can verify whether all the users are legitimate group members by checking:(11)e^∑i∈Ωci,P=e^Rσ,Q.


## 5.2. Security Analysis

Theorem 1.
Our modified group authentication scheme satisfies the correctness property.Proof.
IfΩ⊆U and Ω≥t, the Lagrange interpolation implies that s=∑i∈Ωsiℒi, where ℒi=∏j∈Ω,j≠iwj/wj−wi is the Lagrange coefficient. Moreover, because the AV-nets have the property that ∑i∈ΩuiviRσ=0, we have(12)∑i∈Ωci=∑i∈ΩsiℒiRσ+∑i∈ΩuiviRσ,=∑i∈ΩsiℒiRσ,=sRσ.
Therefore, the equatione^∑t∈Ωci,P=e^Rσ,Q will hold, and the authentication will be successful.Theorem 2.
Our modified group authentication scheme satisfies the secrecy property, assuming that the DL problem holds inG1.Proof.
We denoteReal∏λ,params as the real run of the protocol ∏ and SIMSλ,params as the protocol simulated by a PPT simulator S with only public information as inputs.
Real∏λ,params:(i)
Init:GM generates and outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist:GM computes the credentials si=fwi and sends them to the group members through the secret channel. Without loss of generality, we assume that the credentials s1,s2,…,st−1 are learnt by the inside adversary AI.(iii)
Comp: in theσ-th session, every participating user in Ω selects ui←Rℤq and broadcasts uiRσ. Then, each user computes viRσ=∑j∈Ω,j<iujRσ−∑j∈Ω,j>iujRσ and broadcasts her token as ci=siℒiRσ+uiviRσ. In this step, AI learns u1,u2,…,ut−1 which are possessed by the corrupted users and all the broadcast values.(iv)
Auth: in theσ-th session, everyone verifies whether e^∑i∈Ωci,P=e^Rσ,Q.
SIMSλ,params:(i)
Init: the simulatorS outputs the system parameters params=G1,G2,e^,q,P,Q,Rii∈ℤl,wii∈ℤn.(ii)
Dist:S sends the credentials s1,s2,…,st−1 to the inside adversary AI.(iii)
Comp: We denotek=Ω. In the σ-th session, S randomly selects k values u1′,u2′,…,uk′ from ℤq and broadcasts ui′Rσ for i∈1,2,…,k. S sends u1′,u2′,…,ut−1′ to AI. S, then, randomly selects k−1 values c1′,c2′,…,ck−1′ from G1 and computes ck′=∑i∈Ωci−∑i=1k−1ci′. Then, S broadcasts the tokens c1′,c2′,…,ck′.(iv)
Auth: in theσ-th session, everyone verifies whether e^∑i∈Ωci′,P=e^Rσ,Q.
We now prove that it is infeasible for the inside adversaryAI to distinguish these two protocols. In the Init algorithm, the same public parameters params are published in both protocols. In the Dist algorithm, the same credentials s1,s2,…,st−1 are learnt by AI in both protocols. In the Comp algorithm, both sets u1,u2,…,ut−1 and u1′,u2′,…,ut−1′ are randomly distributed in ℤq, and all the broadcast values are randomly distributed in G1. In Auth, the algorithm will be successful in both protocols. Therefore, AI cannot distinguish between Real∏λ,params and SIMSλ,params because all these algorithms in AI’s view are indistinguishable. In other words, we have(13)ViewAIReal∏λ,params≅cViewAISIMSλ,params.
Moreover, based on the DL assumption,AI cannot learn any secret information of s from the public information Q=sP or ∑i∈Ωci=sRσ. Hence, our modified scheme satisfies the secrecy property.Theorem 3.
Our modified group authentication scheme satisfies the no forgery property, assuming that the CDH problem holds inG1.Proof.
We denoteX as the event that AI can predict the value sRσ from the public parameters params and Y as the event that AI has learnt some secret information through querying the oracle Ω. We denote F as the event that AI outputs a successful forgery. Then, we have(14)PrF=PrF|X∨Y⋅PrX∨Y+PrF|X¯∧Y¯⋅PrX¯∧Y¯≤PrX∨Y+PrFX¯∧Y¯≤PrX+PrY+PrFX¯∧Y¯.
In the abovementioned expression,X¯ and Y¯ denote the complements of X and Y, respectively.
Firstly, we prove thatPrX is negligible. Assume that the inside adversary AO can predict the value sRσ from the public parameters params with nonnegligible probability, e.g., AI derives sRσ from the equation e^sRσ,P=e^Rσ,Q. Then, we show that there exists another adversary ℬ who can use AI as a subroutine to break the CDH problem in G1 with nonnegligible probability. The reduction works as follows: suppose ℬ is given the description of G1 with prime order q and P is a generator of G1. Moreover, ℬ is given two random values Q=sP and Rσ=xP in G1, and ℬ’s task is to compute sRσ=sxP. In the Init algorithm, B simulates the public parameters params by selecting another cyclic group G2 with order q, a bilinear map e^:G1×G1⟶G2, as well as l−1 random values Rii∈1,2,…,l\δ in G1. B, then, sends params to AI. In the Dist algorithm, B selects t−1 random values s1,s2,…,st−1 in ℤq and sends them to AI. In the Comp algorithm, B selects t−1 random values u1,u2,…,ut−1 in ℤq and sends them to AI. B also broadcasts the required number of random values in G1. Note that the abovementioned steps generate a simulated environment for AI that is indistinguishable from a real run of our modified scheme Π. If AI outputs her predict of sRσ, B uses it to solve the CDH problem. Because it is assumed that the CDH assumption holds in G1, our hypothesis that AI can predicate the value sRσ from params with nonnegligible probability must be false. Hence, we have PrX<ε1λ for some negligible function ε1⋅.
Secondly, Theorem2 implies that the real run of our modified scheme Π does not leak any secret information to AI, based on the DL assumption in G1. Also, the hybrid argument [16] further implies that AI does not learn any secret information even if she has queried the oracle Ο polynomial number of times. Hence, we have PrY<ε2λ for some negligible function ε2⋅.
Finally, we analyze the probabilityPrFX¯∧Y¯. In this case, AI needs to guess the value sRσ. Because s is randomly distributed in ℤq and AI only controls at most t−1 group members, the probability of guessing sRσ correct in each trial is exactly 1/q. Recall that AI can try polynomial number of times, and we have PrFX¯∧Y¯=Q/q, where Q denotes the number of trials AI has made.
Putting the abovementioned analyses together, assuming that the CDH assumption holds inG1, we have(15)PrF≤PrX+PrY+PrFX¯∧Y¯<ε1λ+ε2λ+Qq≤ελ,for some negligible function ε⋅. Therefore, our modified scheme satisfies the no forgery property.Theorem 4.
Our modified group authentication scheme satisfies the no impersonation property, assuming that theCDH problem holds in G1.Proof.
DenoteX as the event that AO can predict the value sRσ from the public parameters params and F as the event that AO can impersonate a group member without being detected. Then, we have(16)PrF=PrFXPrX+PrFX¯PrX¯≤PrX+PrFX¯.
Firstly, we prove thatPrX is negligible. Assume that the outside adversary AO can predict the value sRσ from params with nonnegligible probability. Then, one can prove that there exists another adversary B who can use AO as a subroutine to break the CDH problem in G1 with nonnegligible probability. The reduction is very similar as in Theorem 3. The main difference is that B does not need to send any user’s internal states to AO. Hence, we have PrX<ελ for some negligible function ε⋅.
Next, we analyze the probabilityPrFX¯. In this case, AO needs to output a token ct+1, such that the equation ∑i=1t+1ci=sRσ holds, where the set c1,c2,…,ct denotes the other users’ tokens that AO has already learnt. Because s is randomly selected in ℤq, the value sRσ is randomly distributed in G1. Moreover, because the value sRσ is unpredictable, the probability that AO outputs a valid token is exactly 1/q. Recall that AO can try polynomial number of times, and we have PrFX¯=Q/q, where Q denotes the number of trials AO has made.
Putting the abovementioned analysis together, we conclude thatPrF<ελ+Q/q, which is negligible. Therefore, our modified scheme satisfies the no impersonation property assuming that the CDH assumption holds in G1.


## 5.3. Efficiency Analysis

We now give a brief efficiency analysis of our modified scheme. In theInit algorithm, GM selects the system parameters, including two finite cyclic group G1 and G2, a bilinear map e^ between these two groups, and some random values in G1. The computation of Q=sP takes 1 multiplication in G1. In the Dist algorithm, GM selects a random polynomial fx over ℤq with degree t−1 and evaluates this polynomial at n different points. When using Horner’s rule, each evaluation of fx takes t−1 multiplications and t additions in ℤq, and each credential is a value in ℤq. In the Comp algorithm, each user broadcasts 2 values in G1 in two individual rounds. The total computations for each user require at most n+2 multiplications and n additions in G1. Note that, in this step, the Lagrange coefficients can be precomputed beforehand. In the Auth algorithm, each user performs at most n additions in G1 and 2 bilinear maps.An efficiency comparison between our proposed scheme and Chien’s scheme [4] is given in Table 1. Denote the symbols +G1, ×G1, +ℤq, ×ℤq and ⟶ as the computations of addition in G1, multiplication in G1, addition in ℤq, multiplication in ℤq, and bilinear pairing G1×G1⟶G2, respectively. Also, we ignore the other calculations, i.e., select a random element from a group, since their costs are negligible compared with the abovementioned computations.Table 1
Comparison between our scheme and Chien’s scheme.
InitDistCompAuthChien’s scheme1×G1t−1×ℤq, t+ℤq1×G1n+G1,1⟶Our scheme1×G1t−1×ℤq, t+ℤqn+2×G1,n+G1n+G1,1⟶


## 6. Conclusions

In this paper, we have pointed out a security flaw in an existing group authentication scheme by Chien [4]. If this scheme was used in the asynchronous communication model, the adversary can pretend to be a legitimate group member without being detected. The major reason for this attack is that the adversary is able to remove the Lagrange coefficients from the revealed tokens. We have employed the AV-net to solve this problem, and we have rigorously proved that our improvement satisfies the desirable security properties in a well-defined security model. Therefore, our proposed protocol can be safely used as a drop-in replacement for Chien’s scheme in asynchronous networks.



---

*Source: 6183861-2020-07-13.xml*