# A Novel Design of Membership Authentication and Group Key Establishment Protocol

Authors: Lein Harn; Ching-Fang Hsu
Journal: Security and Communication Networks
 (2017)

---

## Abstract

A new type of authentication, calledgroup authentication, has been proposed recently which can authenticate all users belonging to the same group at once in a group communication. However, the group authentication can only detect the existence of nonmembers but cannot identify who are the nonmembers. Furthermore, in a group communication, it needs not only to authenticate memberships but also to establish a group key among all members. In this paper, we propose a novel design to provide both membership authentication and group key establishment. Our proposed membership authentication can not only detect nonmembers but also identify who are the nonmembers. We first propose a basic membership authentication and key establishment protocol which can only support one-time group communication. Then, we extend the basic protocol to support multiple group communications. Our design is unique since tokens of users issued by a group manager (GM) during registration are used for both membership authentication and group key establishment.


---

## Body

## 1. Introduction

User authentication and key establishment are two primary security functions in most secure communications. User authentication is the process of determining whether someone is, in fact, who it is declared to be. Key establishment is the process of distributing a secret communication key to all users. The key can be used to protect the secrecy or integrity of exchange messages in the communication.The trend of communication research has been moved from peer-to-peer communication into group communication in which more than two users participated in the communication session. Although conventional peer-to-peer authentication [1, 2] can be used in group communication to authenticate participants in a straightforward manner the complexity of using this approach is O(n2), where n is the number of users involved in the group communication. In a recent paper [3], a new type of authentication, calledgroup authentication, has been proposed which is specially designed for the group communications. The complexity of using a group authentication is O1 in which it authenticates participants all at once. However, the group authentication can only detect the existence of nonmembers but cannot identify who are the nonmembers. Furthermore, in a group communication, it needs not only to authenticate memberships but also to establish a group key among all members.Centralized group key establishment protocols [4, 5] are the most widely used group key management protocols due to their efficiency. The centralized group key has a mutually trusted KGC to select a group key and then transport the group key to group members secretly. For example, the IEEE 802.11i standard [6] has an online server to select a group key and transport it to each group member. Laih et al. [7] proposed the first group key protocol using a (t,n) secret sharing scheme. Harn and Lin [8] proposed an authenticated group key transfer protocol based on a secret sharing scheme. The advantage of using a secret sharing scheme is its efficiency. However, the limitation of using a centralized group key establishment is due to its requirement of a trusted KGC. In some applications, such as in an ad hoc network, a trusted KGC may not be available.The most commonly used public-key agreement protocol is the Diffie-Hellman (DH) key exchange protocol [9, 10]. Harn and Lin [11] proposed a group DH protocol using the secret sharing scheme. Recently, Wu et al. [12] proposed a new approach which is a hybrid of group key agreement and public-key broadcast encryption. Their scheme is built from public-key based bilinear groups. The main disadvantage of the group DH key exchange is due to its computational and communication complexity since the group key is determined by all group members so each member needs to compute DH keys and exchange information to other members in the process.In this paper, we propose a novel design to provide both membership authentication and group key establishment. Our proposed membership authentication can not only detect nonmembers but also identify who are the nonmembers. In our protocols, members can accomplish membership authentication and key establishment by themselves without needing any other trusted KGC. We first propose a basic membership authentication and key establishment protocol which can only support one-time group communication. Then, we extend the basic protocol to support multiple group communications. Our design is unique since tokens of users issued by a group manager (GM) during registration are used for both membership authentication and group key establishment.Here, we summarize contributions of our paper.(i)
We propose protocols to provide both membership authentication and group key establishment. Our protocols do not need a trusted KGC in real-time to provide authentication and key establishment.(ii)
The membership authentication can not only detect nonmembers but also identify who are nonmembers.(iii)
Tokens of members obtained during registration can not only be used for membership authentication but also be used to establish a pairwise shared key between any pair of members.(iv)
All exchange information between members can be encrypted using pairwise shared keys.The rest of paper is organized as follows. In Section2, we provide some preliminaries, including bivariate polynomials and membership authentication and objectives of our proposed protocols. The basic protocol of membership authentication and group key establishment for one-time group communication is proposed in Section 3. The extended protocol for multiple group communications is presented in Section 4. The conclusion is given in Section 5.


## 2. Preliminaries

### 2.1. Bivariate Polynomials

Shamir’s(t,n) SS [13] is based on a univariate polynomial, f(x), with f(0)=s, where s is the secret. The dealer selects this polynomial with degree t-1 and uses it to generate shares, fximodp,i=1,2,…,n, for shareholders, where p is a prime with p>s, and xi is the public information associated with each shareholder.There are many(t,n) verifiable secret sharing schemes [14–16] using bivariate polynomials. A bivariate polynomial with degree t-1 can be represented as F(x,y)=a0,0+a1,0x+a0,1y+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+⋯+at-1,t-1xt-1yt-1nod⁡p, where ai,j∈GF(p),∀i,j∈[0,t-1]. If the coefficients satisfy ai,j=aj,i,∀i,j∈[0,t-1], it is a symmetric polynomial.The dealer can use a symmetric bivariate polynomial,F(x,y), to generate shares, Fxi,ymodp,i=1,2,…,n, for shareholders. Each share, F(xi,y), is a univariate polynomial with degree t-1. Note that since Fxi,xj=F(xj,xi),∀i,j∈[0,t-1], a pairwise key, Fxi,xj=Fxj,xi, can be established between shareholders, Ui and Uj. Thus, using a symmetric bivariate polynomial can enable two users to establish a pairwise shared key.


### 2.2. Membership Authentication and Key Establishment

