# Asynchronous Group Authentication Based on Geometric Approach

Authors: Hong Wang; Jianhua Li; Feng Zhu; Zhe Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Individual authentication in air warfare is used to check whether a single participant is a legal member of the predefined group but not determine all participants at one time. An asynchronous (m,t,n) group authentication protocol is proposed based on multidimensional sphere reconstruction theorem of space analytic geometry without making any computational assumption, wherem is the number of participants, t is threshold value, and n is the number of members. The proposed protocol can determine whether all participants belong to the predefined group at one time, which is applicable to batch verification prior to individual authentication. The center’s coordinate of (t-1)-dimensional sphere is treated as the shared secret and the coordinate of the point on the surface of the sphere, multiplied by a random blind factor, is issued to all members as their tokens. Ifm participants can reconstruct the shared secret by utilizing their tokens, indicate that there is not any invalid participant, otherwise perform individual authentication. Analyses show the proposed scheme can not only rule out the illegal outsider but also resist up to t-1 group member conspiring to forge a valid token for an outsider. In addition, compared with other schemes the proposed scheme is more applicable for air warfare network, with light-weight computation, flexible distribution, and high information rate.


---

## Body

## 1. Introduction

In these days group oriented security become more and more important in air warfare. Take aeronautical communication network for an example, it is composed of various airborne weapons within a large scope by wireless. Airborne platforms share warfare information and interact with each other by aeronautical communication network. In the case the information which includes current position, condition and task, etc., is confidential, each airborne member would rather drop out the network than its confidential information is leaked [1, 2]. Hence every airborne platform should be assured that all members in the network are valid before transmitting confidential information.Group authentication is one of the most important security services in many kinds of networks. Unlike traditional individual authentication group authentication verifies multiple signatures altogether at once and reduces verification time. Nowadays there are some proposed group authentication schemes which can authenticate all network members at one time. Concerning the basic theory group authentications fall into two categories: based on public key system and not based on public key system. In group authentication based on public key system [3–7], each member makes the individual signature by its private key and delivers its own signature to the aggregator, who is the selected one of group members. After receiving other signatures the aggregator compresses all signatures by the aggregate algorithms. The verifier can process multiple authentications at one time and make the batch verification of the security features, such as the integrity, traceability, and validity of messages. But it always includes complex computation, such as bilinear pairing and exponentiation, which need more computing efforts compared with symmetric cryptographic algorithms [8, 9]. Simultaneously there are also some group authentication schemes which are not based on public key system but some lightweight computation. For example, Harn [10] proposed a lightweight group authentication mechanism by using a preshared secret [11] in 2013. In the scheme the group manager is responsible for registering all group members. During registration the group manager uses Shamir’s secret sharing scheme to issue a private token to each group member. Subsequently all users participating in the group shall reconstruct the preshared secret. When reconstruction is successful it proves that nodes of a network must be valid and belong to a group. Otherwise there must be one or more invalid users among the participants and further authentication, such as individual authentication and batch identification, should be executed. Generally the group authentication based on secret reconstruction contains less computation overhead compared with public key based one; hence it is more suitable for airborne platform than public-key-based one when concerning fast and reliable authentication requirement in air warfare.In Harn’s scheme the notion oft-threshold,m-user andn-group was introduced and 3 schemes based on Shamir’s (t,n)-threshold secret sharing was proposed. In asynchronous (t,m,n) group authentication scheme,k polynomials was used to generatek tokens for each group member andm (m⩾t) participants are allowed to show the tokens asynchronously. Accept while the participants can reconstruct the secret, reject otherwise. The amount of participants must be known as a prior in order to reconstruct the secret, but in air warfare the amount is difficult to be known precisely and even not fixed. It requirek polynomials andk is restricted by kt>n-1. So it is not efficient and flexible enough. Based on the Lagrange interpolation theory Li et al. [14] proposed group authentication in 2016, and there also exists the same problem as Harn’s scheme. Miao et al. [12] developed the group authentication based on Chinese Residue Theorem, but it is one-time authentication since the secret is no longer a secret once it has been recovered. Ji et al. [15] suggested another asynchronous (t,m,n) group authentication scheme based on threshold secret sharing theory in 2016. Before authentication it is assumed that every member has a predistributed randomized component (RC for short) which ensures that all the member’s tokens are correlative, but a new token could not be deduced by coalition attacks. Nevertheless it is hard to meet that the amount of participants is a prerequisite knowledge for group authentication. He et al. [13] improved Ji’s scheme and proposed another (t,m,n) group authentication scheme in which invalid members could be identified if group authentication fails. In He’s scheme one trusted center; i.e., authentication server which is responsible for identification of bad member is needed. But it is hard to deploy a fixed and trusted center in air warfare.Considering the characteristics of air warfare we give the asynchronous group authentication scheme which is applicable to the decentralized and asynchronous communication environment based on secret sharing theory. Meanwhile networking frequently in air warfare requires that the secret can be reused in our scheme. The remainder of this paper is organized as follows. In Section2, we introduce the system model, authentication procedure and hypothesis of this scheme. In Section 3 we propose our asynchronous group authentication scheme based on geometric approach, followed by its security proof and performance analysis in Sections 4 and 5, respectively. In the end we draw our conclusion in Section 6.


## 2. Model and Hypothesis

In this section we formalize the system model and identify authentication procedure.


### 2.1. System Model

#### 2.1.1. Entities

In terms of group authentication there are 4 types of entities in proposed scheme, the group manager (GM for short), group members, cluster header and some adversaries, as shown in Figure1.Figure 1
The class diagram of entities in the communication network.(a)GM: It is the coordinator of the scheme, which is trusted by all group members and responsible for the setup and distributing a secret share to each member by predeployed secure channel. Generally ground-based command site plays the role of GM and is assumed that it is not easy to be assaulted.(b)Group members: All of the members possess the valid token. Group members belong to a predefined group and obtain the subsecret from GM in advance. The token which derives from the subsecret is deemed as the certificate of group member.(c)Cluster Header: It is one of the group members who verify the tokens.(d)Adversaries: There are 2 types of adversaries described as follows, including Insiders and Outsiders.


