# Lightweight Noninteractive Membership Authentication and Group Key Establishment for WSNs

Authors: Qi Cheng; Chingfang Hsu; Lein Harn
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Wireless sensor networks (WSNs) exhibit their potential capacity in the next generation of mobile communication networks and wireless systems (5G). Collected data in WSNs are different from most data transmitted in digital communication applications. Most collected data in WSNs contain only few bits of information. Conventional protocols are not suitable for WSNs since this environment needs more flexible and lightweight protocols for secure group communications. Hence, how to realize the mutual secure and lightweight communication is a big challenge for WSNs. User authentication and key establishment are two fundamental security services in secure communications for WSNs. In this paper, we propose a novel design which embeds the function of membership authentication and group key establishment in WSNs. By using an asymmetric bivariate polynomial, membership authentication and pairwise shared keys distribution are realized. Then, each member mixes his/her input with pairwise shared keys with other members and releases the encrypted value in a broadcast channel. After collecting all released values, each member can compute the group key efficiently. Our proposal is noninteractive and lightweight. As it enjoys low computation and communication costs compared with the state-of-the-art cryptographic solutions, this design is more suitable for efficient membership authentication and group key establishment in WSNs.


---

## Body

## 1. Introduction

Wireless Sensor Networks (WSNs) have been developed to collect data remotely for various applications [1, 2]. For example, data have been collected for traffic analysis, weather prediction, and medical analysis, etc. [3, 4]. For security reason, the collected data need to be protected from eavesdropping. Data encryption requires that both the source node and the receiver node share a pairwise shared key. The source node encrypts the collected data under the shared key, and the receiver node decrypts the ciphertext under the shared key to recover the data.In general, security research studies in WSNs are focused on the development of key establishment and key management solutions. Random key predistribution schemes [5–7] have been developed to allow two sensors to establish a shared key. The random key distribution is a probabilistic scheme and does not guarantee connectivity in WSNs. Each sensor is preloaded with k keys randomly selected from a large pool of keys. Blom [8] proposed the first pairwise key establishment scheme based on threshold cryptography. This approach is a deterministic scheme which can guarantee connectivity in WSNs. Blundo et al. [9] have discussed the key establishment using polynomials. Khan et al. [10] proposed a predistribution scheme using a symmetric matrix and a generator matrix of maximum rank distance to establish pairwise keys for sensor nodes. Group key distribution based on bivariate polynomials [11–14] has also been developed to allow a group of sensors to establish a shared key deterministically. The design of WSNs has been classified into two types: flat and hierarchical. In flat WSNs, all sensors have the same capabilities to collect data and forward data to other sensors in the network. In hierarchical WSNs, devices are organized into a hierarchy based on their capabilities. The key management protocols in WSNs have also been proposed according to two different types: flat and hierarchical.Collected data in WSNs are different from most data in digital communication applications. Most collected data, for example, weather/traffic data, in WSNs contain only few bits of information. Conventional protocols are not suitable for WSNs since WSNs need more fast and lightweight protocols for secure group communications.User authentication and key establishment are two fundamental security services in secure communications for WSNs. 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.In general, key distribution schemes can be classified into two types: centralized key distribution schemes (CKDs) and distributed key distribution schemes (DKDs). In CKDS, the key distribution is served by using a server. During registration, each user needs to share a secret key with the authentication server. Then, later, a one-time session key is determined by the server and is encrypted with the preshared key. The ciphertext is sent to each user in a one-to-one communication. This type of key distribution is very efficient, and the security is based on a trusted server. There are many practical network security schemes which use this type of key distribution, for example, the Kerberos [15] and IEEE 802.11 [16]. In DKDs, the key distribution is performed by all users. Every user needs to interact with every other user to finally determine a one-time session key which is only known to all participated users. Diffie–Hellman public-key distribution scheme [17] is one of the most well-known DKD. Many research papers [18, 19] have proposed schemes in the literature which belong to this type of key distribution schemes. In DKD, there is no centralized trust and there are more interactions among users.Most traditional communications are one-to-one type of communications. The majority of key distribution schemes focus on developing ways to establish a pairwise shared key between two users. Modern communications are no longer interested in one-to-one type of communication but in one-to-many type of communications, such as multicast or conference, in which a group key needs to be established among all users. Diffie–Hellman public-key distribution scheme [17] invented in 1976 only works to establish a pairwise shared key between two users. But, Diffie–Hellman key distribution scheme only works for two users. There are many research papers [18, 19] to extend the original Diffie–Hellman scheme to establish a group key. In 2004, Joux [20] devised a simple three-party Diffie–Hellman group key exchange scheme based on bilinear pairings. Pairing-based cryptography is the use of a pairing between elements of two cryptographic groups and a third group with a mapping. By utilization of the extended Chebyshev chaotic maps, Abbasinezhad-Mood and Nikooghadam [21] proposed an anonymous password-authenticated key exchange protocol. In 1992, Blundo et al. [9] proposed a noninteractive k-secure m-conference scheme based on a multivariate polynomial. Their scheme can establish a conference key of m participants. The storage space of each user is exponentially proportional to the size of conference. This makes their scheme impractical for a group with large size. Laih et al. [22] proposed the first group key distribution scheme based on the secret-sharing scheme. During registration, each group member obtains a token from the group manager. The group manager can distribute a group key to all participated members in broadcasting transmission. There are many published papers based on this approach [23, 24].In this paper, we propose a novel design which embeds the function of membership authentication and group key establishment. We present this efficient lightweight membership authentication and group key establishment based on an asymmetric bivariate polynomial and the logic Exclusive (XOR) operation function. During registration, each member will receive a “token” from the membership registration center (MRC). Tokens are generated by an asymmetric bivariate polynomial, and each token is a univariate polynomial. Each member uses the token for membership authentication, pairwise shared key establishment. Then, by using the logic Exclusive (XOR) operation function, each member mixes his/her input with pairwise shared secrets with other users and uses his/her pairwise shared keys to encrypt the computed value and then sends this value to other members. After collecting all values from other members, each member can compute the group key. This proposed lightweight scheme is especially suitable for WSNs.In summary, we list the contributions of this paper as follows:(i)
An efficient lightweight membership authentication and group key establishment for WSNs is proposed.(ii)
Tokens generated by an asymmetric bivariate polynomial initially can be used for membership authentication and pairwise shared key establishment.(iii)
Our proposed approach is very efficient since there is no need for additional membership authentication and pairwise shared key establishment.(iv)
Our protocol is secure against inside attackers and outside attackers. Furthermore, confidentiality, authentication, freshness, forward secrecy, and backward secrecy of group key can be achieved.(v)
One unique feature of our group key establishment is that the XOR operation is the main computation, so it is lightweight.The organization of this paper is as follows. In Section2, we provide some preliminaries about bivariate polynomials. In Section 3, we present the model of our protocols including the protocol description, types of adversaries, and security properties of our proposed protocol. Our proposed protocol including three parts (a) token generation, (b) membership authentication, and (c) group key establishment is given in Section 4. In Section 5, we analyze the security and performance of this protocol. The conclusion is given in Section 5.