In this section, we describe membership authentication proposed in this paper. Motivated by the group authentication [3] which authenticates users all at once with complexity O(1), we extend its capability of group authentication such that our protocol can not only detect the existence of nonmembers but also identify nonmembers. In our protocols, the GM is in charge of registering all members initially. GM selects a secret and hides the secret in a polynomial. GM issues tokens which are coordinate points on the polynomial to members initially.Later, in real-time operation, members can accomplish membership authentication and key establishment by themselves without the assistance of any trusted KGC. We need to point out that both GM and KGC must be trusted parties; but GM is needed only during initialization and KGC is needed during real-time implementation. Members present their tokens to be authenticated. Nonmembership detection process is first executed. If all released tokens are valid tokens, the secret can be recovered successfully and all users are members; otherwise the recovered secret is invalid so there exist nonmembers. Thus, the detectability of our protocol is guaranteed if there are a sufficient number of tokens available to recover the secret. In other words, the minimal number of tokens needed is determined by the degree of polynomial used to generate tokens initially.After nonmember being detected, nonmembership identification process is executed. The protocol first needs to identify a set of tokens which can recover the valid secret. The token holders are all members. Then, the set of valid tokens can be used as a base to check each remaining token to determine its validity. In this approach, nonmembers can be identified one at a time gradually. Thus, the identifiability of our protocol is guaranteed if there exists at least a set of valid tokens which can be used to recover the real secret.In the membership authentication, the GM is in charge of registering all members initially. GM knows all members; but each member does not need to know other members. This unique feature is especially suitable for some applications. For example, after an earthquake, the Department of Homeland Security may dispatch a responsive team which involves agents from different agencies, such as Department of Defense and Department of Health and Human Services, to form a mobile ad hoc network and uses the network to exchange sensitive information. In such network, there is a GM to register members initially; but each member does not need to know other members. The GM issues tokens to members before deploying them to the disaster site. In forming such a secure ad hoc network, all members can follow the membership authentication protocol without the assistance of the GM. If all users are legitimate members, the outcome of the membership authentication can authenticate users all at once; otherwise, the membership authentication can further identify nonmembers. Finally, a group key is shared among all members.During system setup, the GM follows a(t,n) SS to select a univariate polynomial, f(x), with degree t-1 and f(0)=s, where s is the secret. The GM generates tokens, fxi,i=1,2,…,n, for members, where xi is the public information associated with each member Ui. The GM sends each token si to each member Ui∈U secretly. The GM makes H(s) publicly known, where H(s) is a one-way function of the secret. In a membership authentication which involves μ(i.e.,t≤μ≤n) users, for example, Pvi,i=1,2,…,μ, each user uses his token to compute, cvi, as his released value. Each cvi will be encrypted using a pairwise shared key and send it to each other user separately. After decrypting and collecting all released values, cvi,i=1,2,…,μ, each member can compute Fcv1,cv2,…,cvμ, where F is a public function. There is a nonmembership detection algorithm, GA, which allows each user to determine whether all users are members based on their released values. That is,(1)GAHs?__HFcv1,cv2,…,cvμ=0⟶∃Pvi∉U;1⟶∀Pvi∈U.Furthermore, if there are nonmembers, a nonmembership identification algorithm can identify nonmembers.In a secure group communication, it needs not only membership authentication but also a group key establishment to distribute a group key to all members. The group key is used to protect exchange messages. One unique feature of our proposed protocols is that tokens of members generated by GM initially can not only be used to authenticate membership but also be used to establish pairwise keys between any pair of members. Therefore, in our protocols, all exchange information between members is encrypted by pairwise shared keys and thus the recovered secret is not available to nonmembers. We propose using the recovered secret as the group key for secure communication. This proposed key establishment is accomplished efficiently.


### 2.3. Objectives of Our Protocols

#### 2.3.1. Security Objective

In our protocols, we consider two types of adversaries: insider and outsider.Inside Attacker. Inside attacker is a legitimate member who owns a token generated by GM. But inside attacker may try to recover other member’s token. After obtaining other members’ tokens, the inside attacker is able to recover the secret of GM and forge tokens for attackers. We will also consider attack imposed by colluded inside attackers.Outside Attacker. Outside attacker is an attacker who does not own any token generated by GM and may try to impersonate a legitimate member or to recover the secret group key.


#### 2.3.2. Performance Objective

The objectives of membership authentication are not only to detect the existence of nonmembers but also to identify nonmembers. The following two properties are associated with our proposed protocols.Detectability. This property means the ability of membership authentication to detect the existence of nonmembers.Identifiability. This property means the ability of membership authentication to identify who are nonmembers.In Section3.2, we will examine conditions which will limit these two properties.


## 2.1. Bivariate Polynomials

Shamir’s(t,n) SS [13] is based on a univariate polynomial, f(x), with f(0)=s, where s is the secret. The dealer selects this polynomial with degree t-1 and uses it to generate shares, fximodp,i=1,2,…,n, for shareholders, where p is a prime with p>s, and xi is the public information associated with each shareholder.There are many(t,n) verifiable secret sharing schemes [14–16] using bivariate polynomials. A bivariate polynomial with degree t-1 can be represented as F(x,y)=a0,0+a1,0x+a0,1y+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+⋯+at-1,t-1xt-1yt-1nod⁡p, where ai,j∈GF(p),∀i,j∈[0,t-1]. If the coefficients satisfy ai,j=aj,i,∀i,j∈[0,t-1], it is a symmetric polynomial.The dealer can use a symmetric bivariate polynomial,F(x,y), to generate shares, Fxi,ymodp,i=1,2,…,n, for shareholders. Each share, F(xi,y), is a univariate polynomial with degree t-1. Note that since Fxi,xj=F(xj,xi),∀i,j∈[0,t-1], a pairwise key, Fxi,xj=Fxj,xi, can be established between shareholders, Ui and Uj. Thus, using a symmetric bivariate polynomial can enable two users to establish a pairwise shared key.


