# Group Authentication with Multiple Trials and Multiple Authentications

Authors: Hung-Yu Chien
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Group authentication aims at facilitating efficient authentication of a group of provers by a group of verifiers. A new group authentication scheme is proposed to improve the security of existent asynchronous group authentication schemes and to achieve better computational performance. The new scheme allows any groups of legitimate members to execute multiple authentication trials even under the participation of active attackers.


---

## Body

## 1. Introduction

Authentication is a must for securing computer and network applications. Conventional authentications, either user authentication or device authentication, all focus on the one-to-one scenario where one verifier aims at verifying the legitimacy of one prover at one time. As more and more Internet-of-Things (IoTs) [1, 2] applications and many social networking applications require the authentication of a group of participants efficiently, these many-to-many authentication scenarios call for new kinds of group authentications in which many verifiers would like to verify the legitimacy of many provers at one time to save cost and increase efficiency.Based on Shamir’s(t,n) secret sharing [3], Harn [4] proposed three (t,m,n) group authentication schemes, wheret represents the minimum threshold of participants, m denotes the number of participants in one trial, and n denotes the total number of members of the group. As long as the number m≥t and all these m participants are legitimate, the group authentication succeeds; otherwise, it fails. These group authentication schemes can efficiently authenticate a group of legitimate entities or act as a preprocess to detect the existence of any illegitimate participants. One of Harn’s group authentication schemes is synchronous (t,m,n) group authentication in which all participants are required to release their secret tokens simultaneously; otherwise, an illegitimate participant might forge valid tokens, using the released tokens of others. The other two schemes are the asynchronous (t,m,n) group authentication and the asynchronous (t,m,n) group authentication with multiple authentications; we, respectively, call them Harn’s asynchronous GAS1 and Harn’s asynchronous GAS2 in the rest of this paper. The two schemes all allow the participants release their tokens asynchronously; Harn’s asynchronous GAS2 further provides the group to execute multiple authentications (to recover multiple system secrets) using the same set of predistributed tokens.This paper would focus on the asynchronous schemes because the synchronous case is impractical. We find that Harn’s two asynchronous schemes could not support legitimate entities execute multiple trials even if the specific secret is not yet recovered. This weakness has two implications; if the groups of entities try several times to recover a specific secret (for group authentications), then an attacker might derive entities’ tokens and further derive the system secret; if the system only allows at most one trial for any specific secret (corresponds to a specific group authentication), then an attacker can easily paralyze the system by simply releasing invalid tokens. In Harn’s publication [4], it only emphasizes that once a secret is recovered, then the corresponding group authentication is no longer valid; however, the security of the cases that the members try several times for the not-yet-recovered secret has been neglected.This paper will show the weaknesses of Harn’s asynchronous schemes and propose a new scheme to conquer the weaknesses and improve the efficiency. This rest of this paper is organized as follows. Section2 reviews Harn’s asynchronous schemes. Section 3 shows the weaknesses. Section 4 proposes our new scheme, and Section 5 analyzes its securities and evaluates its performance. Section 6 states our conclusions.


## 2. Review of Harn’s Asynchronous Group Authentication Schemes (GAS)

The schemes consist of two phases: the initialization phase and the group authentication phase. The group manager (GM) initializes the system parameters and assigns each registered entity some secret tokens in the initialization phase. Then, any groups ofm legitimate entities with m≥t can execute the group authentication to verify the legitimacy of the participating entities.


### 2.1.(t,m,n) Asynchronous GAS-Harn’s Asynchronous GAS1

Initially, the group manager (GM) selectsk (where kt>n-1) random polynomials with degree t-1, flx=al,0+al,1x+⋯+al,t-1xt-1modp,l=1,…,k, where p is a prime and al,i∈RZp. He also generates and assigns secret tokens fl(xi),l=1,…,k, to each entity Ui∈U={U1,…,Un}, where xi is Ui’s public identity. For any secret s, the GM finds integers dj,wj,j=1~k, in GF(p), such that s=∑j=1~kdjfjwjmodp, where wi≠wj for every pair of i and j. The GM publishes these parameters dj,wj,j=1~k, and h(s), where h() is a secure cryptographic hash function.Whenm(m≥t) entities P~={P1,…,Pm} would like to authenticate each other, each Pi computes and releases ci=∑j=1kdjfj(xi)∏r=1,r≠imwj-xr/xi-xrmodp. After gathering all the released values, the participants compute s′=∑i=1mcimodp and verify whether the equation h(s)=?h(s′) holds. If the verification succeeds, then the group authentication succeeds; otherwise, it fails. This scheme only allows one valid group authentication.


### 2.2.(t,m,n) Asynchronous GAS with Multiple Authentications-Harn’s Asynchronous GAS2

The(t,m,n) asynchronous GAS with multiple authentications allows the tokens to be reused for multiple authentications (for multiple secrets).Initially, the GM selects two large primesp and q, such that q divides p-1, GF(q) is a subgroup of GF(p), and every gi is a generator for the subgroup GF(q). The GM selects two random polynomials, fl(x),l=1,2, having degree t-1 each with coefficients in GF(p). The GM generates tokens, fl(x),l=1,2, for each registered member Ui. The GM selects multiple secrets sis. For each secret si, the GM selects wi,j,di,j,j=1,2, in GF(q), where wi,1≠wi,2. The secret si is determined as si=gi∑j=12di,jf(wi,j)modqmodp. The GM publishes these numbers wi,j,di,j,j=1,2, and gi,hsi.Whenm(m≥t) entities P~={P1,…,Pm} would like to perform the group authentication corresponding to the reconstruction of the secret si, each participant Pv∈P~ computes cv=∑j=12djfj(xv)∏r=1,r≠vm((wj-xr)/(xv-xr))modq and ev=gicvmodp. Each Pv releases ev. After collecting all evs,v=1,…,m, the participating entities compute si′=∏v=1mev and check whether h(si′)=?h(si) holds. If it holds, then the group authentication succeeds; otherwise, it fails.