## 2. Preliminaries

In Shamir’st,n SS [25], the dealer selects a univariate polynomial, fx, with degree t−1 and f0=s, where s is the secret. The dealer generates 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, Ui. Each share, fxi, is an integer in GFp. Shamir’s t,n SS satisfies security requirements of a t,n SS, that is, (a) with t or more than t shares can reconstruct the secret and (b) with fewer than t shares cannot obtain any information of the secret. Shamir’s SS is unconditionally secure.In Shamir’st,n SS, shareholders cannot verify the validity of their shares obtained from the dealer. In 1985, Chor et al. [26] extended the notion of SS and proposed the first verifiable secret sharing (VSS). Verifiability is the property of a VSS which allows shareholders to verify their shares. Invalid shares may be caused either by the dealer during share generation or by channel noise during transmission. VSS is performed by shareholders after receiving their shares from the dealer and before using their shares to reconstruct the secret. If invalid shares have been detected, shareholders can request the dealer to regenerate new shares. There are many t,n VSSs [27–32] using bivariate polynomials, denoted as BVSSs. A bivariate polynomial with degree t−1 can be represented as Fx,y=∑i=0t−1∑j=0t−1ai,jxiyjmodp, where ai,j∈GFp. We can classify BVSSs into two types, the symmetric BVSSs, denoted as SBVSSs [28, 30, 32], and the asymmetric BVSSs, denoted as ABVSSs, [27, 29, 31]. If the coefficients satisfy ai,j=aj,i,∀i,j∈0,t−1, it is a symmetric bivariate polynomial. Shares generated by a bivariate polynomial can be used to establish pairwise keys between any pair of shareholders. In all t,n SBVSSs, the dealer selects a bivariate polynomial, Fx,y, with degree t−1, and F0,0=s, where s is the secret. The dealer generates shares, Fxi,ymodp,i=1,2,…,n, for shareholders, where p is a prime with p>s and xi is the public information associated with each shareholder, Ui. Each share, Fxi,y, is a univariate polynomial with degree t−1. Note that shares generated in a SBVSS satisfy Fxi,xj=Fxj,xi,∀i,j∈0,t−1, and the pairwise key, Fxi,xj=Fxj,xi, can be established between the pair of shareholders, Ui and Uj. In a similar way, in a ABVSS, the dealer generates a pair of shares, Fxi,ymodp and Fx,ximodp,i=1,2,…,n, for each shareholder, and the pairwise secret key, Fxi,xj or Fxj,xi, can also be established between the pair of shareholders, Ui and Uj.In this paper, we propose a novel design of efficient lightweight membership authentication and group key establishment for WSNs. Our design integrates solutions of membership authentication, pairwise shared key establishment, and group key establishment together. In other words, we propose to use a bivariate polynomial to generate tokens. Tokens of members obtained during registration can be used for (a) membership authentication; (b) pairwise shared keys distribution; and (c) group key establishment. However, most of the existing cryptographic solutions need additional membership authentication and shared keys distribution and also need interactive communications or complex computations for encryption and decryption [33–36].


## 3. Model of Our Proposed Protocol

In this section, we describe the model of our proposed membership authentication and group key agreement protocol for WSNs including the network model and security model, which provide the type of adversaries and security features.


### 3.1. Protocol Description for the Network Model

Without loss of generality, suppose that there has a mutually trusted membership registration center (MRC) and there aren users U1,U2,…,Un, involved in group communications. Each user is required to register at MRC, and MRC manages all registered users which includes removing any unsubscribed users or adding new users. In order to achieve secure communications, each group’s session key is needed to be securely distributed to all corresponding group members in prior of exchanging messages. Typically, if all participants are members and act honestly, the protocol is successful; i.e., only the members belonging to the same group can derive this group’s session key. Otherwise, it fails, i.e., group members obtain nothing. Thus, membership authentication before the group key establishment is necessary.In our proposed protocol, each user needs to register at the MRC initially and obtain secret token. The MRC selects an asymmetric bivariate polynomial and generates tokens. Token of each user is two univariate polynomials: one ist−1 degree in x and the other one is h−1 degree in y.In order to establish a secure group communication involvingm (i.e., 2≤m<n) members, it requires to execute a membership authentication first in which all participated users interact with each other to prove that they belong to the same group. In the membership authentication, each member needs to broadcast a random integer. After receiving all random integers, each member needs to use his secret tokens to compute pairwise shared keys and then compute a hash output as his authentication response. Members can use this authentication response to authenticate his membership. This membership authentication can also identify nonmembers. At the end of membership authentication, each member knows exactly the memberships of users participated in the secure group communication. Then, by using XOR operation function, each member mixes his/her input with pairwise shared keys and, after that, uses his/her pairwise shared keys to encrypt the computed value, and next, sends this value to other members. After collecting all values from other members, each member can compute the group key; that is, a secret group session key is obtained by each member individually. There is no interaction with other members to compute the group key. Thus, our proposed protocol is very efficient in both membership authentication and group key establishment since there is only broadcast transmission. Furthermore, the computation of each member needs only polynomial evaluation, XOR computation, and hash function which are much faster than most public-key computations. We will give detail discussion for its performance evaluation in Section 5.