#### 2.1.2. Adversary Model

In complicated air electromagnetic environment the network participants could be the members who have a valid token, or others who have no valid token. So there are 2 types of adversaries.(a)Insiders: An insider is a legal member who obtains a valid token from GM but may band with other participants to forge a valid token for an illegal participant. It is assumed that there exist at mostt-2 insiders in our scheme.(b)Outsiders: An outsider does not belong to the predefined group and does not have a valid token. During networking authentication an outsider may eavesdrop information exchanged within group members, likely derive a valid token, and pretend to be a legal group member.


### 2.2. Authentication Procedure

Group authentication consists of three steps, i.e. setup, the generation of token and batch verification.(a)Setup: GM generates some system parameters, selects a proper secret value S, and makes the shadow of S such as the hash value of S, publicly known.(b)Generation of tokens: GM computes the subsecret and token for each group member, denoted asU={U1,U2,⋯,Un}, and distributes them to each group member securely.(c)Batch verification: all participants show their tokens, then reconstruct a secretS′ and compare the hash value of S′ with the one of S, and thus verify whether all participants are legal simultaneously.


## 2.1. System Model

### 2.1.1. Entities

In terms of group authentication there are 4 types of entities in proposed scheme, the group manager (GM for short), group members, cluster header and some adversaries, as shown in Figure1.Figure 1
The class diagram of entities in the communication network.(a)GM: It is the coordinator of the scheme, which is trusted by all group members and responsible for the setup and distributing a secret share to each member by predeployed secure channel. Generally ground-based command site plays the role of GM and is assumed that it is not easy to be assaulted.(b)Group members: All of the members possess the valid token. Group members belong to a predefined group and obtain the subsecret from GM in advance. The token which derives from the subsecret is deemed as the certificate of group member.(c)Cluster Header: It is one of the group members who verify the tokens.(d)Adversaries: There are 2 types of adversaries described as follows, including Insiders and Outsiders.


### 2.1.2. Adversary Model

In complicated air electromagnetic environment the network participants could be the members who have a valid token, or others who have no valid token. So there are 2 types of adversaries.(a)Insiders: An insider is a legal member who obtains a valid token from GM but may band with other participants to forge a valid token for an illegal participant. It is assumed that there exist at mostt-2 insiders in our scheme.(b)Outsiders: An outsider does not belong to the predefined group and does not have a valid token. During networking authentication an outsider may eavesdrop information exchanged within group members, likely derive a valid token, and pretend to be a legal group member.


## 2.1.1. Entities

In terms of group authentication there are 4 types of entities in proposed scheme, the group manager (GM for short), group members, cluster header and some adversaries, as shown in Figure1.Figure 1
The class diagram of entities in the communication network.(a)GM: It is the coordinator of the scheme, which is trusted by all group members and responsible for the setup and distributing a secret share to each member by predeployed secure channel. Generally ground-based command site plays the role of GM and is assumed that it is not easy to be assaulted.(b)Group members: All of the members possess the valid token. Group members belong to a predefined group and obtain the subsecret from GM in advance. The token which derives from the subsecret is deemed as the certificate of group member.(c)Cluster Header: It is one of the group members who verify the tokens.(d)Adversaries: There are 2 types of adversaries described as follows, including Insiders and Outsiders.


## 2.1.2. Adversary Model

In complicated air electromagnetic environment the network participants could be the members who have a valid token, or others who have no valid token. So there are 2 types of adversaries.(a)Insiders: An insider is a legal member who obtains a valid token from GM but may band with other participants to forge a valid token for an illegal participant. It is assumed that there exist at mostt-2 insiders in our scheme.(b)Outsiders: An outsider does not belong to the predefined group and does not have a valid token. During networking authentication an outsider may eavesdrop information exchanged within group members, likely derive a valid token, and pretend to be a legal group member.


## 2.2. Authentication Procedure

Group authentication consists of three steps, i.e. setup, the generation of token and batch verification.(a)Setup: GM generates some system parameters, selects a proper secret value S, and makes the shadow of S such as the hash value of S, publicly known.(b)Generation of tokens: GM computes the subsecret and token for each group member, denoted asU={U1,U2,⋯,Un}, and distributes them to each group member securely.(c)Batch verification: all participants show their tokens, then reconstruct a secretS′ and compare the hash value of S′ with the one of S, and thus verify whether all participants are legal simultaneously.


## 3. Our Scheme Based on Geometric Approach

We propose a group authentication scheme based on the threshold secret sharing theory. Geometric theory brings inspiration and productivity to the secret sharing scheme. Blakley [16] proposed a threshold secret sharing scheme based on projective geometry theory early in 1979. Later, some literatures suggest the similar schemes based on analytical geometric theory sequentially. Our proposed scheme is based on multidimensional sphere reconstruction theory. Next we reveal and examine the theorem that four points determinate a sphere and give our group authentication scheme, followed by analysis of correctness.


### 3.1. Multi-Dimensional Sphere Reconstruction Theory