## 2.1.(t,m,n) Asynchronous GAS-Harn’s Asynchronous GAS1

Initially, the group manager (GM) selectsk (where kt>n-1) random polynomials with degree t-1, flx=al,0+al,1x+⋯+al,t-1xt-1modp,l=1,…,k, where p is a prime and al,i∈RZp. He also generates and assigns secret tokens fl(xi),l=1,…,k, to each entity Ui∈U={U1,…,Un}, where xi is Ui’s public identity. For any secret s, the GM finds integers dj,wj,j=1~k, in GF(p), such that s=∑j=1~kdjfjwjmodp, where wi≠wj for every pair of i and j. The GM publishes these parameters dj,wj,j=1~k, and h(s), where h() is a secure cryptographic hash function.Whenm(m≥t) entities P~={P1,…,Pm} would like to authenticate each other, each Pi computes and releases ci=∑j=1kdjfj(xi)∏r=1,r≠imwj-xr/xi-xrmodp. After gathering all the released values, the participants compute s′=∑i=1mcimodp and verify whether the equation h(s)=?h(s′) holds. If the verification succeeds, then the group authentication succeeds; otherwise, it fails. This scheme only allows one valid group authentication.


## 2.2.(t,m,n) Asynchronous GAS with Multiple Authentications-Harn’s Asynchronous GAS2

The(t,m,n) asynchronous GAS with multiple authentications allows the tokens to be reused for multiple authentications (for multiple secrets).Initially, the GM selects two large primesp and q, such that q divides p-1, GF(q) is a subgroup of GF(p), and every gi is a generator for the subgroup GF(q). The GM selects two random polynomials, fl(x),l=1,2, having degree t-1 each with coefficients in GF(p). The GM generates tokens, fl(x),l=1,2, for each registered member Ui. The GM selects multiple secrets sis. For each secret si, the GM selects wi,j,di,j,j=1,2, in GF(q), where wi,1≠wi,2. The secret si is determined as si=gi∑j=12di,jf(wi,j)modqmodp. The GM publishes these numbers wi,j,di,j,j=1,2, and gi,hsi.Whenm(m≥t) entities P~={P1,…,Pm} would like to perform the group authentication corresponding to the reconstruction of the secret si, each participant Pv∈P~ computes cv=∑j=12djfj(xv)∏r=1,r≠vm((wj-xr)/(xv-xr))modq and ev=gicvmodp. Each Pv releases ev. After collecting all evs,v=1,…,m, the participating entities compute si′=∏v=1mev and check whether h(si′)=?h(si) holds. If it holds, then the group authentication succeeds; otherwise, it fails.


## 3. The Weaknesses of Harn’s Asynchronous Schemes