### 3.2. Security Model

Now, we introduce the security model which include the type of adversaries and the required security features for secure group communication. These security requirements will be analyzed in Section5.


#### 3.2.1. Type of Adversaries

We consider two types of attacks: inside and outside attacks. The inside attackers are legitimate members who have obtained valid tokens from MRC initially. From inside attack, colluded members try to recover the MRC’s secret polynomial used to generate tokens for members and then use these uncovered tokens to obtain group keys which they are not authorized to access. On the other hand, the outside attackers are illegitimate members who try to generate valid tokens of members and use them to impersonate members in a secure group communication or to recover secret group keys which they are not authorized to access. In Section5, we will give the detailed security analysis about these two types of attackers.


#### 3.2.2. Security Features

For secure group communication, the group key establishment protocol needs to have the following security features.(a)
Correctness: the protocol can successfully authenticate memberships of all participated users and then establish a secret group key among all members.(b)
Freshness of authentication response: the authentication responses generated by members in the membership authentication can only be used for one time. This feature can prevent replay attack in which attackers replay recorded authentication response to fail the membership authentication.(c)
Freshness of group keys: the secret group key generated by members in the key establishment can only be used for one time communication. This feature can prevent attackers to reuse previously compromised group keys to gain access to other secure communications.(d)
Freshness of the group key authentication: recording a previously used authentication cannot impersonate a member since this random integer is different in every session.(e)
Forward secrecy of group keys: the forward secrecy is ensured if a departing member cannot access the content of communications of any future group session.(f)
Backward secrecy of group keys: the backward secrecy is ensured if a new member cannot access the content of communications of any past session.


## 3.1. Protocol Description for the Network Model

Without loss of generality, suppose that there has a mutually trusted membership registration center (MRC) and there aren users U1,U2,…,Un, involved in group communications. Each user is required to register at MRC, and MRC manages all registered users which includes removing any unsubscribed users or adding new users. In order to achieve secure communications, each group’s session key is needed to be securely distributed to all corresponding group members in prior of exchanging messages. Typically, if all participants are members and act honestly, the protocol is successful; i.e., only the members belonging to the same group can derive this group’s session key. Otherwise, it fails, i.e., group members obtain nothing. Thus, membership authentication before the group key establishment is necessary.In our proposed protocol, each user needs to register at the MRC initially and obtain secret token. The MRC selects an asymmetric bivariate polynomial and generates tokens. Token of each user is two univariate polynomials: one ist−1 degree in x and the other one is h−1 degree in y.In order to establish a secure group communication involvingm (i.e., 2≤m<n) members, it requires to execute a membership authentication first in which all participated users interact with each other to prove that they belong to the same group. In the membership authentication, each member needs to broadcast a random integer. After receiving all random integers, each member needs to use his secret tokens to compute pairwise shared keys and then compute a hash output as his authentication response. Members can use this authentication response to authenticate his membership. This membership authentication can also identify nonmembers. At the end of membership authentication, each member knows exactly the memberships of users participated in the secure group communication. Then, by using XOR operation function, each member mixes his/her input with pairwise shared keys and, after that, uses his/her pairwise shared keys to encrypt the computed value, and next, sends this value to other members. After collecting all values from other members, each member can compute the group key; that is, a secret group session key is obtained by each member individually. There is no interaction with other members to compute the group key. Thus, our proposed protocol is very efficient in both membership authentication and group key establishment since there is only broadcast transmission. Furthermore, the computation of each member needs only polynomial evaluation, XOR computation, and hash function which are much faster than most public-key computations. We will give detail discussion for its performance evaluation in Section 5.


## 3.2. Security Model

Now, we introduce the security model which include the type of adversaries and the required security features for secure group communication. These security requirements will be analyzed in Section5.


### 3.2.1. Type of Adversaries

We consider two types of attacks: inside and outside attacks. The inside attackers are legitimate members who have obtained valid tokens from MRC initially. From inside attack, colluded members try to recover the MRC’s secret polynomial used to generate tokens for members and then use these uncovered tokens to obtain group keys which they are not authorized to access. On the other hand, the outside attackers are illegitimate members who try to generate valid tokens of members and use them to impersonate members in a secure group communication or to recover secret group keys which they are not authorized to access. In Section5, we will give the detailed security analysis about these two types of attackers.


### 3.2.2. Security Features

For secure group communication, the group key establishment protocol needs to have the following security features.(a)
Correctness: the protocol can successfully authenticate memberships of all participated users and then establish a secret group key among all members.(b)
Freshness of authentication response: the authentication responses generated by members in the membership authentication can only be used for one time. This feature can prevent replay attack in which attackers replay recorded authentication response to fail the membership authentication.(c)
Freshness of group keys: the secret group key generated by members in the key establishment can only be used for one time communication. This feature can prevent attackers to reuse previously compromised group keys to gain access to other secure communications.(d)
Freshness of the group key authentication: recording a previously used authentication cannot impersonate a member since this random integer is different in every session.(e)
Forward secrecy of group keys: the forward secrecy is ensured if a departing member cannot access the content of communications of any future group session.(f)
Backward secrecy of group keys: the backward secrecy is ensured if a new member cannot access the content of communications of any past session.