Every three triangle vertexes can determine a circle in a plane. And the center of the circle is the outside center of the triangle. Namely, every three points that do not lie on a straight line can determine a circle in a plane. Let(x1,y1),(x2,y2) and (x3,y3) be the coordinators of three triangle vertexes. Suppose that the equation of circle is (1)x-a2+y-b2=r2Now let us substitute its coordinates into (1) and then get (2)x1-a2+y1-b2=x2-a2+y2-b2=x3-a2+y3-b2Simplify (2) further to (3)A1a+B1b=C1A2a+B2b=C2where A1=2(x2-x1), B1=2(y2-y1), C1=x22+y22-x12-y12, A2=2(x3-x2), B2=2(y3-y2), C2=x32+y32-x22-y22, and thus (4)a=C1B1C2B2A1B1A2B2,b=A1C1A2C2A1B1A2B2Choose a point(a,b) of the plane and a random numberr as the center and the radius of the circle respectively. The point (a,b) of the plane is considered as the secret to be shared. Selectn points of the circle arbitrarily and distribute the coordinates of n points ton users as the subsecrets of them, respectively. Therefore, it is a (3,n) threshold secret sharing scheme; at least 3 users show the subsecrets synchronously and reconstruct the circle and the secret (a,b) is recovered.When the reconstruction theory of three-dimensional circle is extended to(t-1)-dimensional space, t arbitrary points that do not lie on the same (t-2)-dimensional space could determine the sphere of (t-1)-dimensional space. The equation of the sphere is denoted as(5)∑i=1t-1xi-ai2=R,R>0or∑i=1t-1xi2-2a1x1-⋯-2at-1xt-1+d=0where d=∑i=1t-1ai2-R.Similarly, the center(a1,a2,⋯,at-1) of sphere is deemed as the secret to be shared. Selectn points of the circle arbitrarily and distribute the coordinates of n points ton users as the subsecrets of them, respectively. Therefore, it is a (t,n) threshold secret sharing scheme; at leastt users show the subsecrets synchronously and reconstruct the circle, and the secret (a1,a2,⋯,at-1) is recovered.Theorem 1 (see [17]).
Ift points A1(y11,y12,⋯,y1(t-1)), A2(y21,y22,⋯,y2(t-1)) … At(yt1,yt2,⋯,yt(t-1)) do not lie in the common (t-2)-dimensional space, then they can uniquely determine a sphere, described as (5), in (t-1)-dimensional space uniquely, where (6)ai=Di2D,i=1,2,⋯,t-1(7)R=DtD+∑i=1t-1ai2(8)D=y11⋯y1i-1y1iy1i+1⋯y1t-11y21⋯y2i-1y2iy2i+1⋯y2t-11⋮⋯⋮⋮⋮⋱⋮⋮yt1⋯yti-1ytiyti+1⋯ytt-11≠0(9)Di=y11⋯y1i-1∑i=1t-1y1i2y1i+1⋯y1t-11y21⋯y2i-1∑i=1t-1y2i2y2i+1⋯y2t-11⋮⋯⋮⋮⋮⋱⋮⋮yt1⋯yti-1∑i=1t-1yti2yti+1⋯ytt-11Theorem 2 (see [18]).
If there is an odd primep, such that p=3(mod⁡4), any integer z∈[0,p) could be expressed as a modulo sum of square ofk integers; i.e., while z and p are known, there is a solution for z=w12+w22+⋯+wk2(mod⁡p).


### 3.2. Asynchronous Group Authentication

The asynchronous group authentication contains three steps: setup, generation of tokens and batch verification, as shown in Figure2.Figure 2
The detailed process diagram of asynchronous group authentication.(1)Setup. GM chooses an odd prime p=3(mod⁡4), secret vertex S={s1,s2⋯st-1}, and c∈R(0,p). Compute(10)a1=s1+cmod⁡pa2=s2+cmod⁡p⋯at-2=st-2+cmod⁡pat-1=cmod⁡pR=st-1+cmod⁡pLetΩ:∑j=1t-1(xj-aj)2=R(modp) be the equation of sphere in (t-1)-dimensional space.(2)Generation of Tokens. (i)GM runs the algorithm described in Table 1 and generates Bi=(xi1,xi2,⋯,xi(t-1)), where i=1,2⋯n, for each user U={U1,U2,⋯,Un}.Table 1
Choose an arbitrary point in a sphereΩ.
Input:Ω:∑j=1t-1(xj-aj)2=R; Output: (t-1)-dimensional points Bi=(xi1,xi2,⋯,xi(t-1)) in Ω ( 1 ) Choose xi1,xi2,……xi(t-3) in (0,p) randomly; ( 2 ) Compute di1=xi1-a1(modp), di2=xi2-a2(modp)……di(t-3)=xi(t-3)-at-3(modp); ( 3 ) Compute eij=dij2(modp), j=1,2,⋯,t-3; ( 4 ) Choose di(t-2)∈(0,p), then compute ei(t-2)=di(t-2)2(modp); ( 5 ) Compute ei(t-1)′=R-∑j=1t-2eij(modp), di(t-1)=(ei(t-1)′)p+1/4(modp); ( 6 ) Compute ei(t-1)=di(t-1)2(modp); ( 7 ) If et-2+et-1≠R-∑j=1t-3ej(modp), then return 4; ( 8 )   x i ( t - 2 ) = d i ( t - 2 ) + a t - 2 ( m o d p ), xi(t-1)=di(t-1)+at-1(modp) ( 9 ) Output Bi=(xi1,xi2,⋯,xi(t-1))(ii)Choose a random integerr∈R(0,p),(r,p)=1, and then compute (11)Bi′=xi1′,xi2′,⋯,xit-1′modp=rxi1,rxi2,⋯,rxit-1modp,i=1,2⋯n.B i ′ is regarded as token and distributed to Ui, i=1,2⋯n.(3)Batch Verification. While m(t<m<n) participants UIm={Ui1,Ui2,⋯,Uim} show tokens Bij′, j=1,2⋯m, each participant collects all the tokens and computes (12)Ddec=∑j=1t-1xi1j′2xi11′xi12′⋯xi1t-1′1∑j=1t-1xi2j′2xi21′xi22′⋯xi2t-1′1⋮⋮⋮⋱⋮⋮∑j=1t-1xitj′2xit1′xit2′⋯xitt-1′1∑j=1t-1zj2z1z2⋯zt-11where(z1,z2,⋯,zt-1) is substituted by Bij′, j=t+1,t+2,⋯,m. If all Ddec=0 is true for j=t+1,t+2⋯m, then all participants are legal; otherwise there is at least one illegal participant, identifying the illegal participants is next to do.


### 3.3. Analysis of Correctness