We find that both Harn’s asynchronous GAS1 and Harn’s asynchronous GAS2 share one critical weakness. The schemes perform group authentication by recovering and verifying the sealed secret. If the schemes allow users to launch several trials before the secret is recovered, then an attacker would recover both the system secrets and the users’ secret tokens by joining the process several times. On the other hand, if each secret only allows one trial of authentication no matter whether the specific secret is recovered or not, then the system is vulnerable to Denial of Service (DOS) attacks by simply releasing a false value to spoil the authentication instance and the group authentication function of the system. After releasing a fake data, any groups of valid members can no longer perform any group authentications.The key idea of our attack on Harn’s asynchronous GAS1 is introduced in the following phases.Phase 1.
Even though the secret tokensfj(xi)s are well protected in the released value ci=∑j=1kdjfj(xi)∏r=1,r≠im((wj-xr)/(xi-xr))modp, one could solve these unknown variables fj(xi)s as long as he getsk distinct {ci}, where each ci corresponds to the value released by a specific user Ui in an authentication instance and there is at least one member different in any pair of groups in these authentication instances; in such cases, the attacker will havek independent equations withk unknown variables fj(xi)s and he can solve the equations. Let Fi≡{fj(xi)∣1≤i≤k}={f1(xi),…,fk(xi)} denote the set of secret tokens owned by the user Ui; after the above attack, the attacker can acquire Fi. Now the attacker continues the next phase to acquire the secret polynomials.Phase 2.
The attacker repeatedly involves the authentication instances and acquires the secret tokens until he gets the secret tokens of more thant users. Denote these secret token set as F≡{F1,…,Fi,…,Ft}={{f1(x1),…,fk(x1)},…,{f1(xi),…,fk(xi)},…,{f1xt,…,fk(xt)}}. At this point, he organizes these secret tokens as F1={f1(x1),f1(x2),…,f1(xt)}, F2={f2(x1),f2(x2),…,f2(xt)},…,Fk={fk(x1),fk(x2),…,fk(xt)}. Based on Fi,1≤i≤k, the attacker applies the Lagrange polynomial equation to reconstruct the polynomials fi(x),1≤i≤k. The attacker then continues the next phase to derive the system secrets and the secret tokens of other remaining members.Phase 3.
Using the polynomialsfi(x),1≤i≤k, the attacker compute s=∑j=1~kdjfj(wj)modp for the system secret. For any user Ur∈U={U1,…,Un} and the secret tokens of Ur that have not yet been disclosed, the attacker computes {f1(xr),…,fk(xr)}. At this point, the attacker has derived all the system secrets and all the secret tokens of all users. The minimum number of runs that the attacker should participate in is k.The above attack can be easily extended to plot on Harn’s asynchronous GAS2. Attackers can acquire the secret values{(gif1(xv),gif2(xv))∣∀ valid i and 1≤v≤n} corresponding to the secret tokens {f1(xv),f2(xv)∣1≤v≤n} and the system secrets si=gi∑j=12di,jf(wi,j)modqmodp.Example 1.
Now we take one example to demonstrate the attack process.
System Initialization. Let p=11, t=3, n=6, k=2, (d1=1,w1=6), and (d2=2,w1=7) be the system parameters. f1(x)=1+2x+2x2mod11 and f2(x)=2+2x+1x2mod11 are the two secret polynomials, and the system secret is s=1·f1(6)+2·f2(7)mod11=8+20mod11=6. The group of users, U, is {Ui with identity xi=i,1≤i≤6}. U1 gets the secret tokens (f1(1)=5,f2(1)=5), U2 gets the secret tokens (f1(2)=2,f2(2)=10), U3 gets the secret tokens (f1(3)=3,f2(3)=6), U4 gets the secret tokens (f1(4)=8,f2(4)=4), U5 gets the secret tokens (f1(5)=6,f2(5)=4), and U6 gets the secret tokens (f1(6)=8,f2(6)=6).
Now we show the attack.
Attack Phase1. Assume that the attacker A participates in two runs of authentications with {U1,U2,U3} and, respectively, impersonates U4,U5 in these runs.
In run 1,A will get(1)ci=∑j=12djfjxi∏r=1,r≠i4wj-xrxi-xrmodp∣1≤i≤3.We list the calculations as follows:(2)c1=∑j=12djfj1∏r=1,r≠14wj-r1-r=1·f116-26-36-41-21-31-4+2·f217-27-37-41-21-31-4=1·5·4·3·2-1·-2·-3+2·5·5·4·3-1·-2·-3=1·5·7+2·5·1=1c2=∑j=12djfj2∏r=1,r≠24wj-r2-r=1·f126-16-36-42-12-32-4+2·f227-17-37-42-12-32-4=1·2·5·3·21·-1·-2+2·10·6·4·31·-1·-2=1·2·4+2·10·3=2c3=∑j=12djfj3∏r=1,r≠34wj-r3-r=1·f136-16-26-43-13-23-4+2·f237-17-27-43-13-23-4=1·3·5·4·22·1·-1+2·6·6·5·32·1·-1=1·3·2+2·6·10=5.
In run 2,A will get(3)ci=∑j=12djfjxi∏r∈1,2,3,5,r≠iwj-xrxi-xrmodp∣1≤i≤3as follows:(4)c1=∑j=12djfj1∏r=2,3,5wj-r1-r=1·f116-26-36-51-21-31-5+2·f217-27-37-51-21-31-5=1·5·4·3·1-1·-2·-4+2·5·5·4·2-1·-2·-4=1·5·4+2·5·6=3c2=∑j=12djfj2∏r=1,3,5wj-r2-r=1·f126-16-36-52-12-32-5+2·f227-17-37-52-12-32-5=1·2·5·3·11·-1·-3+2·10·6·4·21·-1·-3=1·2·5+2·10·5=0c3=∑j=12djfj3∏r=1,2,5wj-r3-r=1·f136-16-26-53-13-23-5+2·f237-17-27-53-13-23-5=1·3·5·4·12·1·-2+2·6·6·5·22·1·-2=3.
So nowA has the following independent equations in (5a), (5b), and (5c). He then solves the equations and gets f1(1)=5,f2(1)=5,f1(2)=2,f2(2)=10,f1(3)=3,f2(3)=6. (5a)7f11+2f21=1mod11,4f11+f21=3mod11(5b)4f12+6f22=2mod11,5f12+10f22=0mod11(5c)2f13+9f23=5mod11,6f13+3f23=3mod11.
A applies the Lagrange polynomial formula on (f1(1)=5,f1(2)=2,f1(3)=3) and derives the polynomial f1(x)=1+2x+2x2mod11, applies the formula on (f2(1)=5,f2(2)=10,f2(3)=6), and derives f2(x)=2+2x+1x2mod11. Finally, he computes s=1·f1(6)+2·f2(7)mod11=8+20mod11=6. He can further computes the secret tokens of other remaining members {(f1(i),f2(i))∣4≤i≤6}.


## 4. An Improved Scheme That Enables Multiple Trials and Multiple Authentications

Now we will propose an improved scheme that not only conquers the weaknesses of Harn’s(t,m,n) asynchronous schemes but also improves the system performance. The GM in our scheme only publishes simple public data and the members can execute group authentication with multiple authentications and multiple trials.


### 4.1. Preliminaries

We shall propose our scheme, based on elliptic curve cryptography and bilinear pairing. We now briefly review them as follows.Elliptic curves overGF(p) [6]: a nonsupersingular elliptic curve E(Fp) is the set of points P=(x,y), for x,y∈ZP satisfying the equation y2≡x3+ax+bmodp, where a,b∈Zp are constants such that 4a3+27b2≠0modp, together with the pointO called the point at infinity. Two points P=(x1,y1) and Q=(x2,y2) on the elliptic curveE can be added together using the following rule: if x2=x1 and y2=-y1, then P+Q=O; otherwise, P+Q=(x3,y3) where x3=λ2-x1-x2modp, y3=λ(x1-x3)-y1modp, and λ=(y2-y1)/(x2-x1) if P≠Q or λ=(3x12+a)/(2y1) if P=Q.Definition 2 (nondegenerate, bilinear, computable map [7]).
LetG1,G2, and G3 be cyclic groups of prime order q, where G1 and G2 are additive groups on elliptic curves and G3 is multiplicative. Let e: G1×G2→G3 be a map with the following properties: (1)
Nondegenerate: there existsX,Y∈G1,G2 such that e(X,Y)≠1.(2)
Bilinear:e(X1+X2,Y)=e(X1,Y)·e(X2,Y) and e(X,Y1+Y2)=e(X,Y1)·e(X,Y2).(3)
Computability: there exist efficient algorithms to computee(P,Q) for all P,Q∈G1,G2.Definition 3.
The elliptic curve discrete logarithm problem (ECDLP) [6] is as follows: given an elliptic curve over a finite field Fp and two points P,Q∈E(Fp), find a number k such that Q=kP.Definition 4 (the Bilinear Pairing Inversion (BPI) problem [7]).
Givene(P,Q)∈G3 and Q∈G2, find P.Definition 5.
The computational elliptic curve Diffie-Hellman problem (ECDHP) [6] is as follows: given an elliptic curve over a finite field Fp, a point P∈E(Fp) of order q, and points A=aP,B=bP∈P, find the point C=abP.It is believed that the ECDHP, the ECDLP, and the BPI are hard problems for proper parameter setting.