## 2.2. Membership Authentication and Key Establishment

In this section, we describe membership authentication proposed in this paper. Motivated by the group authentication [3] which authenticates users all at once with complexity O(1), we extend its capability of group authentication such that our protocol can not only detect the existence of nonmembers but also identify nonmembers. In our protocols, the GM is in charge of registering all members initially. GM selects a secret and hides the secret in a polynomial. GM issues tokens which are coordinate points on the polynomial to members initially.Later, in real-time operation, members can accomplish membership authentication and key establishment by themselves without the assistance of any trusted KGC. We need to point out that both GM and KGC must be trusted parties; but GM is needed only during initialization and KGC is needed during real-time implementation. Members present their tokens to be authenticated. Nonmembership detection process is first executed. If all released tokens are valid tokens, the secret can be recovered successfully and all users are members; otherwise the recovered secret is invalid so there exist nonmembers. Thus, the detectability of our protocol is guaranteed if there are a sufficient number of tokens available to recover the secret. In other words, the minimal number of tokens needed is determined by the degree of polynomial used to generate tokens initially.After nonmember being detected, nonmembership identification process is executed. The protocol first needs to identify a set of tokens which can recover the valid secret. The token holders are all members. Then, the set of valid tokens can be used as a base to check each remaining token to determine its validity. In this approach, nonmembers can be identified one at a time gradually. Thus, the identifiability of our protocol is guaranteed if there exists at least a set of valid tokens which can be used to recover the real secret.In the membership authentication, the GM is in charge of registering all members initially. GM knows all members; but each member does not need to know other members. This unique feature is especially suitable for some applications. For example, after an earthquake, the Department of Homeland Security may dispatch a responsive team which involves agents from different agencies, such as Department of Defense and Department of Health and Human Services, to form a mobile ad hoc network and uses the network to exchange sensitive information. In such network, there is a GM to register members initially; but each member does not need to know other members. The GM issues tokens to members before deploying them to the disaster site. In forming such a secure ad hoc network, all members can follow the membership authentication protocol without the assistance of the GM. If all users are legitimate members, the outcome of the membership authentication can authenticate users all at once; otherwise, the membership authentication can further identify nonmembers. Finally, a group key is shared among all members.During system setup, the GM follows a(t,n) SS to select a univariate polynomial, f(x), with degree t-1 and f(0)=s, where s is the secret. The GM generates tokens, fxi,i=1,2,…,n, for members, where xi is the public information associated with each member Ui. The GM sends each token si to each member Ui∈U secretly. The GM makes H(s) publicly known, where H(s) is a one-way function of the secret. In a membership authentication which involves μ(i.e.,t≤μ≤n) users, for example, Pvi,i=1,2,…,μ, each user uses his token to compute, cvi, as his released value. Each cvi will be encrypted using a pairwise shared key and send it to each other user separately. After decrypting and collecting all released values, cvi,i=1,2,…,μ, each member can compute Fcv1,cv2,…,cvμ, where F is a public function. There is a nonmembership detection algorithm, GA, which allows each user to determine whether all users are members based on their released values. That is,(1)GAHs?__HFcv1,cv2,…,cvμ=0⟶∃Pvi∉U;1⟶∀Pvi∈U.Furthermore, if there are nonmembers, a nonmembership identification algorithm can identify nonmembers.In a secure group communication, it needs not only membership authentication but also a group key establishment to distribute a group key to all members. The group key is used to protect exchange messages. One unique feature of our proposed protocols is that tokens of members generated by GM initially can not only be used to authenticate membership but also be used to establish pairwise keys between any pair of members. Therefore, in our protocols, all exchange information between members is encrypted by pairwise shared keys and thus the recovered secret is not available to nonmembers. We propose using the recovered secret as the group key for secure communication. This proposed key establishment is accomplished efficiently.


## 2.3. Objectives of Our Protocols

### 2.3.1. Security Objective

In our protocols, we consider two types of adversaries: insider and outsider.Inside Attacker. Inside attacker is a legitimate member who owns a token generated by GM. But inside attacker may try to recover other member’s token. After obtaining other members’ tokens, the inside attacker is able to recover the secret of GM and forge tokens for attackers. We will also consider attack imposed by colluded inside attackers.Outside Attacker. Outside attacker is an attacker who does not own any token generated by GM and may try to impersonate a legitimate member or to recover the secret group key.


### 2.3.2. Performance Objective

The objectives of membership authentication are not only to detect the existence of nonmembers but also to identify nonmembers. The following two properties are associated with our proposed protocols.Detectability. This property means the ability of membership authentication to detect the existence of nonmembers.Identifiability. This property means the ability of membership authentication to identify who are nonmembers.In Section3.2, we will examine conditions which will limit these two properties.


## 2.3.1. Security Objective

In our protocols, we consider two types of adversaries: insider and outsider.Inside Attacker. Inside attacker is a legitimate member who owns a token generated by GM. But inside attacker may try to recover other member’s token. After obtaining other members’ tokens, the inside attacker is able to recover the secret of GM and forge tokens for attackers. We will also consider attack imposed by colluded inside attackers.Outside Attacker. Outside attacker is an attacker who does not own any token generated by GM and may try to impersonate a legitimate member or to recover the secret group key.


## 2.3.2. Performance Objective