Lemma Linear equations(13)a11x1+a12x2+⋯+a1,n-1xn-1+a1,n=0a21x1+a22x2+⋯+a2,n-1xn-1+a2,n=0⋯an1x1+an2x2+⋯+an,n-1xn-1+an,n=0have a solution if and only if(14)a11a12⋯a1na21a22⋯a2n⋯⋯⋯⋯an1an2⋯ann=0Proof.
If the system of linear equations (13) has a solution, thus the rank of its coefficient matrix C equals the one of augmented matrix A, where(15)C=a11a12⋯a1,n-1a21a22⋯a2,n-1⋯⋯⋯⋯an1an2⋯an,n-1,A=a11a12⋯a1,n-1a1na21a22⋯a2,n-1a2n⋯⋯⋯⋯⋯an1an2⋯an,n-1ann,
i.e., Rank(C)=Rank(A).
Since Rank(A)≤n-1, Rank(C) ≤n-1. So A=0, (14) is true.
Moreover, if (14) is true, i.e., column vectors are linear dependent, (a1n,a2n,⋯,ann)T could be expressed as linear combination of (a11,a21,⋯,an1)T…(a1,n-1,a2,n-1,⋯,an,n-1)T; i.e., (13) have a solution.Theorem 3.
Ift vector Bi=(xi1,xi2,⋯,xi(t-1))(modp), (i=1,2,⋯,t), is linear independent in (t-1)-dimensional space, then the equation of sphere that thet vectors determine is (16)∑j=1t-1x1j2x11x12⋯x1t-11∑j=1t-1x2j2x21x22⋯x2t-11⋮⋮⋮⋱⋮⋮∑j=1t-1xtj2xt1xt2⋯xtt-11∑j=1t-1zj2z1z2⋯zt-11=0Proof.
Suppose that (5) is the sphere equation to be determined. Since Bi=(xi1,xi2,⋯,xi(t-1))(modp), (i=1,2,⋯,t), lie on the sphere, then Ai:∑k=1t-1xik2-2a1xi1-⋯-2at-1xi,t-1+d=0, j=1,2,⋯,t. After variable substitution (5) is transformed into ∑i=1t-1zi2-2a1z1-⋯-2at-1zt-1+d=0. While a1⋯at-1 and d are regarded as the unknown variables, thus (17)∑k=1t-1x1k2-2a1x11-⋯-2at-1x1,t-1+d=0∑k=1t-1x2k2-2a1x21-⋯-2at-1x2,t-1+d=0⋯∑k=1t-1xt-1,k2-2a1xt-1,1-⋯-2at-1xt-1,t-1+d=0∑i=1t-1zi2-2a1z1-⋯-2at-1zt-1+d=0
Equations (17) have a solution if and only if the determinant (16) is true by referring to Lemma, so the equation of the sphere that Bi=(xi1,xi2,⋯,xi(t-1))(modp), (i=1,2,⋯,t), lie on is (16).
According to the characteristics of determinant (16) takes on the following form: (18)∑j=1t-1rx1j2rx11rx12⋯rx1t-11∑j=1t-1rx2j2rx21rx22⋯rx2t-11⋮⋮⋮⋱⋮⋮∑j=1t-1rxtj2rxt1rxt2⋯rxtt-11∑j=1t-1rzj2rz1rz2⋯rzt-11=0
Namely,(19)∑j=1t-1x1j′2x11′x12′⋯x1,t-1′1∑j=1t-1x2j′2x21′x22′⋯x2,t-1′1⋮⋮⋮⋱⋮⋮∑j=1t-1xtj′2xt1′xt2′⋯xt,t-1′1∑j=1t-1rzj2rz1rz2⋯rzt-11=0
WhenBi′=(xi1′,xi2′,⋯,xi(t-1)′)(modp)=(rxi1,rxi2,⋯,rxi(t-1))(modp), i=1,2⋯n, lie on the sphere Ω, (17) is true.


## 3.1. Multi-Dimensional Sphere Reconstruction Theory

Every three triangle vertexes can determine a circle in a plane. And the center of the circle is the outside center of the triangle. Namely, every three points that do not lie on a straight line can determine a circle in a plane. Let(x1,y1),(x2,y2) and (x3,y3) be the coordinators of three triangle vertexes. Suppose that the equation of circle is (1)x-a2+y-b2=r2Now let us substitute its coordinates into (1) and then get (2)x1-a2+y1-b2=x2-a2+y2-b2=x3-a2+y3-b2Simplify (2) further to (3)A1a+B1b=C1A2a+B2b=C2where A1=2(x2-x1), B1=2(y2-y1), C1=x22+y22-x12-y12, A2=2(x3-x2), B2=2(y3-y2), C2=x32+y32-x22-y22, and thus (4)a=C1B1C2B2A1B1A2B2,b=A1C1A2C2A1B1A2B2Choose a point(a,b) of the plane and a random numberr as the center and the radius of the circle respectively. The point (a,b) of the plane is considered as the secret to be shared. Selectn points of the circle arbitrarily and distribute the coordinates of n points ton users as the subsecrets of them, respectively. Therefore, it is a (3,n) threshold secret sharing scheme; at least 3 users show the subsecrets synchronously and reconstruct the circle and the secret (a,b) is recovered.When the reconstruction theory of three-dimensional circle is extended to(t-1)-dimensional space, t arbitrary points that do not lie on the same (t-2)-dimensional space could determine the sphere of (t-1)-dimensional space. The equation of the sphere is denoted as(5)∑i=1t-1xi-ai2=R,R>0or∑i=1t-1xi2-2a1x1-⋯-2at-1xt-1+d=0where d=∑i=1t-1ai2-R.Similarly, the center(a1,a2,⋯,at-1) of sphere is deemed as the secret to be shared. Selectn points of the circle arbitrarily and distribute the coordinates of n points ton users as the subsecrets of them, respectively. Therefore, it is a (t,n) threshold secret sharing scheme; at leastt users show the subsecrets synchronously and reconstruct the circle, and the secret (a1,a2,⋯,at-1) is recovered.Theorem 1 (see [17]).
Ift points A1(y11,y12,⋯,y1(t-1)), A2(y21,y22,⋯,y2(t-1)) … At(yt1,yt2,⋯,yt(t-1)) do not lie in the common (t-2)-dimensional space, then they can uniquely determine a sphere, described as (5), in (t-1)-dimensional space uniquely, where (6)ai=Di2D,i=1,2,⋯,t-1(7)R=DtD+∑i=1t-1ai2(8)D=y11⋯y1i-1y1iy1i+1⋯y1t-11y21⋯y2i-1y2iy2i+1⋯y2t-11⋮⋯⋮⋮⋮⋱⋮⋮yt1⋯yti-1ytiyti+1⋯ytt-11≠0(9)Di=y11⋯y1i-1∑i=1t-1y1i2y1i+1⋯y1t-11y21⋯y2i-1∑i=1t-1y2i2y2i+1⋯y2t-11⋮⋯⋮⋮⋮⋱⋮⋮yt1⋯yti-1∑i=1t-1yti2yti+1⋯ytt-11Theorem 2 (see [18]).
If there is an odd primep, such that p=3(mod⁡4), any integer z∈[0,p) could be expressed as a modulo sum of square ofk integers; i.e., while z and p are known, there is a solution for z=w12+w22+⋯+wk2(mod⁡p).