### 4.2. The Proposed Scheme

#### 4.2.1. The System Model

Here we describe the model for one group, and it is easy to extend this model for several groups. In the system, there are two kinds of participants: the GM and a group of registered members. The GM is responsible for setting up/updating the system parameters. After initialization, the participants in each session would like to verify whether all the participants belong to the same group; this verification is achieved by the validation of the aggregated released-shares. The GM is trusted, and registered members might be compromised and disclose their secrets. Unless being compromised, a registered member always behaves honestly.The GM publishes a predetermined parametert. The scheme can verify whether all participants of one session with m participants (m≥t) belong to the same group. The scheme is secure if it can withstand the collusion of up to t-1 insiders (registered members).


#### 4.2.2. The Scheme Facilitating Multiple Trials and Multiple Authentications without Server’s Active Participation

Like Harn’s asynchronous(t,m,n) schemes, our scheme also follows the same (t,m,n) notation, the asynchronous communication, and multiple authentications. Additionally, our scheme allows multiple trials. The GM only needs to publish some simple data no matter how many authentications and trails these members would like to perform. The scheme consists of two phases: the initialization phase and the group authentication phase.Initialization. The GM sets up three cyclic groups G1, G2, and G3 with orderq, where G1 and G2 are additive groups on elliptic curves and G3 is multiplicative.P is a generator for G2. It chooses a secret random polynomial with degree t-1, fx=a0+a1x+⋯+at-1xt-1modq with a0=s, and a master secret s. It computes Q=sP and publishes Q as the system-wise public key. For each registered member Ui∈U={U1,…,Un} with identity xi, it assigns f(xi) as Ui’s secret token.Group Authentication. When m(m≥t) entities P~={P1,…,Pm} would like to authenticate each other in the vth authentication instance, the group of users agree on a random point Rv (we discuss two options of implementing the generation of random points Rvs in Section 4.3). Each Pi∈P~ computes ci=f(xi)∏r=1,r≠im(-xr/(xi-xr)) and ciRv and releases ciRv. After all users release their values, they compute ∑i=1m‍ciRv and verify whether the equation e(∑i=1mciRv,P)=?e(Rv,Q) holds. If it holds, they satisfy the group authentication; otherwise, they fail.


### 4.3. Implementation Options of ChoosingRv

The generation and selection of the random pointsRv play a crucial factor affecting the security. Here, we discuss two possible options. The two options mainly tackle the possible threat that an adversary might manipulate the selection of Rv.The first one is that the GM periodically updates a list of authenticated random points, and the entities choose one from the list of unused ones. The entities refuse to apply any points that they have used.The second approach is applying a one-way hash function that maps any strings to a random point—H1:{0,1}∗→G1. Boneh and Franklin’s MaptoPoint function is one of such functions [7]. In this approach, each participant in the group calculates Rv = H1(date∥time∥x1∥x2∥⋯∥xm), where date and time are the current timestamp and xis are the participants’ identities.


### 4.4. Comparison of Our Improvements with One Possible Extension of Harn’s GAS2

In addition to our proposed scheme, one another possible improvement is by extending Harn’s GAS2. The system might require that each participant never tries to recover one specific secret twice; that is, whenever an authentication fails, he should only try another authentication corresponding to other secrets. This arrangement could prevent the attacks in Section3.However, we would like to discuss the differences between the above extension with our scheme. The extension, even though it could reduce the treats of our attacks, is still not absolutely immune to DOS attacks. The GM has to preselect lots of possible secrets and publishes these numberswi,j,di,j,j=1,2, and {(gi,hsi)}. If the list is not large enough, then the successive releasing of false shares could quickly deplete the list. If the GM tries to prepare a very long list, it causes it lots of overhead.On the contrary, our implementation Option 2 is much more simple, efficient, and withstand heavy DOS attacks.


## 4.1. Preliminaries

We shall propose our scheme, based on elliptic curve cryptography and bilinear pairing. We now briefly review them as follows.Elliptic curves overGF(p) [6]: a nonsupersingular elliptic curve E(Fp) is the set of points P=(x,y), for x,y∈ZP satisfying the equation y2≡x3+ax+bmodp, where a,b∈Zp are constants such that 4a3+27b2≠0modp, together with the pointO called the point at infinity. Two points P=(x1,y1) and Q=(x2,y2) on the elliptic curveE can be added together using the following rule: if x2=x1 and y2=-y1, then P+Q=O; otherwise, P+Q=(x3,y3) where x3=λ2-x1-x2modp, y3=λ(x1-x3)-y1modp, and λ=(y2-y1)/(x2-x1) if P≠Q or λ=(3x12+a)/(2y1) if P=Q.Definition 2 (nondegenerate, bilinear, computable map [7]).
LetG1,G2, and G3 be cyclic groups of prime order q, where G1 and G2 are additive groups on elliptic curves and G3 is multiplicative. Let e: G1×G2→G3 be a map with the following properties: (1)
Nondegenerate: there existsX,Y∈G1,G2 such that e(X,Y)≠1.(2)
Bilinear:e(X1+X2,Y)=e(X1,Y)·e(X2,Y) and e(X,Y1+Y2)=e(X,Y1)·e(X,Y2).(3)
Computability: there exist efficient algorithms to computee(P,Q) for all P,Q∈G1,G2.Definition 3.
The elliptic curve discrete logarithm problem (ECDLP) [6] is as follows: given an elliptic curve over a finite field Fp and two points P,Q∈E(Fp), find a number k such that Q=kP.Definition 4 (the Bilinear Pairing Inversion (BPI) problem [7]).
Givene(P,Q)∈G3 and Q∈G2, find P.Definition 5.
The computational elliptic curve Diffie-Hellman problem (ECDHP) [6] is as follows: given an elliptic curve over a finite field Fp, a point P∈E(Fp) of order q, and points A=aP,B=bP∈P, find the point C=abP.It is believed that the ECDHP, the ECDLP, and the BPI are hard problems for proper parameter setting.