The objectives of membership authentication are not only to detect the existence of nonmembers but also to identify nonmembers. The following two properties are associated with our proposed protocols.Detectability. This property means the ability of membership authentication to detect the existence of nonmembers.Identifiability. This property means the ability of membership authentication to identify who are nonmembers.In Section3.2, we will examine conditions which will limit these two properties.


## 3. Basic Protocol of Membership Authentication and Key Establishment

In our design, the GM uses a bivariate polynomial to generate tokens for members. The tokens can be used not only to establish pairwise keys between any pair of members but also to achieve membership authentication and group key establishment.


### 3.1. Algorithm

Basic Protocol of Membership Authentication and Key EstablishmentToken Generation. The GM selects a t-1 degree symmetric polynomial: (2)Fx,y=a0,0+a1,0x+a0,1y+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+⋯+at-1,t-1,t-1xt-1yt-1nod⁡p,where F(0,0)=s,ai,j∈GF(p),ai,j=aj,i,∀i,j∈[0,t-1], s is the secret, and p is a prime with p>s. The GM computes tokens, si(y)=Fxi,ymodp, for group members, Ui,i=1,2,…,n, where xi is the public information associated with each group member, Ui. The GM sends each token, si(y), to member Ui secretly. The GM makes Hs publicly known, where H(s) is a one-way function of the secret.Membership Authentication and Key Establishment. Assume that u (i.e., t≤u≤n) members, Uv1,Uv2,…,Uvu, want to establish a secure group communication.Step 1.
Each memberUvi uses his/her token, svi(y), to compute wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp.Step 2.
Each memberUvi uses his/her token, svi(y), to compute pairwise shared keys, ki,j=svi(xvj)=F(xvi,xvj),j=1,2,…,u,j≠i, where ki,j is the secret key shared between members, Uvi and Uvj.Step 3.
Each memberUvi computes ci,j=Eki,jwvi,j=1,2,…,u,j≠i, where Eki,jwvi denotes the conventional encryption of wvi using the key ki,j, each member Uvici,j,j=1,2,…,u,j≠i, to other members.Step 4.
After receiving ciphertext,cj,i,j=1,2,…,u,j≠i, from other members, Uvi computes wvj=Dki,j(cj,i),j=1,2,…,u,j≠i, where Dki,j(cj,i) denotes the decryption of cj,i using the key ki,j.Nonmembership DetectionStep 5.
Each memberUvi computes ∑i=1uwvimodp=s′. If H(s)=Hs′, all members have been successfully authenticated and s is the group communication key; otherwise, there are nonmembers and continue on next step.Nonmembership IdentificationStep 6.
Each memberUvi uses wvj,j=1,2,…,u,j≠i, obtained from Step 4 to compute svj(0)=wvj∏l=1,l≠ju-xvl/xvj-xvl-1modp,j=1,2,…,u,j≠i.Step 7.
Each memberUvi searches for a subset of t values from the set, svj0,j=1,2,…,u, for example, the subset is svj0,j=1,2,…,t, and uses them to compute s′=∑i=1tsvi0∏l=1,l≠it-xvl/xvi-xvlmodp. If Hs′=H(s), then tokens in this sunset are all valid and they are members; s is the group communication key. Then, this subset is used as a base to test each remaining token one at a time to check whether using this token and all tokens in the subset can still recover the same secret or not. If it is so, the token is valid and the token holder is a member; otherwise, it is invalid and the token holder is a nonmember.


### 3.2. Analysis