## 3.2. Asynchronous Group Authentication

The asynchronous group authentication contains three steps: setup, generation of tokens and batch verification, as shown in Figure2.Figure 2
The detailed process diagram of asynchronous group authentication.(1)Setup. GM chooses an odd prime p=3(mod⁡4), secret vertex S={s1,s2⋯st-1}, and c∈R(0,p). Compute(10)a1=s1+cmod⁡pa2=s2+cmod⁡p⋯at-2=st-2+cmod⁡pat-1=cmod⁡pR=st-1+cmod⁡pLetΩ:∑j=1t-1(xj-aj)2=R(modp) be the equation of sphere in (t-1)-dimensional space.(2)Generation of Tokens. (i)GM runs the algorithm described in Table 1 and generates Bi=(xi1,xi2,⋯,xi(t-1)), where i=1,2⋯n, for each user U={U1,U2,⋯,Un}.Table 1
Choose an arbitrary point in a sphereΩ.
Input:Ω:∑j=1t-1(xj-aj)2=R; Output: (t-1)-dimensional points Bi=(xi1,xi2,⋯,xi(t-1)) in Ω ( 1 ) Choose xi1,xi2,……xi(t-3) in (0,p) randomly; ( 2 ) Compute di1=xi1-a1(modp), di2=xi2-a2(modp)……di(t-3)=xi(t-3)-at-3(modp); ( 3 ) Compute eij=dij2(modp), j=1,2,⋯,t-3; ( 4 ) Choose di(t-2)∈(0,p), then compute ei(t-2)=di(t-2)2(modp); ( 5 ) Compute ei(t-1)′=R-∑j=1t-2eij(modp), di(t-1)=(ei(t-1)′)p+1/4(modp); ( 6 ) Compute ei(t-1)=di(t-1)2(modp); ( 7 ) If et-2+et-1≠R-∑j=1t-3ej(modp), then return 4; ( 8 )   x i ( t - 2 ) = d i ( t - 2 ) + a t - 2 ( m o d p ), xi(t-1)=di(t-1)+at-1(modp) ( 9 ) Output Bi=(xi1,xi2,⋯,xi(t-1))(ii)Choose a random integerr∈R(0,p),(r,p)=1, and then compute (11)Bi′=xi1′,xi2′,⋯,xit-1′modp=rxi1,rxi2,⋯,rxit-1modp,i=1,2⋯n.B i ′ is regarded as token and distributed to Ui, i=1,2⋯n.(3)Batch Verification. While m(t<m<n) participants UIm={Ui1,Ui2,⋯,Uim} show tokens Bij′, j=1,2⋯m, each participant collects all the tokens and computes (12)Ddec=∑j=1t-1xi1j′2xi11′xi12′⋯xi1t-1′1∑j=1t-1xi2j′2xi21′xi22′⋯xi2t-1′1⋮⋮⋮⋱⋮⋮∑j=1t-1xitj′2xit1′xit2′⋯xitt-1′1∑j=1t-1zj2z1z2⋯zt-11where(z1,z2,⋯,zt-1) is substituted by Bij′, j=t+1,t+2,⋯,m. If all Ddec=0 is true for j=t+1,t+2⋯m, then all participants are legal; otherwise there is at least one illegal participant, identifying the illegal participants is next to do.


## 3.3. Analysis of Correctness

Lemma Linear equations(13)a11x1+a12x2+⋯+a1,n-1xn-1+a1,n=0a21x1+a22x2+⋯+a2,n-1xn-1+a2,n=0⋯an1x1+an2x2+⋯+an,n-1xn-1+an,n=0have a solution if and only if(14)a11a12⋯a1na21a22⋯a2n⋯⋯⋯⋯an1an2⋯ann=0Proof.
If the system of linear equations (13) has a solution, thus the rank of its coefficient matrix C equals the one of augmented matrix A, where(15)C=a11a12⋯a1,n-1a21a22⋯a2,n-1⋯⋯⋯⋯an1an2⋯an,n-1,A=a11a12⋯a1,n-1a1na21a22⋯a2,n-1a2n⋯⋯⋯⋯⋯an1an2⋯an,n-1ann,
i.e., Rank(C)=Rank(A).
Since Rank(A)≤n-1, Rank(C) ≤n-1. So A=0, (14) is true.
Moreover, if (14) is true, i.e., column vectors are linear dependent, (a1n,a2n,⋯,ann)T could be expressed as linear combination of (a11,a21,⋯,an1)T…(a1,n-1,a2,n-1,⋯,an,n-1)T; i.e., (13) have a solution.Theorem 3.
Ift vector Bi=(xi1,xi2,⋯,xi(t-1))(modp), (i=1,2,⋯,t), is linear independent in (t-1)-dimensional space, then the equation of sphere that thet vectors determine is (16)∑j=1t-1x1j2x11x12⋯x1t-11∑j=1t-1x2j2x21x22⋯x2t-11⋮⋮⋮⋱⋮⋮∑j=1t-1xtj2xt1xt2⋯xtt-11∑j=1t-1zj2z1z2⋯zt-11=0Proof.
Suppose that (5) is the sphere equation to be determined. Since Bi=(xi1,xi2,⋯,xi(t-1))(modp), (i=1,2,⋯,t), lie on the sphere, then Ai:∑k=1t-1xik2-2a1xi1-⋯-2at-1xi,t-1+d=0, j=1,2,⋯,t. After variable substitution (5) is transformed into ∑i=1t-1zi2-2a1z1-⋯-2at-1zt-1+d=0. While a1⋯at-1 and d are regarded as the unknown variables, thus (17)∑k=1t-1x1k2-2a1x11-⋯-2at-1x1,t-1+d=0∑k=1t-1x2k2-2a1x21-⋯-2at-1x2,t-1+d=0⋯∑k=1t-1xt-1,k2-2a1xt-1,1-⋯-2at-1xt-1,t-1+d=0∑i=1t-1zi2-2a1z1-⋯-2at-1zt-1+d=0
Equations (17) have a solution if and only if the determinant (16) is true by referring to Lemma, so the equation of the sphere that Bi=(xi1,xi2,⋯,xi(t-1))(modp), (i=1,2,⋯,t), lie on is (16).
According to the characteristics of determinant (16) takes on the following form: (18)∑j=1t-1rx1j2rx11rx12⋯rx1t-11∑j=1t-1rx2j2rx21rx22⋯rx2t-11⋮⋮⋮⋱⋮⋮∑j=1t-1rxtj2rxt1rxt2⋯rxtt-11∑j=1t-1rzj2rz1rz2⋯rzt-11=0
Namely,(19)∑j=1t-1x1j′2x11′x12′⋯x1,t-1′1∑j=1t-1x2j′2x21′x22′⋯x2,t-1′1⋮⋮⋮⋱⋮⋮∑j=1t-1xtj′2xt1′xt2′⋯xt,t-1′1∑j=1t-1rzj2rz1rz2⋯rzt-11=0
WhenBi′=(xi1′,xi2′,⋯,xi(t-1)′)(modp)=(rxi1,rxi2,⋯,rxi(t-1))(modp), i=1,2⋯n, lie on the sphere Ω, (17) is true.