## 4.2. The Proposed Scheme

### 4.2.1. The System Model

Here we describe the model for one group, and it is easy to extend this model for several groups. In the system, there are two kinds of participants: the GM and a group of registered members. The GM is responsible for setting up/updating the system parameters. After initialization, the participants in each session would like to verify whether all the participants belong to the same group; this verification is achieved by the validation of the aggregated released-shares. The GM is trusted, and registered members might be compromised and disclose their secrets. Unless being compromised, a registered member always behaves honestly.The GM publishes a predetermined parametert. The scheme can verify whether all participants of one session with m participants (m≥t) belong to the same group. The scheme is secure if it can withstand the collusion of up to t-1 insiders (registered members).


### 4.2.2. The Scheme Facilitating Multiple Trials and Multiple Authentications without Server’s Active Participation

Like Harn’s asynchronous(t,m,n) schemes, our scheme also follows the same (t,m,n) notation, the asynchronous communication, and multiple authentications. Additionally, our scheme allows multiple trials. The GM only needs to publish some simple data no matter how many authentications and trails these members would like to perform. The scheme consists of two phases: the initialization phase and the group authentication phase.Initialization. The GM sets up three cyclic groups G1, G2, and G3 with orderq, where G1 and G2 are additive groups on elliptic curves and G3 is multiplicative.P is a generator for G2. It chooses a secret random polynomial with degree t-1, fx=a0+a1x+⋯+at-1xt-1modq with a0=s, and a master secret s. It computes Q=sP and publishes Q as the system-wise public key. For each registered member Ui∈U={U1,…,Un} with identity xi, it assigns f(xi) as Ui’s secret token.Group Authentication. When m(m≥t) entities P~={P1,…,Pm} would like to authenticate each other in the vth authentication instance, the group of users agree on a random point Rv (we discuss two options of implementing the generation of random points Rvs in Section 4.3). Each Pi∈P~ computes ci=f(xi)∏r=1,r≠im(-xr/(xi-xr)) and ciRv and releases ciRv. After all users release their values, they compute ∑i=1m‍ciRv and verify whether the equation e(∑i=1mciRv,P)=?e(Rv,Q) holds. If it holds, they satisfy the group authentication; otherwise, they fail.


## 4.2.1. The System Model

Here we describe the model for one group, and it is easy to extend this model for several groups. In the system, there are two kinds of participants: the GM and a group of registered members. The GM is responsible for setting up/updating the system parameters. After initialization, the participants in each session would like to verify whether all the participants belong to the same group; this verification is achieved by the validation of the aggregated released-shares. The GM is trusted, and registered members might be compromised and disclose their secrets. Unless being compromised, a registered member always behaves honestly.The GM publishes a predetermined parametert. The scheme can verify whether all participants of one session with m participants (m≥t) belong to the same group. The scheme is secure if it can withstand the collusion of up to t-1 insiders (registered members).


## 4.2.2. The Scheme Facilitating Multiple Trials and Multiple Authentications without Server’s Active Participation

Like Harn’s asynchronous(t,m,n) schemes, our scheme also follows the same (t,m,n) notation, the asynchronous communication, and multiple authentications. Additionally, our scheme allows multiple trials. The GM only needs to publish some simple data no matter how many authentications and trails these members would like to perform. The scheme consists of two phases: the initialization phase and the group authentication phase.Initialization. The GM sets up three cyclic groups G1, G2, and G3 with orderq, where G1 and G2 are additive groups on elliptic curves and G3 is multiplicative.P is a generator for G2. It chooses a secret random polynomial with degree t-1, fx=a0+a1x+⋯+at-1xt-1modq with a0=s, and a master secret s. It computes Q=sP and publishes Q as the system-wise public key. For each registered member Ui∈U={U1,…,Un} with identity xi, it assigns f(xi) as Ui’s secret token.Group Authentication. When m(m≥t) entities P~={P1,…,Pm} would like to authenticate each other in the vth authentication instance, the group of users agree on a random point Rv (we discuss two options of implementing the generation of random points Rvs in Section 4.3). Each Pi∈P~ computes ci=f(xi)∏r=1,r≠im(-xr/(xi-xr)) and ciRv and releases ciRv. After all users release their values, they compute ∑i=1m‍ciRv and verify whether the equation e(∑i=1mciRv,P)=?e(Rv,Q) holds. If it holds, they satisfy the group authentication; otherwise, they fail.


## 4.3. Implementation Options of ChoosingRv

The generation and selection of the random pointsRv play a crucial factor affecting the security. Here, we discuss two possible options. The two options mainly tackle the possible threat that an adversary might manipulate the selection of Rv.The first one is that the GM periodically updates a list of authenticated random points, and the entities choose one from the list of unused ones. The entities refuse to apply any points that they have used.The second approach is applying a one-way hash function that maps any strings to a random point—H1:{0,1}∗→G1. Boneh and Franklin’s MaptoPoint function is one of such functions [7]. In this approach, each participant in the group calculates Rv = H1(date∥time∥x1∥x2∥⋯∥xm), where date and time are the current timestamp and xis are the participants’ identities.