## 3.2.1. Type of Adversaries

We consider two types of attacks: inside and outside attacks. The inside attackers are legitimate members who have obtained valid tokens from MRC initially. From inside attack, colluded members try to recover the MRC’s secret polynomial used to generate tokens for members and then use these uncovered tokens to obtain group keys which they are not authorized to access. On the other hand, the outside attackers are illegitimate members who try to generate valid tokens of members and use them to impersonate members in a secure group communication or to recover secret group keys which they are not authorized to access. In Section5, we will give the detailed security analysis about these two types of attackers.


## 3.2.2. Security Features

For secure group communication, the group key establishment protocol needs to have the following security features.(a)
Correctness: the protocol can successfully authenticate memberships of all participated users and then establish a secret group key among all members.(b)
Freshness of authentication response: the authentication responses generated by members in the membership authentication can only be used for one time. This feature can prevent replay attack in which attackers replay recorded authentication response to fail the membership authentication.(c)
Freshness of group keys: the secret group key generated by members in the key establishment can only be used for one time communication. This feature can prevent attackers to reuse previously compromised group keys to gain access to other secure communications.(d)
Freshness of the group key authentication: recording a previously used authentication cannot impersonate a member since this random integer is different in every session.(e)
Forward secrecy of group keys: the forward secrecy is ensured if a departing member cannot access the content of communications of any future group session.(f)
Backward secrecy of group keys: the backward secrecy is ensured if a new member cannot access the content of communications of any past session.


## 4. Our Proposed Protocol

In this section, we present a membership authentication and group key establishment protocol using an asymmetric bivariate polynomial and XOR operation function. The protocol is described in Algorithm1. There are three phases in our protocol, i.e., token generation, membership authentication, group key establishment, and authentication. For every phase, we give the illustrative figure, respectively, in Figures 1–3.Algorithm 1: Membership authentication and group key establishment.
Token generationForn users U1,U2,…,Un, the MRC selects a random asymmetric polynomial, Fx,y=a0,0+a1,0x+a0,1y+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+…++at−1,h−1xt−1yh−1modp, where Fx,y is t−1 degree in x and h−1 degree (i.e., h>2t−2). We will prove this condition in Theorem 1 in y, ai,j∈GFp,∀i∈0,t−1,∀j∈0,h−1, and p is a prime integer with p>n. The MRC computes a pair of shares, siy=Fxi,y and six=Fx,xi, for each user, Ui,i=1,2,…,n, where xi∉0,1 is the public information associated with each user, Ui. The MRC sends each pair of shares as Ui’s token, siy,six, to user Ui through the secure channel.Membership authenticationWe assume thatm (i.e., 2≤m<n) users, for example Uv1,Uv2,…,Uvm, want to engage in a group key establishment in WSNs.Step 1. Each member Uvi broadcasts a random integer, ri∈GFp to all other members, where i=1,2,…,m.Step 2. Assume that the value Fxvi,xvj, with xvi<xvj, is used as the pairwise shared key between the shareholders Uvi and Uvj. Each member Uvi uses one of shares of his token, sviy or svix, to compute pairwise shared keys, ki,j=svixvj=Fxvi,xvj,j=1,2,…,m,j≠i, between any other users, where ki,j is the secret key shared between users, Uvi and Uvj.Step 3. Each member Uvi computes authentication responses, Authi,j=hki,jrj,j=1,2,…,m,j≠i, where hki,jrj is a one-way hash output with ki,j and rj as inputs. Each Authi,j is sent to member Uvj publicly for authentication.Step 4. After receiving Authi,j=hki,jrj, from member Uvi, the member Uvj uses his computed pairwise shared key, ki,j=svixvj=Fxvi,xvj, in Step 2 to compute hki,jrj and check whether Authi,j=hki,jrj. If the checking is successful, member Uvi has been authenticated; otherwise, member Uvi has not been authenticated. Repeat this process for all other members Uvi,i=1,2,…,m,i≠j.Group key establishment and authenticationLet us assume that at the end of membership authentication, allm members, Uv1,Uv2,…,Uvm have been successfully authenticated. Then, members follow an XOR operation algorithm to complete the group key establishment process. However, all exchange information among members is encrypted under the pairwise shared keys, ki,j, j=1,2,…,m,j≠i, in the Step 2 of membership authentication.Step 1. Each member Uvi needs to select a secret input si∈GFp and broadcasts a random integer, li∈GFp to all other members, where i=1,2,…,m.Step 2. Each member Uvi uses his pairwise shared keys with other members to compute qvi.=si⊕ki,1⊕ki,2⊕⋯⊕ki,j⊕⋯⊕ki,mmodp,j=1,2,…,m,j≠i,where⊕is the XOR operation.Step 3. Each member Uvi uses his computed pairwise shared keys, ki,j,j=1,2,…,m,j≠i, in the Step 2 of membership authentication to encrypt qvi as ui,j=Eki,jqvi,j=1,2,…,m,j≠i. Member Uvi sends each ui,j to member Uvj.Step 4. After receiving uj,i, from other member, member Uvi uses his computed pairwise shared key, ki,j, in the Step 2 of membership authentication to decrypt as qvj.=Eki,juj.i. Repeat this process for all uj,i,j=1,2,…,m,j≠i.Step 5. After obtaining qvj.,j=1,2,…,m,j≠i, from all other members, member Uvi computes qv1.⊕qv2.⊕⋯⊕qvi.⊕⋯⊕qvm.modp=s1⊕s2.⊕⋯⊕si.⊕⋯⊕smmodp=Ki, i=1,2,…,m, where ⊕ is the XOR operation.Step 6. Each member Uvi computes and broadcasts HKiL,i=1,2,…,m, and then checks if HK1L=HK2L=⋯=HKiL=⋯=HKmLmodp, where L=∑i=1mli and HKiL is a one-way hash output with Ki and L as input s. If the checking is successful, the group key has been authenticated, Ki=K is the secret group communication key; otherwise, the group key has not been authenticated. Repeat this process for all group members Uvi,i=1,2,…,m.Figure 1
Token generation.Figure 2
Membership authentication.Figure 3
Group key establishment and authentication.