(i) CorrectnessNonmembership Detection. In Step 1, each member Uvi uses his/her token to compute the partial information of the secret, wvi, and, in Step 2, to compute pairwise secret keys shared with other members. In Step 3, the partial information of the secret wvi is encrypted using these pairwise shared keys to other members and then, in Step 4, each member Uvi recovers wvj(j=1,…,u,j≠i), from other members. Finally, in Step 5, since wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp and si(y)=Fxi,ymodp, following Lagrange interpolation formula, we have ∑i=1uwvimodp=∑i=1uF(xvi,0)∏l=1,l≠iu-xvl/xvi-xvlmodp=F0,0=s. It implies that any subset A=Uv1,Uv2,…,Uvu∈Γ with t or more than t members can work together with others to compute ∑i=1uwvimodp=s′. Hence, it holds that H(s)=Hs′. On the other hand, if there are nonmembers, then H(s)≠Hs′.Nonmembership Identification. Following Lagrange interpolation formula, in Step 7 of our proposed protocol, any t members with their valid tokens, for example, the subset of tokens is svjy,j=1,2,…,t, can use their tokens to recover the secret. This set of valid tokens can be used to test the validity of each remaining token one at a time. The test procedure is just by including this token and all tokens in the set to check whether it can still recover the same secret or not. This process can be used to identify nonmembers.(ii) SecurityTheorem 1 (inside attack).
The proposed basic protocol can resist up tot-1/2 colluded members to recover the secret polynomial F(x,y) of GM.Proof.
F
(
x
,
y
) is a symmetric polynomial with ai,j∈GFp,ai,j=aj,i,∀i,j∈0,t-1, selected by GM which contains t(t+1)/2 different coefficients. In the proposed basic protocol, each token, si(y), is a univariate polynomial with degree t-1. In other words, each member can use his token to establish t linearly independent equations in terms of the coefficients of the polynomial F(x,y). There are ht linearly independent equations with knowing h tokens. If GM wants to prevent up to h colluded group members from recovering the secret polynomial, F(x,y), it needs t(t+1)/2>ht⇒t+1>2h. Thus, up to t-1/2 colluded members cannot recover the secret polynomial, F(x,y).Theorem 2 (outside attack).
The proposed basic protocol can resist any nonmember to obtain the secret.Proof.
In our proposed protocol, the partial information of the secret is encrypted using pairwise keys shared with other group members. Since nonmember does not own any valid token generated by the GM, nonmembers neither can impersonate any group members nor can decrypt any ciphertext, then, to obtain the partial information of the secret. Thus, after all members are successfully authenticated, the recovered secret can be used as the secret group key since the recovered secret is not available to nonmembers.(iii) PerformanceDetectability. The nonmembership detection is based on Lagrange interpolation formula. That is, withtor more thantcoordinate points of a polynomial can uniquely determine this polynomial and the secret; however, if there is any invalid value in the set of coordinate points, it cannot determine the original polynomial and the secret. Thus, our nonmembership detection can detect the existence of nonmembers. The only condition which limits the detectability is that it requires to have at leastttokens presented in the process.Identifiability. The nonmembership identification is based on the polynomial and the secret which was used to generate tokens initially. According to Lagrange interpolation formula, anytvalid tokens can recover this original polynomial. Thus, each member needs first to search for a set oftvalid tokens which can be used to recover the real secret. The token holders in this set are members. Then, this set of tokens is used as a base to test each remaining token by checking whether with this token and all tokens in the base the same secret can still be recovered or not. If it is so, the token holder is a member; otherwise, the token holder is a nonmember. The only condition which limits the identifiability is that it requires having at leasttvalid tokens presented in the protocols.Computational Complexity. In the basic protocol, each token, si(y), is a univariate polynomial with degree t-1. Thus, each member needs to store t coefficients of a univariate polynomial. The memory storage of each shareholder is tlog2⁡p bits, where p is the modulus. In the protocol, there is no interaction among users. Each member Uvi sends ciphertext ci,j=Eki,j(wvi),j=1,2,…,u,j≠i, to other members. Horner’s rule [17] can be used to evaluate polynomials. In the following discussion, we show the cost for computing wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp, in Step 1. From Horner’s rule, evaluating a polynomial of degree t-1 needs t-1 multiplications and t additions. Since multiplication takes more time than addition, the performance is only addressed to the number of multiplications needed. The computational cost in Step 1 to compute wvi is to evaluate one polynomial. The computational cost in Step 2 to compute pairwise shared keys, ki,j=svi(xvj),j=1,2,…,u,j≠i, is to evaluate u-1 polynomials, where u is the number of members participating in the secret reconstruction. Overall, the computational cost to reconstruct the secret of each member is to compute ut multiplications.In our proposed protocol, the main computation is the polynomial evaluation. The modulus in our polynomial computation is much smaller than the modulus (e.g., 1,024 bits) used in most public-key cryptosystems. In addition, not like most conventional user authentication protocol which authenticates one user each time, the proposed protocol authenticates all users at once. After all users are successfully authenticated, there is no computation needed to establish a group key. Thus, the proposed protocol is very efficient in comparing with most communication protocols.However, if there exist nonmembers, the nonmembership identification is invoked. Since each member needs to search for a subset oftvalid tokens from a set containing u users participating in a secure group communication, the complexity of this searching is O(u!), where u is the number of participants in a group communication. We would like to point out that in some practical applications u can be a small integer. Once this subset of valid tokens is determined, Lagrange interpolation formula is executed to test each remaining token one at a time to identify whether it is an invalid token or not.After user authentication and key establishment, all participating members can recover the secret and the tokens,si(0),i=1,2,…,n, of other members. In other words, the tokens cannot be reused for multiple times since members can impersonate other members participating in different secret group communications. In the next section, we extend the basic protocol to support multiple group communications.


## 3.1. Algorithm

Basic Protocol of Membership Authentication and Key EstablishmentToken Generation. The GM selects a t-1 degree symmetric polynomial: (2)Fx,y=a0,0+a1,0x+a0,1y+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+⋯+at-1,t-1,t-1xt-1yt-1nod⁡p,where F(0,0)=s,ai,j∈GF(p),ai,j=aj,i,∀i,j∈[0,t-1], s is the secret, and p is a prime with p>s. The GM computes tokens, si(y)=Fxi,ymodp, for group members, Ui,i=1,2,…,n, where xi is the public information associated with each group member, Ui. The GM sends each token, si(y), to member Ui secretly. The GM makes Hs publicly known, where H(s) is a one-way function of the secret.Membership Authentication and Key Establishment. Assume that u (i.e., t≤u≤n) members, Uv1,Uv2,…,Uvu, want to establish a secure group communication.Step 1.
Each memberUvi uses his/her token, svi(y), to compute wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp.Step 2.
Each memberUvi uses his/her token, svi(y), to compute pairwise shared keys, ki,j=svi(xvj)=F(xvi,xvj),j=1,2,…,u,j≠i, where ki,j is the secret key shared between members, Uvi and Uvj.Step 3.
Each memberUvi computes ci,j=Eki,jwvi,j=1,2,…,u,j≠i, where Eki,jwvi denotes the conventional encryption of wvi using the key ki,j, each member Uvici,j,j=1,2,…,u,j≠i, to other members.Step 4.
After receiving ciphertext,cj,i,j=1,2,…,u,j≠i, from other members, Uvi computes wvj=Dki,j(cj,i),j=1,2,…,u,j≠i, where Dki,j(cj,i) denotes the decryption of cj,i using the key ki,j.Nonmembership DetectionStep 5.
Each memberUvi computes ∑i=1uwvimodp=s′. If H(s)=Hs′, all members have been successfully authenticated and s is the group communication key; otherwise, there are nonmembers and continue on next step.Nonmembership IdentificationStep 6.
Each memberUvi uses wvj,j=1,2,…,u,j≠i, obtained from Step 4 to compute svj(0)=wvj∏l=1,l≠ju-xvl/xvj-xvl-1modp,j=1,2,…,u,j≠i.Step 7.
Each memberUvi searches for a subset of t values from the set, svj0,j=1,2,…,u, for example, the subset is svj0,j=1,2,…,t, and uses them to compute s′=∑i=1tsvi0∏l=1,l≠it-xvl/xvi-xvlmodp. If Hs′=H(s), then tokens in this sunset are all valid and they are members; s is the group communication key. Then, this subset is used as a base to test each remaining token one at a time to check whether using this token and all tokens in the subset can still recover the same secret or not. If it is so, the token is valid and the token holder is a member; otherwise, it is invalid and the token holder is a nonmember.