## 4.4. Comparison of Our Improvements with One Possible Extension of Harn’s GAS2

In addition to our proposed scheme, one another possible improvement is by extending Harn’s GAS2. The system might require that each participant never tries to recover one specific secret twice; that is, whenever an authentication fails, he should only try another authentication corresponding to other secrets. This arrangement could prevent the attacks in Section3.However, we would like to discuss the differences between the above extension with our scheme. The extension, even though it could reduce the treats of our attacks, is still not absolutely immune to DOS attacks. The GM has to preselect lots of possible secrets and publishes these numberswi,j,di,j,j=1,2, and {(gi,hsi)}. If the list is not large enough, then the successive releasing of false shares could quickly deplete the list. If the GM tries to prepare a very long list, it causes it lots of overhead.On the contrary, our implementation Option 2 is much more simple, efficient, and withstand heavy DOS attacks.


## 5. Security Analysis and Performance Evaluation

### 5.1. The Security

Lemma 6.
Given a random pointRv and a group of members P~={U1,,…,Um} with m≥t, the only condition that the groupP can reconstruct the value sRv in the proposed scheme is that all the participating members are valid and the scheme can resist up to t-1 colluded insiders.Proof.
Since the secret tokens are generated using a secrett-1-degree polynomial, the scheme can resist the collusion of up to t-1 insiders. Also, any single invalid contribution from any invalid participants would ruin the computation of sRv.Lemma 7.
Given a valid released valueciRv, where ci=f(xi)∏r=1,r≠im(-xr/(xi-xr)), one cannot derive the value ci and the corresponding f(xi) as long as the ECDLP is hard.Lemma 8.
Given a valid releasedciRv and another point R~, one cannot derive the value ciR~ as long as the ECDHP is hard.Lemma 9.
Given the valuese(Rv,Q) and Q, one cannot derive the value ∑i=1m‍ciRv which satisfies e(∑i=1m‍ciRv,P)=?e(Rv,Q) as long as the BPI is hard.Based on the above lemmas, we have the following theorem.Theorem 10.
The proposed scheme satisfies the security requirements of the asynchronous(t,m,n) group authentication.


### 5.2. The Performance

We first compare the computational complexities of the three schemes: ours, Harn’s GAS1, and Harn’s GAS2.LetTh denote the time complexity for one hash operation, TEM denote that of one elliptic curve point multiplication, TEA denote that for one elliptic curve point addition, Tmul,q denote that for one multiplication in field q (where q corresponds to the order of G1,G2,G3 in our scheme), Tinv,q denote that for one inverse operation in field q, Tmul,p denote that for one multiplication in field p (where p corresponds to the modular field in Harn’s schemes), Tinv,p denote that for one multiplication in field p, Texp,p/Texp,q, respectively, denote that for one exponentiation in field p/q, and Tpair denote that for one pairing.Each userUi in our scheme needs to compute one Lagrange component ci=f(xi)∏r=1,r≠im(-xr/xi-xr), one ciR, m-1 point additions in G1, and the verification e(∑i=1m‍ciR,P)=?e(R,Q). The verification costs two pairing operations (2Tpair,G1). The addition in G1 costs mTEA. The computation of ciR costs TEM, and the computation of ci costs (2(m-1)+2)Tmul,q+ Tinv,q. So totally it takes (2(m-1)+2)Tmul,q+Tinv,q+TEM+mTEA+2Tpair.Each participant in Harn’s GAS1 takesk[(2(m-2)+3)Tmul,p+Tinv,p] for computing ci, takes (m-1)Tadd,p for computing s′, and takes 1Th for verifying h(s)=?h(s′). Each participant totally takes k[(2(m-2)+3)Tmul,p+Tinv,p]+(m-1)Tadd,p+1Th.Each participant in Harn’s GAS2 takes[(2(m-2)+3)Tmul,q+Tinv,q] for computing cv, takes Texp,p for computing ev, takes (m-1)Tmul,p for computing si′, and takes 1Th for verifying h(si)=?h(si′). Each participant totally takes [(2(m-2)+3)Tmul,q+Tinv,q]+Texp,p+(m-1)Tmul,p+1Th.Table1 summarizes the performance. Row 2 lists the security properties. Only our scheme can resist an attacker from deriving the secrets when the schemes allow multiple trials. Row 3 lists the detailed computational complexity. Based on Row 3, it is still difficult to get an insight of the complexities since they involve quite different operations. We, therefore, further evaluate the computational cost under the practical setting from NSA [8] and the algebra equations of elliptic curve operations [6]. The security of ECC with 160-bit key is roughly equivalent to that of RSA with 1024-bit key or D-H algorithm with 1024-bit key. So let us assume that theq (the order of G1 and G2) in our scheme is 160 bits, andp in Harn’s schemes is 1024 bits. Under the above setting and approximations, Tmul,p (the time complexity of a field multiplication in Zp, wherep is 1024 bits) is 41 times Tmul,q (the time complexity of field multiplication in Zq, whereq is 160 bits), TEM≅29Tmul,p,TEA≅0.12Tmul,p,Texp,p≅240Tmul,p≅8TEM, and TEM≅241TEA, where ≅ means “roughly equal.”Table 1
Summaries of performance of group authentication schemes.
Ours
Harn’s GAS1
Harn’s GAS2
Securities under multiple trials for each secret
Allow multiple authentications with multiple trials
Attackers can disclose system’s secrets and users’ secret tokens
Attackers can disclose system’s secrets and users’ secret tokens
Each user’s computational cost for one group authentication (detailed)
(
2
(
m
-
1
)
+
2
)
T
m
u
l
,
q
+
T
i
n
v
,
q
+
T
E
M
+
m
T
E
A
+
2
T
p
a
i
r
k
[
(
2
(
m
-
2
)
+
3
)
T
m
u
l
,
p
+
T
i
n
v
,
p
]
+
(
m
-
1
)
T
a
d
d
,
p
+
1
T
h
2
[
(
2
(
m
-
2
)
+
3
)
T
m
u
l
,
q
+
T
i
n
v
,
q
]
+
T
e
x
p
,
p
+
(
m
-
1
)
T
m
u
l
,
p
+
1
T
h
Approximated complexities (based on the figures from [5])
(
7
m
+
1429
)
T
m
u
l
,
q
+
2
T
p
a
i
r
≅
(
7
m
+
6785
)
T
m
u
l
,
q
41
k
(
2
m
+
239
)
T
m
u
l
,
q
+
(
m
-
1
)
T
a
d
d
,
p
+
1
T
h
≅
41
k
(
2
m
+
239
)
T
m
u
l
,
q
+
(
m
-
1
)
T
a
d
d
,
p
(45m+1418)Tmul,qUsing the above setting and approximations and neglecting the minor computations like hashing and field addition, the complexities in Row 3 can be further simplified as follows. The complexity of our scheme is as follows:(2(m-1)+2)Tmul,q+Tinv,q+TEM+mTEA+2Tpair≅(2(m-1)+2)Tmul,q+Tinv,q+29Tmul,p+0.12mTmul,p + 2Tpair≅2mTmul,q+240Tmul,q+29∗41Tmul,q+0.12m∗41Tmul,p+2Tpair≅(7m+1429)Tmul,q+2Tpair. The complexity of Harn’s GAS1 is as follows: k[(2(m-2)+3)Tmul,p+Tinv,p]+(m-1)Tadd,p+1Th≅41k(2m+239)Tmul,q+(m-1)Tadd,p. The complexity of Harn’s GAS2 is as follows: 2[(2(m-2)+3)Tmul,q+Tinv,q]+Texp,p+(m-1)Tmul,p + 1Th≅2[(2(m-2)+239)Tmul,q]+240∗41Tmul,q+41(m-1)Tmul,q + 1Th≅(45m+1418)Tmul,q.To further simplify the complexity approximation, we refer to an efficient paring implementation [5]. Based on the figures there [5], we roughly approximate one pairing operation as 5356Tmul,q. We approximate (7m+1429)Tmul,q+2Tpair≅(7m+6785)Tmul,q in Row 4. From Row 4, we can tell that Harn’s schemes have lower computational cost than ours when the number of participants is small; but the costs of Harn’s schemes grow faster than ours when the number of participants increases. All the costs of the three schemes increase as the number of participants increases, but the cost of Harn’s GAS1 also depends on the valuek. Because the parameterk in Harn’s GAS1 should satisfy kt>n-1, we only compare our scheme with Harn’s GAS2 in Figure 1 to give us an insight of the performances of the three schemes. From Figure 1, we can see that the cost of Harn’s GAS2 increases much faster than ours when the number of participants increases. When the number is around 141, the cost of Harn’s GAS2 overpasses ours and increases very fast. The comparison shows that our scheme not only owns better security but also provides better computational performance when the number of participants is large.Figure 1
The comparison of computational cost versus the number of participants. The unit of the cost isTmul,q.