## 5. Analysis

In this section, we address the security and performance of our proposed protocol.


### 5.1. Security Analysis

In this section, we discuss security features and possible attacks of our protocol as described in Section3.2.


#### 5.1.1. Security Features

(a)
Correctness: In membership authentication, if all participated users are members as they claimed in Step 1 of membership authentication, each member,Ui, in Step 2 should be able to compute the pairwise shared key ki,j. Thus, in Step 4, the authentication response, Authi,j=hki,jrj, can be used to verify Uvi’s membership by Uvj. Nonmembers cannot forge this authentication response since nonmembers do not know the secret tokens of member, Ui. In group key establishment, the correctness of this property comes from the rule of XOR operation and qvi.=si⊕ki,1⊕ki,2⊕⋯⊕ki,j⊕⋯⊕ki,mmodp,wherej=1,2,…,m.j≠i; thus, qvi1.⊕qv2.⊕⋯⊕qvi.⊕⋯⊕qvm.modp=s1⊕s2.⊕⋯⊕si.⊕⋯⊕smmodp=Ki, i=1,2,…,m.(b)
Freshness of authentication response: in Step 3 of membership authentication, the authentication response,Authi,j=hki,jrj, is a hash output of pairwise shared key and random integer selected by participated member initially. Recording a previously used authentication response cannot impersonate a member since this random integer is different in every session.(c)
Freshness of group keys: in the group key establishment, the group key,K=s1⊕s2.⊕⋯⊕si.⊕⋯⊕smmodp, is determined by Uvi’s secret input si initially. This group key is different in every session.(d)
Freshness of the group key authentication: in Step 6 of group key establishment, the authenticationHKiL is a one-way hash output with input s group key determined by each member’s secret input si and sum of random integers selected by the participated member initially. Recording a previously used authentication cannot impersonate a member since this random integer is different in every session.(e)
Forward secrecy of group keys: if a member has departed from the group, the departed member cannot access the content of future communications since the any group key,K, can only be computed by members involved in the secure communication.(f)
Backward secrecy of group keys: if a member joins the group, the new member cannot access the content of any past communications since the any group key,K, can only be computed by members involved in the secure communication.


#### 5.1.2. Possible Attacks

Theorem 1.
(inside attack). In the proposed protocol, ifh>2t−2, it needs at least t insider attackers to work together to reconstruct the tokens. The proposed protocol can resist up to t−1 colluded members to recover the secret polynomial Fx,y of MRC.Proof.
Inside attackers are legitimate members who own valid tokens from the MRC during registration.
SinceFx,y=a0,0+a1,0x+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+…+at−1,h−1xt−1yh−1modp is an asymmetric polynomial of degree t−1 in x and h−1 degree in y, which contains th different coefficients. In the proposed scheme, each token siy,six contains two univariate polynomials with degree h−1 in y and t−1 degree in x, respectively. In other words, each user can use his token to establish t+h linearly independent equations in terms of the coefficients of the asymmetric bivariate polynomial Fx,y. When there are t−1 colluded users with their tokens together, they can establish total t+ht−1 equations. At the same time, for t−1 colluded users, there are 2C2t−1 pairwise keys. Hence, having t−1 colluded users’ shares, the total number of linearly independent equations is t+ht−1−2C2t−1. If the number of coefficients of the bivariate polynomial Fx,y is larger than the number of linearly independent equations available to the colluded users (i.e.,th>t+ht−1−2C2t−1), they cannot recover the bivariate polynomial. Hence, they cannot learn any information of the secret. From th>t+ht−1−2C2t−1, we obtain h>2t−2. Hence, if h>2t−2, it assures that t−1 colluded inside adversaries cannot recover the secret polynomial Fx,y selected by MRC initially. Thus, it needs at least t inside attackers to work together to reconstruct the tokens. The proposed protocol can resist up to t−1 colluded members to recover the secret polynomial Fx,y of MRC. According to the security level requirement, the proper values of t and h can be selected. For example, when n=t−1, all member collusions cannot recover the secret polynomial Fx,y of MRC.Theorem 2.
(outside attack). In the proposed protocol, the outside attacker cannot obtain any secret information.Proof.
Outside attackers are illegitimate users who do not own any valid tokens from MRC. The outside attackers may try to impersonate members in the group key establishment to obtain the group key. However, since in the group key establishment, all exchange information of legitimate members are encrypted using pairwise shared keys and outside attackers do not own any valid token to recover any pairwise shared key, so the outside attacker cannot obtain any secret information.


### 5.2. Performance Evaluation