## 4. Security Analyses

As mentioned previously, there exist two attacks against group authentication. One is from Insider, the other is from Outsider. In our scheme some Insiders attempt to reconstruct the predefined secret successfully by using their own tokens, thus they may generate a new token for an invalid member. However, it is impossible for some Insiders to derive the secret from their own tokens according to sphere reconstruction theory, and so the scheme is secure even if some legal members are compromised; see the following Theorem4 for details. On the other hand, an Outsider may intercept a valid token by eavesdropping on the private channel successfully. It is also impossible for an Outsider to replay the used token since blind factor is changed frequently, for details see Theorem 5.


### 4.1. Coalition Attack Resistance

Assume that less thant-1 legal members may attack the scheme together as previous hypothesis. But there exist t-2 members who are likely to attack jointly and try to reconstruct the shared secret. It is out of the question to reconstruct a predefined sphere in t-1 dimensional space by using t-2 points on the sphere, so the coalition attack is ineffective by t-2 members correspondingly.Theorem 4.
Less thant-1 legal members cannot get the secret S={s1,s2⋯st-1}, i.e., the center’s coordinate of t-1 dimensional sphere.Proof.
Lett-2 participants’ tokens be Bi′=rBi=(rxi1,rxi2,⋯,rxi(t-1))=(xi1′,xi2′,⋯,xi(t-1)′)(modp), where i=1,2⋯t-2, Bi=(xi1,xi2,⋯,xi(t-1)),r is a random number which plays the role of blinding Bi. The attacker could not derive Bi from Bi′ unless the large integer factorization problem is feasible to be solved. Additionally t-2 vectors are insufficient to determine the (t-1)-dimensional sphere. The proof is by contradiction. Suppose it is true that t-2 vectors are enough to determine the (t-1)-dimensional sphere. Without lose of generality, let the vectors be denoted as B1,B2⋯Bt-2 determining a sphere Ω1. Besides pick other two points W and V which are not on the sphere Ω1. Due to Theorem 1, by B1,B2⋯Bt-2, W and V, another sphere, called as Ω2, is determined. Clearly Ω1≠Ω2, since W∉Ω1 and V∉Ω1, but W∈Ω2 and V∈Ω2. Consequently by B1,B2⋯Bt-2 two different spheres are determined. If it did, it would be in contradiction with the above supposition of B1,B2⋯Bt-2 uniquely determining a sphere of (t-1)-dimension. Therefore the sphere is not recovered by less than t-1 legal members, nor is the secret correspondingly.


### 4.2. Replay Attack Resistance

After legal participants showing the invalid tokens asynchronously, the Outsider may acquire the token which is to be reused illegally next. In our scheme blind factor concealing the token is beneficial to resist against the replay attack.Theorem 5.
An Outsider cannot pass the group authentication by reusing the other token.Proof.
Assume thatUi1′’s token is leaked of the participants, UIm′={Ui1′,Ui2′,⋯,Uim′} (t<m<n). Ui1′’s token is denoted as Bi1′=(xi11′,xi12′,⋯,xi1(t-1)′)(modp)=(rxi11,rxi12,⋯,rxi1(t-1))(modp) which is to be replayed. But GM has updated all online tokens before next group authentication, so all tokens become Bij′′=(xij1′′,xij2′′,⋯,xijt-1′′)(modp)=(r′xij1,r′xij2,⋯,r′xij(t-1))(modp), j=1,2⋯n. The replay attacker fakes Ui1′ by reusing Bi1′ in a new authentication protocol. After substituting these values into determinant (16), we get(20)∑j=1t-1x1j′2x11′x12′⋯x1,t-1′1∑j=1t-1x2j′′2x21′′x22′′⋯x2,t-1′′1⋮⋮⋮⋱⋮⋮∑j=1t-1xtj′′2xt1′′xt2′′⋯xt,t-1′′1∑j=1t-1xt+1,j′′2xt+1,1′′xt+1,2′′⋯xt+1,t-1′′1=∑j=1t-1rx1j2rx11rx12⋯rx1,t-11∑j=1t-1r′x2j2r′x21r′x22⋯r′x2,t-11⋮⋮⋮⋱⋮⋮∑j=1t-1r′xtj2r′xt1r′xt2⋯r′xt,t-11∑j=1t-1r′xt+1,j2r′xt+1,1r′xt+1,2⋯r′xt+1,t-11
There is any common factor in each row and column of determinant (20), so equation (16) is different from equation (20). The probability that r=r′ is 1/(p-1), where p is an odd prime, while p→∞, 1/(p-1)→0. Consequently the probability that the reused token passes the new authentication is negligible.