## 5.1. The Security

Lemma 6.
Given a random pointRv and a group of members P~={U1,,…,Um} with m≥t, the only condition that the groupP can reconstruct the value sRv in the proposed scheme is that all the participating members are valid and the scheme can resist up to t-1 colluded insiders.Proof.
Since the secret tokens are generated using a secrett-1-degree polynomial, the scheme can resist the collusion of up to t-1 insiders. Also, any single invalid contribution from any invalid participants would ruin the computation of sRv.Lemma 7.
Given a valid released valueciRv, where ci=f(xi)∏r=1,r≠im(-xr/(xi-xr)), one cannot derive the value ci and the corresponding f(xi) as long as the ECDLP is hard.Lemma 8.
Given a valid releasedciRv and another point R~, one cannot derive the value ciR~ as long as the ECDHP is hard.Lemma 9.
Given the valuese(Rv,Q) and Q, one cannot derive the value ∑i=1m‍ciRv which satisfies e(∑i=1m‍ciRv,P)=?e(Rv,Q) as long as the BPI is hard.Based on the above lemmas, we have the following theorem.Theorem 10.
The proposed scheme satisfies the security requirements of the asynchronous(t,m,n) group authentication.


## 5.2. The Performance

We first compare the computational complexities of the three schemes: ours, Harn’s GAS1, and Harn’s GAS2.LetTh denote the time complexity for one hash operation, TEM denote that of one elliptic curve point multiplication, TEA denote that for one elliptic curve point addition, Tmul,q denote that for one multiplication in field q (where q corresponds to the order of G1,G2,G3 in our scheme), Tinv,q denote that for one inverse operation in field q, Tmul,p denote that for one multiplication in field p (where p corresponds to the modular field in Harn’s schemes), Tinv,p denote that for one multiplication in field p, Texp,p/Texp,q, respectively, denote that for one exponentiation in field p/q, and Tpair denote that for one pairing.Each userUi in our scheme needs to compute one Lagrange component ci=f(xi)∏r=1,r≠im(-xr/xi-xr), one ciR, m-1 point additions in G1, and the verification e(∑i=1m‍ciR,P)=?e(R,Q). The verification costs two pairing operations (2Tpair,G1). The addition in G1 costs mTEA. The computation of ciR costs TEM, and the computation of ci costs (2(m-1)+2)Tmul,q+ Tinv,q. So totally it takes (2(m-1)+2)Tmul,q+Tinv,q+TEM+mTEA+2Tpair.Each participant in Harn’s GAS1 takesk[(2(m-2)+3)Tmul,p+Tinv,p] for computing ci, takes (m-1)Tadd,p for computing s′, and takes 1Th for verifying h(s)=?h(s′). Each participant totally takes k[(2(m-2)+3)Tmul,p+Tinv,p]+(m-1)Tadd,p+1Th.Each participant in Harn’s GAS2 takes[(2(m-2)+3)Tmul,q+Tinv,q] for computing cv, takes Texp,p for computing ev, takes (m-1)Tmul,p for computing si′, and takes 1Th for verifying h(si)=?h(si′). Each participant totally takes [(2(m-2)+3)Tmul,q+Tinv,q]+Texp,p+(m-1)Tmul,p+1Th.Table1 summarizes the performance. Row 2 lists the security properties. Only our scheme can resist an attacker from deriving the secrets when the schemes allow multiple trials. Row 3 lists the detailed computational complexity. Based on Row 3, it is still difficult to get an insight of the complexities since they involve quite different operations. We, therefore, further evaluate the computational cost under the practical setting from NSA [8] and the algebra equations of elliptic curve operations [6]. The security of ECC with 160-bit key is roughly equivalent to that of RSA with 1024-bit key or D-H algorithm with 1024-bit key. So let us assume that theq (the order of G1 and G2) in our scheme is 160 bits, andp in Harn’s schemes is 1024 bits. Under the above setting and approximations, Tmul,p (the time complexity of a field multiplication in Zp, wherep is 1024 bits) is 41 times Tmul,q (the time complexity of field multiplication in Zq, whereq is 160 bits), TEM≅29Tmul,p,TEA≅0.12Tmul,p,Texp,p≅240Tmul,p≅8TEM, and TEM≅241TEA, where ≅ means “roughly equal.”Table 1
Summaries of performance of group authentication schemes.
Ours
Harn’s GAS1
Harn’s GAS2
Securities under multiple trials for each secret
Allow multiple authentications with multiple trials
Attackers can disclose system’s secrets and users’ secret tokens
Attackers can disclose system’s secrets and users’ secret tokens
Each user’s computational cost for one group authentication (detailed)
(
2
(
m
-
1
)
+
2
)
T
m
u
l
,
q
+
T
i
n
v
,
q
+
T
E
M
+
m
T
E
A
+
2
T
p
a
i
r
k
[
(
2
(
m
-
2
)
+
3
)
T
m
u
l
,
p
+
T
i
n
v
,
p
]
+
(
m
-
1
)
T
a
d
d
,
p
+
1
T
h
2
[
(
2
(
m
-
2
)
+
3
)
T
m
u
l
,
q
+
T
i
n
v
,
q
]
+
T
e
x
p
,
p
+
(
m
-
1
)
T
m
u
l
,
p
+
1
T
h
Approximated complexities (based on the figures from [5])
(
7
m
+
1429
)
T
m
u
l
,
q
+
2
T
p
a
i
r
≅
(
7
m
+
6785
)
T
m
u
l
,
q
41
k
(
2
m
+
239
)
T
m
u
l
,
q
+
(
m
-
1
)
T
a
d
d
,
p
+
1
T
h
≅
41
k
(
2
m
+
239
)
T
m
u
l
,
q
+
(
m
-
1
)
T
a
d
d
,
p
(45m+1418)Tmul,qUsing the above setting and approximations and neglecting the minor computations like hashing and field addition, the complexities in Row 3 can be further simplified as follows. The complexity of our scheme is as follows:(2(m-1)+2)Tmul,q+Tinv,q+TEM+mTEA+2Tpair≅(2(m-1)+2)Tmul,q+Tinv,q+29Tmul,p+0.12mTmul,p + 2Tpair≅2mTmul,q+240Tmul,q+29∗41Tmul,q+0.12m∗41Tmul,p+2Tpair≅(7m+1429)Tmul,q+2Tpair. The complexity of Harn’s GAS1 is as follows: k[(2(m-2)+3)Tmul,p+Tinv,p]+(m-1)Tadd,p+1Th≅41k(2m+239)Tmul,q+(m-1)Tadd,p. The complexity of Harn’s GAS2 is as follows: 2[(2(m-2)+3)Tmul,q+Tinv,q]+Texp,p+(m-1)Tmul,p + 1Th≅2[(2(m-2)+239)Tmul,q]+240∗41Tmul,q+41(m-1)Tmul,q + 1Th≅(45m+1418)Tmul,q.To further simplify the complexity approximation, we refer to an efficient paring implementation [5]. Based on the figures there [5], we roughly approximate one pairing operation as 5356Tmul,q. We approximate (7m+1429)Tmul,q+2Tpair≅(7m+6785)Tmul,q in Row 4. From Row 4, we can tell that Harn’s schemes have lower computational cost than ours when the number of participants is small; but the costs of Harn’s schemes grow faster than ours when the number of participants increases. All the costs of the three schemes increase as the number of participants increases, but the cost of Harn’s GAS1 also depends on the valuek. Because the parameterk in Harn’s GAS1 should satisfy kt>n-1, we only compare our scheme with Harn’s GAS2 in Figure 1 to give us an insight of the performances of the three schemes. From Figure 1, we can see that the cost of Harn’s GAS2 increases much faster than ours when the number of participants increases. When the number is around 141, the cost of Harn’s GAS2 overpasses ours and increases very fast. The comparison shows that our scheme not only owns better security but also provides better computational performance when the number of participants is large.Figure 1
The comparison of computational cost versus the number of participants. The unit of the cost isTmul,q.


## 6. Conclusions

In this paper, we have shown the weaknesses of Harn’s asynchronous group authentication schemes. An attacker can derive the system secrets and the members’ secret tokens if the schemes allow multiple trials before the corresponding secret is recovered, or an attacker can easily disable the functions of the schemes by simply releasing invalid shares if the schemes do not allow multiple trials. We have proposed an improved scheme that allows multiple trials for each system secret. The analysis shows that our scheme even has better computational performance when the number of participants is greater than 141.



---

*Source: 3109624-2017-05-28.xml*