## 3.2. Analysis

(i) CorrectnessNonmembership Detection. In Step 1, each member Uvi uses his/her token to compute the partial information of the secret, wvi, and, in Step 2, to compute pairwise secret keys shared with other members. In Step 3, the partial information of the secret wvi is encrypted using these pairwise shared keys to other members and then, in Step 4, each member Uvi recovers wvj(j=1,…,u,j≠i), from other members. Finally, in Step 5, since wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp and si(y)=Fxi,ymodp, following Lagrange interpolation formula, we have ∑i=1uwvimodp=∑i=1uF(xvi,0)∏l=1,l≠iu-xvl/xvi-xvlmodp=F0,0=s. It implies that any subset A=Uv1,Uv2,…,Uvu∈Γ with t or more than t members can work together with others to compute ∑i=1uwvimodp=s′. Hence, it holds that H(s)=Hs′. On the other hand, if there are nonmembers, then H(s)≠Hs′.Nonmembership Identification. Following Lagrange interpolation formula, in Step 7 of our proposed protocol, any t members with their valid tokens, for example, the subset of tokens is svjy,j=1,2,…,t, can use their tokens to recover the secret. This set of valid tokens can be used to test the validity of each remaining token one at a time. The test procedure is just by including this token and all tokens in the set to check whether it can still recover the same secret or not. This process can be used to identify nonmembers.(ii) SecurityTheorem 1 (inside attack).
The proposed basic protocol can resist up tot-1/2 colluded members to recover the secret polynomial F(x,y) of GM.Proof.
F
(
x
,
y
) is a symmetric polynomial with ai,j∈GFp,ai,j=aj,i,∀i,j∈0,t-1, selected by GM which contains t(t+1)/2 different coefficients. In the proposed basic protocol, each token, si(y), is a univariate polynomial with degree t-1. In other words, each member can use his token to establish t linearly independent equations in terms of the coefficients of the polynomial F(x,y). There are ht linearly independent equations with knowing h tokens. If GM wants to prevent up to h colluded group members from recovering the secret polynomial, F(x,y), it needs t(t+1)/2>ht⇒t+1>2h. Thus, up to t-1/2 colluded members cannot recover the secret polynomial, F(x,y).Theorem 2 (outside attack).
The proposed basic protocol can resist any nonmember to obtain the secret.Proof.
In our proposed protocol, the partial information of the secret is encrypted using pairwise keys shared with other group members. Since nonmember does not own any valid token generated by the GM, nonmembers neither can impersonate any group members nor can decrypt any ciphertext, then, to obtain the partial information of the secret. Thus, after all members are successfully authenticated, the recovered secret can be used as the secret group key since the recovered secret is not available to nonmembers.(iii) PerformanceDetectability. The nonmembership detection is based on Lagrange interpolation formula. That is, withtor more thantcoordinate points of a polynomial can uniquely determine this polynomial and the secret; however, if there is any invalid value in the set of coordinate points, it cannot determine the original polynomial and the secret. Thus, our nonmembership detection can detect the existence of nonmembers. The only condition which limits the detectability is that it requires to have at leastttokens presented in the process.Identifiability. The nonmembership identification is based on the polynomial and the secret which was used to generate tokens initially. According to Lagrange interpolation formula, anytvalid tokens can recover this original polynomial. Thus, each member needs first to search for a set oftvalid tokens which can be used to recover the real secret. The token holders in this set are members. Then, this set of tokens is used as a base to test each remaining token by checking whether with this token and all tokens in the base the same secret can still be recovered or not. If it is so, the token holder is a member; otherwise, the token holder is a nonmember. The only condition which limits the identifiability is that it requires having at leasttvalid tokens presented in the protocols.Computational Complexity. In the basic protocol, each token, si(y), is a univariate polynomial with degree t-1. Thus, each member needs to store t coefficients of a univariate polynomial. The memory storage of each shareholder is tlog2⁡p bits, where p is the modulus. In the protocol, there is no interaction among users. Each member Uvi sends ciphertext ci,j=Eki,j(wvi),j=1,2,…,u,j≠i, to other members. Horner’s rule [17] can be used to evaluate polynomials. In the following discussion, we show the cost for computing wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp, in Step 1. From Horner’s rule, evaluating a polynomial of degree t-1 needs t-1 multiplications and t additions. Since multiplication takes more time than addition, the performance is only addressed to the number of multiplications needed. The computational cost in Step 1 to compute wvi is to evaluate one polynomial. The computational cost in Step 2 to compute pairwise shared keys, ki,j=svi(xvj),j=1,2,…,u,j≠i, is to evaluate u-1 polynomials, where u is the number of members participating in the secret reconstruction. Overall, the computational cost to reconstruct the secret of each member is to compute ut multiplications.In our proposed protocol, the main computation is the polynomial evaluation. The modulus in our polynomial computation is much smaller than the modulus (e.g., 1,024 bits) used in most public-key cryptosystems. In addition, not like most conventional user authentication protocol which authenticates one user each time, the proposed protocol authenticates all users at once. After all users are successfully authenticated, there is no computation needed to establish a group key. Thus, the proposed protocol is very efficient in comparing with most communication protocols.However, if there exist nonmembers, the nonmembership identification is invoked. Since each member needs to search for a subset oftvalid tokens from a set containing u users participating in a secure group communication, the complexity of this searching is O(u!), where u is the number of participants in a group communication. We would like to point out that in some practical applications u can be a small integer. Once this subset of valid tokens is determined, Lagrange interpolation formula is executed to test each remaining token one at a time to identify whether it is an invalid token or not.After user authentication and key establishment, all participating members can recover the secret and the tokens,si(0),i=1,2,…,n, of other members. In other words, the tokens cannot be reused for multiple times since members can impersonate other members participating in different secret group communications. In the next section, we extend the basic protocol to support multiple group communications.