## 4.1. Coalition Attack Resistance

Assume that less thant-1 legal members may attack the scheme together as previous hypothesis. But there exist t-2 members who are likely to attack jointly and try to reconstruct the shared secret. It is out of the question to reconstruct a predefined sphere in t-1 dimensional space by using t-2 points on the sphere, so the coalition attack is ineffective by t-2 members correspondingly.Theorem 4.
Less thant-1 legal members cannot get the secret S={s1,s2⋯st-1}, i.e., the center’s coordinate of t-1 dimensional sphere.Proof.
Lett-2 participants’ tokens be Bi′=rBi=(rxi1,rxi2,⋯,rxi(t-1))=(xi1′,xi2′,⋯,xi(t-1)′)(modp), where i=1,2⋯t-2, Bi=(xi1,xi2,⋯,xi(t-1)),r is a random number which plays the role of blinding Bi. The attacker could not derive Bi from Bi′ unless the large integer factorization problem is feasible to be solved. Additionally t-2 vectors are insufficient to determine the (t-1)-dimensional sphere. The proof is by contradiction. Suppose it is true that t-2 vectors are enough to determine the (t-1)-dimensional sphere. Without lose of generality, let the vectors be denoted as B1,B2⋯Bt-2 determining a sphere Ω1. Besides pick other two points W and V which are not on the sphere Ω1. Due to Theorem 1, by B1,B2⋯Bt-2, W and V, another sphere, called as Ω2, is determined. Clearly Ω1≠Ω2, since W∉Ω1 and V∉Ω1, but W∈Ω2 and V∈Ω2. Consequently by B1,B2⋯Bt-2 two different spheres are determined. If it did, it would be in contradiction with the above supposition of B1,B2⋯Bt-2 uniquely determining a sphere of (t-1)-dimension. Therefore the sphere is not recovered by less than t-1 legal members, nor is the secret correspondingly.


## 4.2. Replay Attack Resistance

After legal participants showing the invalid tokens asynchronously, the Outsider may acquire the token which is to be reused illegally next. In our scheme blind factor concealing the token is beneficial to resist against the replay attack.Theorem 5.
An Outsider cannot pass the group authentication by reusing the other token.Proof.
Assume thatUi1′’s token is leaked of the participants, UIm′={Ui1′,Ui2′,⋯,Uim′} (t<m<n). Ui1′’s token is denoted as Bi1′=(xi11′,xi12′,⋯,xi1(t-1)′)(modp)=(rxi11,rxi12,⋯,rxi1(t-1))(modp) which is to be replayed. But GM has updated all online tokens before next group authentication, so all tokens become Bij′′=(xij1′′,xij2′′,⋯,xijt-1′′)(modp)=(r′xij1,r′xij2,⋯,r′xij(t-1))(modp), j=1,2⋯n. The replay attacker fakes Ui1′ by reusing Bi1′ in a new authentication protocol. After substituting these values into determinant (16), we get(20)∑j=1t-1x1j′2x11′x12′⋯x1,t-1′1∑j=1t-1x2j′′2x21′′x22′′⋯x2,t-1′′1⋮⋮⋮⋱⋮⋮∑j=1t-1xtj′′2xt1′′xt2′′⋯xt,t-1′′1∑j=1t-1xt+1,j′′2xt+1,1′′xt+1,2′′⋯xt+1,t-1′′1=∑j=1t-1rx1j2rx11rx12⋯rx1,t-11∑j=1t-1r′x2j2r′x21r′x22⋯r′x2,t-11⋮⋮⋮⋱⋮⋮∑j=1t-1r′xtj2r′xt1r′xt2⋯r′xt,t-11∑j=1t-1r′xt+1,j2r′xt+1,1r′xt+1,2⋯r′xt+1,t-11
There is any common factor in each row and column of determinant (20), so equation (16) is different from equation (20). The probability that r=r′ is 1/(p-1), where p is an odd prime, while p→∞, 1/(p-1)→0. Consequently the probability that the reused token passes the new authentication is negligible.


## 5. Performance Comparison and Analysis

The network environment in air warfare is complicated. Besides security requirement, efficiency is necessary for any group oriented authentication. The air tactical network has their inherent characteristics, such as high speed of aircrafts, poor stability of network topology, unpredictable discontinuity of communication link etc., which pose challenges for authentication. Considering these requirements our scheme has four contributions. Firstly our scheme can determine if there is any invalid participant in network by computing determinant (12) once, whose complexity is O(1). Secondly all participants are allowed to show their tokens asynchronously since blind factor hides the token. Thirdly GM serves for system setup and secret issuing, not online server. Any participant may act as the verifier since the network is deployed by distributed mode. Fourthly in the proposed scheme tokens generated by the GM initially can be used only to determine whether all participants are legal members, not to recover the secret. So the same secret can be employed for multiple authentications. In addition, any open token will not compromise the secrecy of uncovered secrets. Besides feasible practicability the proposed scheme provides some gains in efficiency, as batch verification of multiple participants is significantly faster than individual authentication, i.e.,“one-by-one” verification. The following is for details comparing with other authentication schemes.


### 5.1. Comparison with Individual Authentication

Individual authentication means that every two participants verify each other and any participant need verify other participants. Assume that 5 communications is necessary in each individual authentication, and it costs5(m-1)! communications form participants to finish individual authentications mutually. However, it costs only 2m communications form participants to finish group authentication. One is for showing the token and the other is for issuing the decision. In terms of computation overhead our proposed group authentication scheme outperforms previously individual authentication. Individual authentication demands any participant to verify each of other participants, so the complexity is O(m), but our proposed group authentication scheme demands only one batch verification so as to determine whether there is any invalid participant. The complexity is O(1).


### 5.2. Comparison with Other Group Authentication