Most of the latest schemes can either provide user authentication or group key establishment separately [37–40]. They need additional membership authentication and shared keys distribution and also need interactive communications and complex computations for encryption and decryption. We first discuss performance features of our protocol as follows.Compared with the existing schemes, our protocol can provide both membership authentication and group key establishment simultaneously. By using a bivariate polynomial, membership authentication and pairwise shared keys distribution are realized at the same time. Then, just by the XOR operation, each member mixes his/her input with pairwise shared keys with other members and releases the encrypted value in a broadcast channel. After collecting all released values, each member can compute the group key efficiently. In our protocol, tokens of members obtained during registration can be used for (a) membership authentication; (b) pairwise shared keys distribution; and (c) group key establishment. It is very efficient.According to the definition in most communications, “Interactive communications” means acting one upon or with the other. In our group key establishment phase, each member computes his/her own values and releases the values to others without “waiting” for other members’ inputs. In other words, each member does not need waiting time in computing and releasing values to other members. We call this property “noninteractive,” which can speed up the communication process significantly.Our proposal is noninteractive, computation-efficient, and lightweight, which has the advantages in storage, computation, and communication cost. Specific analysis is as follows.


#### 5.2.1. Storage Cost

In our protocol. each member needs to store a token,siy,six, which consists of two univariate polynomials: one is t−1 degree in x and the other one is h−1 degree in y. Thus, each shareholder needs to store t+h coefficients of a univariate polynomial. The storage requirement for each user is t+hlog2p bits, where p is the modulus. This polynomial-based modulus is far less than public-key-based modulus.


#### 5.2.2. Computation Cost

For our protocol, in Step 2 of membership authentication, when evaluating the polynomials, Horner’s rule [32] can be used to reduce the computational cost. Each shareholder needs to compute m−1 pairwise shared keys, ki,j=svixvj=Fxvi,xvj,j=1,2,…,m,j≠i, by evaluating m−1 different polynomials. Using Horner’s rule, evaluating a polynomial of degree h−1 needs h−1 multiplications and h additions. In addition, each member needs to generate one authentication response and to verify m−1 authentication responses. Since each authentication response is a hash output, each member needs to compute m hash outputs. In steps of group key establishment, there are all XOR operations, symmetric encryption, and decryption operations which is very efficient in comparing with all existing protocols. Finally, there is only computing hash function to authenticate the group session key by each member. The computation load of our proposed protocol is much simpler than most public-key based schemes. For example, the RSA [41] public-key operation requires approximately 1.5log2N modulo multiplications (i.e., in RSA, N is at least 1024 bits).


#### 5.2.3. Communication Cost

The communication of membership authentication is performed completely in the broadcast channel. The total communication time is to transmitm random integers, ri,i=1,2,…,m, and mm−1 authentication responses for all participated group members. To establish the group key, the total communication time is to transmit m random integers, li,i=1,2,…,m,mm−1-encrypted messages and m hash outputs to authenticate the group session key for all participated group members. In our protocol, all transmitted data are computed on polynomial-based modulus. Furthermore, since our protocols are noninteractive, all released values can be broadcasted simultaneously and they are very efficient.


## 5.1. Security Analysis

In this section, we discuss security features and possible attacks of our protocol as described in Section3.2.


### 5.1.1. Security Features

(a)
Correctness: In membership authentication, if all participated users are members as they claimed in Step 1 of membership authentication, each member,Ui, in Step 2 should be able to compute the pairwise shared key ki,j. Thus, in Step 4, the authentication response, Authi,j=hki,jrj, can be used to verify Uvi’s membership by Uvj. Nonmembers cannot forge this authentication response since nonmembers do not know the secret tokens of member, Ui. In group key establishment, the correctness of this property comes from the rule of XOR operation and qvi.=si⊕ki,1⊕ki,2⊕⋯⊕ki,j⊕⋯⊕ki,mmodp,wherej=1,2,…,m.j≠i; thus, qvi1.⊕qv2.⊕⋯⊕qvi.⊕⋯⊕qvm.modp=s1⊕s2.⊕⋯⊕si.⊕⋯⊕smmodp=Ki, i=1,2,…,m.(b)
Freshness of authentication response: in Step 3 of membership authentication, the authentication response,Authi,j=hki,jrj, is a hash output of pairwise shared key and random integer selected by participated member initially. Recording a previously used authentication response cannot impersonate a member since this random integer is different in every session.(c)
Freshness of group keys: in the group key establishment, the group key,K=s1⊕s2.⊕⋯⊕si.⊕⋯⊕smmodp, is determined by Uvi’s secret input si initially. This group key is different in every session.(d)
Freshness of the group key authentication: in Step 6 of group key establishment, the authenticationHKiL is a one-way hash output with input s group key determined by each member’s secret input si and sum of random integers selected by the participated member initially. Recording a previously used authentication cannot impersonate a member since this random integer is different in every session.(e)
Forward secrecy of group keys: if a member has departed from the group, the departed member cannot access the content of future communications since the any group key,K, can only be computed by members involved in the secure communication.(f)
Backward secrecy of group keys: if a member joins the group, the new member cannot access the content of any past communications since the any group key,K, can only be computed by members involved in the secure communication.


### 5.1.2. Possible Attacks