## 4. Extended Protocol for Multiple Group Communications

In this section, an extended protocol in which tokens obtained from the GM initially can be reused for multiple group communications is presented. The basic idea is that the GM needs to select two large public primes,p and q, such that p divides q-1, GF(p) is a unique subgroup of GF(q) with order p, and every gi is a generator of GF(p). GM follows the sametoken generation procedure as described in Section 3 to select a symmetric polynomial, F(x,y), and generate tokens, si(y)=F(xi,y)modp, for group members, Ui,i=1,2,…,n. In addition, GM computes, si=gis,i=1,2,…,m, and makes gi,Hsi∣i=1,2,…,m publicly known, wherem is the number of secure group communications that the protocol can support.


### 4.1. Algorithm

Extended Protocol for Multiple Group CommunicationsGroup Authentication and Key Establishment. Assume that, at jth round, u (i.e., t≤u≤n) members, Uv1,Uv2,…,Uvu, want to establish a secure group communication.Step 1.
Each memberUvi uses his/her token, svi(y), to compute wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp, and dvi=gjwvimodq.Step 2.
Each memberUvi uses his/her token, svi(y), to compute pairwise shared keys, ki,r=svi(xvr)=Fxvi,xvr,r=1,2,…,u,r≠i, where ki,r is the secret key shared between members, Uvi and Uvr.Step 3.
Each memberUvi computes ci,r=Eki,r(dvi),r=1,2,…,u,r≠i, where Eki,rdvi denotes the conventional encryption of dvi using the key ki,r. Each member Uvi sends ci,r,r=1,2,…,u,r≠i, to other members.Step 4.
After receiving ciphertext,cr,i,r=1,2,…,u,r≠i, from other members, Uvi computes dvr=Dki,r(cr,i),r=1,2,…,u,r≠i, where Dki,r(cr,i) denotes the decryption of cr,i using the key ki,r.Nonmembership DetectionStep 5.
Each memberUvi computes ∏i=1udvimodq=sj′. If H(sj)=Hsj′, all members have been successfully authenticated and sj is the group communication key; otherwise, there are nonmembers and continue on next step.Nonmembership IdentificationStep 6.
Each memberUvi uses dvr,r=1,2,…,u,r≠i, obtained from Step 4 to compute cvr=dvr∏l=1,l≠ru-xvl/xvr-xvl-1modpmodq,r=1,2,…,u,r≠i.Step 7.
Each memberUvi searches for a subset of t values from the set, cvr,r=1,2,…,u, for example, the subset is cvr,r=1,2,…,t, and uses them to compute ∏i=1tcvr∏l=1,l≠it-xvl/xvi-xvlmodpmodq=sj′. If H(sj)=Hsj′, then tokens in this sunset are all valid and they are members and sj is the group communication key. Then, this subset is used as a base to test each remaining token one at a time to check whether using this token and all tokens in the subset can still recover the same secret or not. If it is so, the token is valid and the token holder is a member; otherwise, it is invalid and the token holder is a nonmember.


### 4.2. Analysis

(i) CorrectnessNonmembership Detection. In Step 5, since wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp, dvi=gjwvimodq and siy=Fxi,ymodp, following Lagrange interpolation formula, we have ∏i=1udvimodq=∏i=1ugjwvimodq=gj∑i=1uwvimodpmodq=gj∑i=1uF(xvi,0)∏l=1,l≠iu-xvl/xvi-xvlmodpmodq=gjF(0,0)modq=gjsmodq=sj. It implies that any subset A=Uv1,Uv2,…,Uvu∈Γ of group members can work together to compute ∏i=1udvimodq=sj′. Hence, it holds that Hsj=Hsj′. Otherwise, if there are nonmembers, then Hsj≠Hsj′.Nonmembership Identification. In Step 6, we get cvr=dvr∏l=1,l≠ru-xvl/xvr-xvl-1modpmodq=gjwvr∏l=1,l≠ru-xvl/xvr-xvl-1modpmodq=gjsvr(0)modpmodq. Thus, in Step 7, if values in the subset cvr,r=1,2,…,t are all valid, we should have ∏i=1t‍cvr∏l=1,l≠it-xvl/xvi-xvlmodpmodq=sj.(ii) Security. In this extended protocol, each member’s private value of token, svi(0), is protected in the value dvi=gjwvimodq, under the discrete logarithm assumption. Similarly, the secret, s, is protected in the public value, si=gis,i=1,2,…,m, under the discrete logarithm assumption.(iii) Performance. The modular exponentiation takes more computational time than multiplication and addition. So, we only consider the modular exponentiation in the following discussion. In this extended protocol, each member needs to compute only one modular exponentiation if all users are members. However, if there are nonmembers, more modular exponentiations are needed to identify nonmembers.Remark 3.
In comparison between algorithms presented in Sections3 and 4, tokens generated during initiation can only be used for one group communication in the basic algorithm but tokens can be used for multiple group communications in the extended algorithm. Furthermore, only polynomial evaluations are needed in the basic algorithm but modular exponentiations are needed in the extended algorithm. According to Horner’s rule [17], each polynomial evaluation needs t modular multiplications. But, each modular exponentiation with two large moduli, p and q (say p is 160 bits and q is 1024 bits), needs 1.5log2⁡p modular multiplications. Since t is much smaller than p, computational speed in the basic algorithm is much faster than computational speed in the extended algorithm.