Our scheme is based on multidimensional sphere reconstruction theory instead of any mathematical hard problem. The computation overhead in our scheme is more lightweight, which contains neither bilinear pairing computation nor exponentiation, comparing with batch verification based on public key algorithm. Obviously our scheme mainly includes the calculation of high-order determinants which is associated with the number of participants. Concerning the efficiency of calculation Wiedemann [19] gave a probabilistic method whose complexity is O((t+1)(w+t+1log⁡(t+1))) for the calculation of t-1 order determinant, where w represents the total of computation in Galios field. When m(t<m<n) participants join the group authentication, the computation of m-t determinants is demanded, so the complexity of our proposed scheme is O((m-t)(t+1)(w+t+1log⁡(t+1))).By contrast with other group authentication schemes based on the secret sharing theory our scheme shows better efficiency, parallelization and accuracy, as shown in Table2. Harn’s scheme made use ofk different polynomials of degree t-1 to generatek tokens, the secret is magnified byktimes and the information rate is ρ=log2S/log2K<1, whereS is the secret andK is the total of secret share. Besides the thresholdt is restricted by the number of polynomials and the total of members, i.e., kt>n-1 in order to guarantee the security. For instance, if there are 1000 members and Harn’s scheme uses polynomials of degree 2 to generate tokens, at least 500 polynomials are demanded, which means that each member hold at least 500 shares as the token, thus the scheme is too inefficient. Miao’s scheme hide the secret shares by using blind factors which guarantee the asynchronism of token-showing, but the secret is not reused to next authentication once it is recovered. He’s scheme consists of unified authentication, which ensure that there are not any invalid member of participants, and single authentication, which run individual verifications one by one when unified authentication fails. But a permanent online sever is required in He’s scheme which does not apply to the de-centralized air warfare.Table 2
Comparison with other group authentication.
Manage mode Threshold restriction Information rate Basic theory Literature[4] Centralized ∖ ∖ Public key algorithm Literature[10] Distributed k t > n - 1 <1 Lagrange interpolation Literature[12] Distributed n > t 1 Chinese remainder theorem Literature[13] Centralized n > t <1 Lagrange interpolation Our scheme Distributed n > t 1 Sphere renconstruction


## 5.1. Comparison with Individual Authentication

Individual authentication means that every two participants verify each other and any participant need verify other participants. Assume that 5 communications is necessary in each individual authentication, and it costs5(m-1)! communications form participants to finish individual authentications mutually. However, it costs only 2m communications form participants to finish group authentication. One is for showing the token and the other is for issuing the decision. In terms of computation overhead our proposed group authentication scheme outperforms previously individual authentication. Individual authentication demands any participant to verify each of other participants, so the complexity is O(m), but our proposed group authentication scheme demands only one batch verification so as to determine whether there is any invalid participant. The complexity is O(1).


## 5.2. Comparison with Other Group Authentication

Our scheme is based on multidimensional sphere reconstruction theory instead of any mathematical hard problem. The computation overhead in our scheme is more lightweight, which contains neither bilinear pairing computation nor exponentiation, comparing with batch verification based on public key algorithm. Obviously our scheme mainly includes the calculation of high-order determinants which is associated with the number of participants. Concerning the efficiency of calculation Wiedemann [19] gave a probabilistic method whose complexity is O((t+1)(w+t+1log⁡(t+1))) for the calculation of t-1 order determinant, where w represents the total of computation in Galios field. When m(t<m<n) participants join the group authentication, the computation of m-t determinants is demanded, so the complexity of our proposed scheme is O((m-t)(t+1)(w+t+1log⁡(t+1))).By contrast with other group authentication schemes based on the secret sharing theory our scheme shows better efficiency, parallelization and accuracy, as shown in Table2. Harn’s scheme made use ofk different polynomials of degree t-1 to generatek tokens, the secret is magnified byktimes and the information rate is ρ=log2S/log2K<1, whereS is the secret andK is the total of secret share. Besides the thresholdt is restricted by the number of polynomials and the total of members, i.e., kt>n-1 in order to guarantee the security. For instance, if there are 1000 members and Harn’s scheme uses polynomials of degree 2 to generate tokens, at least 500 polynomials are demanded, which means that each member hold at least 500 shares as the token, thus the scheme is too inefficient. Miao’s scheme hide the secret shares by using blind factors which guarantee the asynchronism of token-showing, but the secret is not reused to next authentication once it is recovered. He’s scheme consists of unified authentication, which ensure that there are not any invalid member of participants, and single authentication, which run individual verifications one by one when unified authentication fails. But a permanent online sever is required in He’s scheme which does not apply to the de-centralized air warfare.Table 2
Comparison with other group authentication.
Manage mode Threshold restriction Information rate Basic theory Literature[4] Centralized ∖ ∖ Public key algorithm Literature[10] Distributed k t > n - 1 <1 Lagrange interpolation Literature[12] Distributed n > t 1 Chinese remainder theorem Literature[13] Centralized n > t <1 Lagrange interpolation Our scheme Distributed n > t 1 Sphere renconstruction


## 6. Conclusions and Future Work

We propose an asynchronous group authentication scheme based on space analytic geometry, which verifies if all participants belong to a predefined group at one time. Our scheme does depend on not any mathematical hard problem, but sphere reconstruction theorem of multidimension space. Each member has a unique share obtained from GM as the token. The token is a hidden coordinate, multiplied by a blind factor, of a point on(t-1) dimensional sphere, the center of which is the shared secret. While more thant participants show their tokens, we determine if participants are legal by verifying whether the shown token is on the (t-1) dimensional sphere. Analyses indicate that the proposed scheme can rule out fake outsider attackers and resist against coalition of insider attackers. In addition, compared with other schemes the proposed scheme is more applicable for air warfare network, with light-weight computation, flexible distribution, and high information rate.The proposed scheme actually puts forward a general method to construct an asynchronous group authentication scheme based on space analytic geometry. The participants pass the group authentication if and only if everyone’s token is valid. In our future work, we are about to address the problem of finding invalid efficiently when batch verification fails.



---

*Source: 5289383-2018-12-05.xml*