Theorem 1.
(inside attack). In the proposed protocol, ifh>2t−2, it needs at least t insider attackers to work together to reconstruct the tokens. The proposed protocol can resist up to t−1 colluded members to recover the secret polynomial Fx,y of MRC.Proof.
Inside attackers are legitimate members who own valid tokens from the MRC during registration.
SinceFx,y=a0,0+a1,0x+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+…+at−1,h−1xt−1yh−1modp is an asymmetric polynomial of degree t−1 in x and h−1 degree in y, which contains th different coefficients. In the proposed scheme, each token siy,six contains two univariate polynomials with degree h−1 in y and t−1 degree in x, respectively. In other words, each user can use his token to establish t+h linearly independent equations in terms of the coefficients of the asymmetric bivariate polynomial Fx,y. When there are t−1 colluded users with their tokens together, they can establish total t+ht−1 equations. At the same time, for t−1 colluded users, there are 2C2t−1 pairwise keys. Hence, having t−1 colluded users’ shares, the total number of linearly independent equations is t+ht−1−2C2t−1. If the number of coefficients of the bivariate polynomial Fx,y is larger than the number of linearly independent equations available to the colluded users (i.e.,th>t+ht−1−2C2t−1), they cannot recover the bivariate polynomial. Hence, they cannot learn any information of the secret. From th>t+ht−1−2C2t−1, we obtain h>2t−2. Hence, if h>2t−2, it assures that t−1 colluded inside adversaries cannot recover the secret polynomial Fx,y selected by MRC initially. Thus, it needs at least t inside attackers to work together to reconstruct the tokens. The proposed protocol can resist up to t−1 colluded members to recover the secret polynomial Fx,y of MRC. According to the security level requirement, the proper values of t and h can be selected. For example, when n=t−1, all member collusions cannot recover the secret polynomial Fx,y of MRC.Theorem 2.
(outside attack). In the proposed protocol, the outside attacker cannot obtain any secret information.Proof.
Outside attackers are illegitimate users who do not own any valid tokens from MRC. The outside attackers may try to impersonate members in the group key establishment to obtain the group key. However, since in the group key establishment, all exchange information of legitimate members are encrypted using pairwise shared keys and outside attackers do not own any valid token to recover any pairwise shared key, so the outside attacker cannot obtain any secret information.


## 5.1.1. Security Features

(a)
Correctness: In membership authentication, if all participated users are members as they claimed in Step 1 of membership authentication, each member,Ui, in Step 2 should be able to compute the pairwise shared key ki,j. Thus, in Step 4, the authentication response, Authi,j=hki,jrj, can be used to verify Uvi’s membership by Uvj. Nonmembers cannot forge this authentication response since nonmembers do not know the secret tokens of member, Ui. In group key establishment, the correctness of this property comes from the rule of XOR operation and qvi.=si⊕ki,1⊕ki,2⊕⋯⊕ki,j⊕⋯⊕ki,mmodp,wherej=1,2,…,m.j≠i; thus, qvi1.⊕qv2.⊕⋯⊕qvi.⊕⋯⊕qvm.modp=s1⊕s2.⊕⋯⊕si.⊕⋯⊕smmodp=Ki, i=1,2,…,m.(b)
Freshness of authentication response: in Step 3 of membership authentication, the authentication response,Authi,j=hki,jrj, is a hash output of pairwise shared key and random integer selected by participated member initially. Recording a previously used authentication response cannot impersonate a member since this random integer is different in every session.(c)
Freshness of group keys: in the group key establishment, the group key,K=s1⊕s2.⊕⋯⊕si.⊕⋯⊕smmodp, is determined by Uvi’s secret input si initially. This group key is different in every session.(d)
Freshness of the group key authentication: in Step 6 of group key establishment, the authenticationHKiL is a one-way hash output with input s group key determined by each member’s secret input si and sum of random integers selected by the participated member initially. Recording a previously used authentication cannot impersonate a member since this random integer is different in every session.(e)
Forward secrecy of group keys: if a member has departed from the group, the departed member cannot access the content of future communications since the any group key,K, can only be computed by members involved in the secure communication.(f)
Backward secrecy of group keys: if a member joins the group, the new member cannot access the content of any past communications since the any group key,K, can only be computed by members involved in the secure communication.


## 5.1.2. Possible Attacks

Theorem 1.
(inside attack). In the proposed protocol, ifh>2t−2, it needs at least t insider attackers to work together to reconstruct the tokens. The proposed protocol can resist up to t−1 colluded members to recover the secret polynomial Fx,y of MRC.Proof.
Inside attackers are legitimate members who own valid tokens from the MRC during registration.
SinceFx,y=a0,0+a1,0x+a1,1xy+a2,0x2+a0,2y2+a1,2xy2+a2,1x2y+a2,2x2y2+…+at−1,h−1xt−1yh−1modp is an asymmetric polynomial of degree t−1 in x and h−1 degree in y, which contains th different coefficients. In the proposed scheme, each token siy,six contains two univariate polynomials with degree h−1 in y and t−1 degree in x, respectively. In other words, each user can use his token to establish t+h linearly independent equations in terms of the coefficients of the asymmetric bivariate polynomial Fx,y. When there are t−1 colluded users with their tokens together, they can establish total t+ht−1 equations. At the same time, for t−1 colluded users, there are 2C2t−1 pairwise keys. Hence, having t−1 colluded users’ shares, the total number of linearly independent equations is t+ht−1−2C2t−1. If the number of coefficients of the bivariate polynomial Fx,y is larger than the number of linearly independent equations available to the colluded users (i.e.,th>t+ht−1−2C2t−1), they cannot recover the bivariate polynomial. Hence, they cannot learn any information of the secret. From th>t+ht−1−2C2t−1, we obtain h>2t−2. Hence, if h>2t−2, it assures that t−1 colluded inside adversaries cannot recover the secret polynomial Fx,y selected by MRC initially. Thus, it needs at least t inside attackers to work together to reconstruct the tokens. The proposed protocol can resist up to t−1 colluded members to recover the secret polynomial Fx,y of MRC. According to the security level requirement, the proper values of t and h can be selected. For example, when n=t−1, all member collusions cannot recover the secret polynomial Fx,y of MRC.Theorem 2.
(outside attack). In the proposed protocol, the outside attacker cannot obtain any secret information.Proof.
Outside attackers are illegitimate users who do not own any valid tokens from MRC. The outside attackers may try to impersonate members in the group key establishment to obtain the group key. However, since in the group key establishment, all exchange information of legitimate members are encrypted using pairwise shared keys and outside attackers do not own any valid token to recover any pairwise shared key, so the outside attacker cannot obtain any secret information.