## 4.1. Algorithm

Extended Protocol for Multiple Group CommunicationsGroup Authentication and Key Establishment. Assume that, at jth round, u (i.e., t≤u≤n) members, Uv1,Uv2,…,Uvu, want to establish a secure group communication.Step 1.
Each memberUvi uses his/her token, svi(y), to compute wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp, and dvi=gjwvimodq.Step 2.
Each memberUvi uses his/her token, svi(y), to compute pairwise shared keys, ki,r=svi(xvr)=Fxvi,xvr,r=1,2,…,u,r≠i, where ki,r is the secret key shared between members, Uvi and Uvr.Step 3.
Each memberUvi computes ci,r=Eki,r(dvi),r=1,2,…,u,r≠i, where Eki,rdvi denotes the conventional encryption of dvi using the key ki,r. Each member Uvi sends ci,r,r=1,2,…,u,r≠i, to other members.Step 4.
After receiving ciphertext,cr,i,r=1,2,…,u,r≠i, from other members, Uvi computes dvr=Dki,r(cr,i),r=1,2,…,u,r≠i, where Dki,r(cr,i) denotes the decryption of cr,i using the key ki,r.Nonmembership DetectionStep 5.
Each memberUvi computes ∏i=1udvimodq=sj′. If H(sj)=Hsj′, all members have been successfully authenticated and sj is the group communication key; otherwise, there are nonmembers and continue on next step.Nonmembership IdentificationStep 6.
Each memberUvi uses dvr,r=1,2,…,u,r≠i, obtained from Step 4 to compute cvr=dvr∏l=1,l≠ru-xvl/xvr-xvl-1modpmodq,r=1,2,…,u,r≠i.Step 7.
Each memberUvi searches for a subset of t values from the set, cvr,r=1,2,…,u, for example, the subset is cvr,r=1,2,…,t, and uses them to compute ∏i=1tcvr∏l=1,l≠it-xvl/xvi-xvlmodpmodq=sj′. If H(sj)=Hsj′, then tokens in this sunset are all valid and they are members and sj is the group communication key. Then, this subset is used as a base to test each remaining token one at a time to check whether using this token and all tokens in the subset can still recover the same secret or not. If it is so, the token is valid and the token holder is a member; otherwise, it is invalid and the token holder is a nonmember.


## 4.2. Analysis

(i) CorrectnessNonmembership Detection. In Step 5, since wvi=svi(0)∏l=1,l≠iu-xvl/xvi-xvlmodp, dvi=gjwvimodq and siy=Fxi,ymodp, following Lagrange interpolation formula, we have ∏i=1udvimodq=∏i=1ugjwvimodq=gj∑i=1uwvimodpmodq=gj∑i=1uF(xvi,0)∏l=1,l≠iu-xvl/xvi-xvlmodpmodq=gjF(0,0)modq=gjsmodq=sj. It implies that any subset A=Uv1,Uv2,…,Uvu∈Γ of group members can work together to compute ∏i=1udvimodq=sj′. Hence, it holds that Hsj=Hsj′. Otherwise, if there are nonmembers, then Hsj≠Hsj′.Nonmembership Identification. In Step 6, we get cvr=dvr∏l=1,l≠ru-xvl/xvr-xvl-1modpmodq=gjwvr∏l=1,l≠ru-xvl/xvr-xvl-1modpmodq=gjsvr(0)modpmodq. Thus, in Step 7, if values in the subset cvr,r=1,2,…,t are all valid, we should have ∏i=1t‍cvr∏l=1,l≠it-xvl/xvi-xvlmodpmodq=sj.(ii) Security. In this extended protocol, each member’s private value of token, svi(0), is protected in the value dvi=gjwvimodq, under the discrete logarithm assumption. Similarly, the secret, s, is protected in the public value, si=gis,i=1,2,…,m, under the discrete logarithm assumption.(iii) Performance. The modular exponentiation takes more computational time than multiplication and addition. So, we only consider the modular exponentiation in the following discussion. In this extended protocol, each member needs to compute only one modular exponentiation if all users are members. However, if there are nonmembers, more modular exponentiations are needed to identify nonmembers.Remark 3.
In comparison between algorithms presented in Sections3 and 4, tokens generated during initiation can only be used for one group communication in the basic algorithm but tokens can be used for multiple group communications in the extended algorithm. Furthermore, only polynomial evaluations are needed in the basic algorithm but modular exponentiations are needed in the extended algorithm. According to Horner’s rule [17], each polynomial evaluation needs t modular multiplications. But, each modular exponentiation with two large moduli, p and q (say p is 160 bits and q is 1024 bits), needs 1.5log2⁡p modular multiplications. Since t is much smaller than p, computational speed in the basic algorithm is much faster than computational speed in the extended algorithm.


## 5. Conclusion

We propose two efficient protocols of membership authentication and key establishment. The basic protocol can support a one-time communication in which each member needs only to perform polynomial evaluation. The extended protocol can support multiple communications in which each member needs to perform modular exponentiations. Both protocols are noninteractive.



---

*Source: 8547876-2017-08-30.xml*