## 5.2. Performance Evaluation

Most of the latest schemes can either provide user authentication or group key establishment separately [37–40]. They need additional membership authentication and shared keys distribution and also need interactive communications and complex computations for encryption and decryption. We first discuss performance features of our protocol as follows.Compared with the existing schemes, our protocol can provide both membership authentication and group key establishment simultaneously. By using a bivariate polynomial, membership authentication and pairwise shared keys distribution are realized at the same time. Then, just by the XOR operation, each member mixes his/her input with pairwise shared keys with other members and releases the encrypted value in a broadcast channel. After collecting all released values, each member can compute the group key efficiently. In our protocol, tokens of members obtained during registration can be used for (a) membership authentication; (b) pairwise shared keys distribution; and (c) group key establishment. It is very efficient.According to the definition in most communications, “Interactive communications” means acting one upon or with the other. In our group key establishment phase, each member computes his/her own values and releases the values to others without “waiting” for other members’ inputs. In other words, each member does not need waiting time in computing and releasing values to other members. We call this property “noninteractive,” which can speed up the communication process significantly.Our proposal is noninteractive, computation-efficient, and lightweight, which has the advantages in storage, computation, and communication cost. Specific analysis is as follows.


### 5.2.1. Storage Cost

In our protocol. each member needs to store a token,siy,six, which consists of two univariate polynomials: one is t−1 degree in x and the other one is h−1 degree in y. Thus, each shareholder needs to store t+h coefficients of a univariate polynomial. The storage requirement for each user is t+hlog2p bits, where p is the modulus. This polynomial-based modulus is far less than public-key-based modulus.


### 5.2.2. Computation Cost

For our protocol, in Step 2 of membership authentication, when evaluating the polynomials, Horner’s rule [32] can be used to reduce the computational cost. Each shareholder needs to compute m−1 pairwise shared keys, ki,j=svixvj=Fxvi,xvj,j=1,2,…,m,j≠i, by evaluating m−1 different polynomials. Using Horner’s rule, evaluating a polynomial of degree h−1 needs h−1 multiplications and h additions. In addition, each member needs to generate one authentication response and to verify m−1 authentication responses. Since each authentication response is a hash output, each member needs to compute m hash outputs. In steps of group key establishment, there are all XOR operations, symmetric encryption, and decryption operations which is very efficient in comparing with all existing protocols. Finally, there is only computing hash function to authenticate the group session key by each member. The computation load of our proposed protocol is much simpler than most public-key based schemes. For example, the RSA [41] public-key operation requires approximately 1.5log2N modulo multiplications (i.e., in RSA, N is at least 1024 bits).


### 5.2.3. Communication Cost

The communication of membership authentication is performed completely in the broadcast channel. The total communication time is to transmitm random integers, ri,i=1,2,…,m, and mm−1 authentication responses for all participated group members. To establish the group key, the total communication time is to transmit m random integers, li,i=1,2,…,m,mm−1-encrypted messages and m hash outputs to authenticate the group session key for all participated group members. In our protocol, all transmitted data are computed on polynomial-based modulus. Furthermore, since our protocols are noninteractive, all released values can be broadcasted simultaneously and they are very efficient.


## 5.2.1. Storage Cost

In our protocol. each member needs to store a token,siy,six, which consists of two univariate polynomials: one is t−1 degree in x and the other one is h−1 degree in y. Thus, each shareholder needs to store t+h coefficients of a univariate polynomial. The storage requirement for each user is t+hlog2p bits, where p is the modulus. This polynomial-based modulus is far less than public-key-based modulus.


## 5.2.2. Computation Cost

For our protocol, in Step 2 of membership authentication, when evaluating the polynomials, Horner’s rule [32] can be used to reduce the computational cost. Each shareholder needs to compute m−1 pairwise shared keys, ki,j=svixvj=Fxvi,xvj,j=1,2,…,m,j≠i, by evaluating m−1 different polynomials. Using Horner’s rule, evaluating a polynomial of degree h−1 needs h−1 multiplications and h additions. In addition, each member needs to generate one authentication response and to verify m−1 authentication responses. Since each authentication response is a hash output, each member needs to compute m hash outputs. In steps of group key establishment, there are all XOR operations, symmetric encryption, and decryption operations which is very efficient in comparing with all existing protocols. Finally, there is only computing hash function to authenticate the group session key by each member. The computation load of our proposed protocol is much simpler than most public-key based schemes. For example, the RSA [41] public-key operation requires approximately 1.5log2N modulo multiplications (i.e., in RSA, N is at least 1024 bits).


## 5.2.3. Communication Cost

The communication of membership authentication is performed completely in the broadcast channel. The total communication time is to transmitm random integers, ri,i=1,2,…,m, and mm−1 authentication responses for all participated group members. To establish the group key, the total communication time is to transmit m random integers, li,i=1,2,…,m,mm−1-encrypted messages and m hash outputs to authenticate the group session key for all participated group members. In our protocol, all transmitted data are computed on polynomial-based modulus. Furthermore, since our protocols are noninteractive, all released values can be broadcasted simultaneously and they are very efficient.


## 6. Conclusion

We have proposed a novel design of lightweight membership authentication and group key establishment protocol for WSNs. Our protocol provides both membership authentication and group key establishment simultaneously. However, all existing schemes can provide membership authentication and key establishment separately. We have included the security analysis and performance evaluation in the paper. Our protocol is very efficient in terms of computation and communication, so it is absolutely attractive for secure group communications in WSNs.



---

*Source: 1452546-2020-05-16.xml*