# Practical KGC-Free Polynomial-Based Multiple Group Keys Agreement for IoT Health Care Systems

Authors: Qi Cheng; Zhuo Zhao; Chingfang Hsu; Maoyuan Zhang; Qing Yang; Di Wu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Although nowadays lots of group key agreement schemes have been presented, most of these protocols generate a secret key for a single group. However, in the IoT HCS, more and more communications are involved in multiple groups and users can join multiple groups to communicate at the same time. Therefore, applying the conventional public-key-based one-at-a-time group key establishment protocols has heavy computational cost or suffer from security vulnerabilities. At the same time, in an IoT HCS, a trusted KGC is usually not available and so more flexible self-organized multigroup keys generation will be desired by all group members. In order to address this issue, a practical scheme for efficient and flexible KGC-free polynomial-based multigroup key establishments for IoT HCS is proposed. The proposed protocol can generate multiple group keys for all group members at once, instead of generating one key each time for a single group; more importantly, there is no need for a trusted KGC in the process of group keys establishment and each user can join multiple groups at the same time using only one reserved share. Meanwhile, the security of the proposed protocol is discussed in detail. Finally, we compare this protocol with the latest related group key distribution protocols in performance analysis. The results show that this efficient and flexible KGC-free polynomial-based multiple group keys establishment protocol is more suitable for practical group key agreement in IoT HCS.


---

## Body

## 1. Introduction

The widespread application of the Internet of Things (IoT) brings great opportunities to the health care system (HCS). The IoT-based HCS provides enormous convenience for group communication among doctors, patients, paramedics, ambulances, and hospitals. The healthcare system can transmit the medical information collected by the internal equipment to multiple members in the group. Since medical information involves the life safety of patients, ensuring the safety of personal health information is crucial [1–6]. HCS is mainly responsible for collecting patient’s health information and transmitting this information to group members in the system through the access point. When information is transmitted on the network, it is vulnerable to malicious attacks such as eavesdropping, tampering, and replay. It is possible that the adversary performs malicious attacks and manipulates the information transmitted on the network, which will threaten the lives of patients. The sensitivity of medical data brings many privacy and security issues to the IoT-based HCS. For example, an adversary may eavesdrop on medical information transmitted on the network [7–10]; an adversary may destroy the key used to encrypt data. Hence, it is essential to protect the security of medical data. Only when safety is guaranteed can the hospital provide better services to patients. Then, it is necessary to provide security services for the IoT-based HCS to resist various attacks. For data security, the source node and target node need to share a key before communicating. This process is called key distribution or establishment in IoT-based HCS. It is worth noting that these nodes have small memory space, slow operation speed, and limited battery power. Therefore, a lightweight key distribution protocol needs to be designed for the IoT-based HCS.The asymmetric cryptographic schemes (e.g., RSA [11]) are impractically used in IoT HCS due to node’s inherit characteristics such as limited memory, power, and CPU [12, 13]. There are many methods that can be used to design a secure key distribution protocol for the IoT-based HCS. One way is to use a master key to preload all nodes, which has the advantages of low memory consumption and no communication/computing overhead. Unfortunately, this method cannot resist node capture attacks because all nodes are preloaded with the same key. Once one node is captured, the entire network may be in danger. Another method is to use the paired key shared between the two nodes to preload each node, where each node needs to store the paired keys shared with other nodes. Obviously, this method is able to withstand the node capture attack, but the storage space of the node will increase linearly with the increase of the network size. Therefore, it is impractical to apply this method to large networks.In recent years, memory consumption, computing and communication efficiency, connectivity, and robustness to node capture attacks have been focused on by key distribution protocols. At the same time, as an important part of group-based services, in IoT HCS, it is important to ensure secure communication between all group members through the group key. This goal can be achieved through the key establishment protocol. Secret sharing (SS) is computational complexity based on polynomials and unconditional security. Due to its special advantage, it becomes a very popular tool to design group key establishment protocols and then many types of SS are proposed, such as dynamic threshold SS [14]. A linear secret sharing scheme is designed by Hsu et al. [15] using Vandermonde Matrix to effectively generate the group key. Recently, by using an asymmetric bivariate polynomial, [16] proposed a lightweight construction, which realizes both the verification of membership and the establishment of group key. At the same time, lots of group key establishment protocols based on public key cryptography methods have been presented. However, most of these protocols [17–21] are the same as the above two protocols [15, 16], only one key can be generated at a time for a single group.Group-oriented communication services have attracted widespread attention, and it is increasingly being used in HCS based on the IoT, enabling users to join multiple groups at the same time to facilitate communication. At present, the application of multigroup communication in HCS based on the IoT faces two important issues of security and privacy. In order to meet the challenge, we study how to establish efficient and secure multigroup keys for many-to-many group communication in HCS based on the IoT. The traditional group key agreement protocol can be used in a straightforward way to establish multiple group keys. But in this protocol, if users frequently leave or join group communication, the system needs to constantly regenerate new group keys, which greatly increases the overhead. Hence, the traditional group key agreement protocol has the disadvantage of higher computational cost, and it is not suitable for IoT HCS. More importantly, in an IoT HCS, a trusted KGC is usually not available, then self-organized KGC-free multiple group keys generation will be more desired by all group members.To solve this problem, an efficient and flexible polynomial-based self-organized one-time multiple group keys establishment scheme for IoT HCS is presented in this paper. This scheme does not need to distribute a separate group key for each group once at a time and can generate multiple group keys for all group members at one time. In addition, there is no need for a trusted KGC in the process of group keys establishment. Each user uses only one share reserved to join multiple groups at the same time. We define it as self-organize one-time multiple group keys establishment method. Meanwhile, the security properties of our scheme are analyzed in detail. Finally, comparing the performance of our protocol with the latest public-key-based group key establishment protocol, the results show that in IoT HCS our scheme has the advantages of high efficiency and practicality.Our main contributions are summarized as follows:(a)
We design a polynomial-based self-organize multiple group keys establishment protocol for IoT HCS, in which there is no need for a trusted KGC in the process of group keys establishment, and multigroup keys generation will be performed by all involved group members.(b)
Our method is very efficient since in this protocol each user can join multiple groups at the same time using only one share reserved. There has no rekeying overhead.(c)
One unique feature of our design is that in this protocol the multigroup keys generation is performed by all group members. There is no need to set up a trusted server. It is very flexible for IoT HCS. Moreover, the polynomial is much more efficient than public key calculations. It is truly low computation.The rest of this paper is arranged as follows. Some related work of the key agreement schemes is discussed in Section2. Section 3 introduces some essential preliminaries. The model of the proposed protocol is briefly introduced in Section 4. Section 5 presents our polynomial-based self-organize multiple group keys establishment protocol. The correctness and the security are proven in Section 6. Section 7 evaluates the performance of our scheme and makes comparisons between our protocol and latest protocol. At last, we make a summary for this paper in Section 8.


## 2. Related Work

For HCS based on the IoT, more and more key establishment protocols are proposed [22–30]. Most schemes are implemented in a flat structure and establish a separate key for each group once a time. The following methods are more used in group key agreement schemes, namely random-key predistribution [31], polynomial-based predistribution [32], and grid-based predistribution [33]. The first random key protocol was designed by Eschenauer and Gligor [31]. This scheme first randomly selects a key set from the key space, namely the key pool. Before being deployed, each sensor node randomly selects a subset from the key pool, called a key ring, and stores it in its own memory. Sensor nodes must look for public keys in their respective key rings before communicating with other nodes. If there is a public key, it will be used as a shared key for both parties to communicate. On the contrary, it is necessary to find a neighbor node that has a public key with both parties in the communication. The random key scheme is a probabilistic scheme. In other words, sensor nodes can only establish a shared key with a certain probability, and it cannot ensure that there is a shared key between all nodes. This requires increasing the size of the key ring of the sensor node to increase the probability of establishing a shared key between nodes. But it will also increase the success rate of node capture attacks. Hence, it is necessary to weigh the advantages and disadvantages between network connections and node capture attacks. The key distribution scheme using polynomials is deterministic, which means that there is a shared key between any two nodes. Suppose that the proposed scheme uses a t−1 degree polynomial to establish the shared key for the node, if the number of nodes captured by the adversary is t or more than t, it will pose a threat to the entire network. For the purpose of improving the security of the scheme, the degree of the polynomial needs to be increased, but this makes the storage and calculation overhead of the nodes larger. Therefore, our intention is to design a multigroup key distribution protocol, which has the advantages of high efficiency and high security simultaneously.A new key management protocol was proposed by Park et al. [34], which is aimed at the coexistence of multiple multicast groups in the same network. In this scheme, three different services are provided by the service provider for the IEEE 802.16 network [35]. The service provider is responsible for managing each user group. When a user exits or joins the user group, the service provider needs to update the broadcast key using asymmetric encryption. However, due to the limited resources of IoT devices, asymmetric encryption increases the computational cost of the key generation process. In the group key agreement scheme proposed in [36], the group key used for encryption is negotiated by members of the group, and then each group member is assigned a key for decryption. Only members of the group can decrypt the ciphertext encrypted by their shared key. Like the above scheme, in [34], this scheme also uses asymmetric encryption to establish multigroup keys. Recently, the authors of [37] proposed a multiparty key agreement based on elliptic curve cryptography (ECC) encryption, which is more computational efficient than RSA, but this protocol also needs a group controller (GC) and rekeying overhead. Hsu et al. [38] proposed an efficient user-oriented multigroup key agreement scheme based on secret sharing, which relies on the trusted key generation center (KGC) to negotiate keys. We observe that in an IoT HCS, if there is no trusted KGC, self-organized one-time multiple group keys generation will be desired by all group members. This observation motivates us to come up with a solution to meet this requirement.


## 3. Preliminaries

We briefly described the knowledge related to secret sharing in this section. In the secret sharing scheme, the trusteddealer splits the secret s into multiple smaller shares and transmits them to the participants in the group to realize the sharing of the secret in the same group. Authorized participants in the same group can recover their secrets, while other unauthorized participants cannot recover their secrets. If a scheme can make it impossible for any unauthorized participant to recover the key and obtain any secret-related information, it is regarded as a perfect scheme.SupposeP=1,…,n represents a collection of participants. Based on the Shannon’s entropy function, [39] proposed that secret sharing protocol should meet the following conditions:(a)
Correctness. The secrets s can be recovered by authorized participants. In other words, it has HS|A=0 for any A∈Γ. Γ refers to access structure that is the collection of authorized participants.(b)
Security. It is impossible for the secret s to be recovered by an unauthorized participant. In other words, it has 0<HS|A≤HS for any A∉Γ. What we are concerned about is HS|A=HS. In this case, any information related to the secret s cannot be obtained by the participants in A. So, the security of this protocol is perfect.If the participant’s share is in the same domain as the secret (this is the minimum size of the shares as demonstrated in [40]), a perfect secret sharing protocol is ideal.


### 3.1. Secret Sharing Scheme Based on Polynomials

In Shamir’st,n secret sharing scheme [41] based on linear polynomial, the trusted dealer chooses a t−1 degree polynomial fx, where f0=s. The dealer uses fx to split s into smaller shares, fxi, i=1,2,…,n, and distribute them to each participant, where xi is a public identifier for each participant Ui. This secret sharing scheme meets the above two security features. That are (a) the secret that can be recovered only if the number of shares is not less than t and (b) the number of shares is less than t, it is impossible to recover the secret. Hence, Shamir’s t,n secret sharing scheme is unconditionally secure, and it contains the following two phases.


#### 3.1.1. Share Generation

Suppose there aren participants, U=U1,U2,…,Un. Dealer D randomly selects a t−1 degree polynomial fx=a0+a1x+⋯+at−1xt−1modp, where the secret s=f0=a0, and all coefficients, ai, i=0,1,…,t−1, belong to the finite field GFp with p>s. D calculates n shares, yi=fxi, i=1,2,…,n, where xi is a public identifier for each participant Ui. Then, each share yi is secretly distributed to the corresponding participant Ui.


#### 3.1.2. Secret Reconstruction

Assume that there aret participants, U1,U2,…,Ut, reconstructing the secret s. Participants release their shares and recover the secret by using the Lagrange interpolating formula, s=f0=∑i=1tfxi∏r=1,r≠it−xr/xi−xrmodp.


## 3.1. Secret Sharing Scheme Based on Polynomials

In Shamir’st,n secret sharing scheme [41] based on linear polynomial, the trusted dealer chooses a t−1 degree polynomial fx, where f0=s. The dealer uses fx to split s into smaller shares, fxi, i=1,2,…,n, and distribute them to each participant, where xi is a public identifier for each participant Ui. This secret sharing scheme meets the above two security features. That are (a) the secret that can be recovered only if the number of shares is not less than t and (b) the number of shares is less than t, it is impossible to recover the secret. Hence, Shamir’s t,n secret sharing scheme is unconditionally secure, and it contains the following two phases.


### 3.1.1. Share Generation

Suppose there aren participants, U=U1,U2,…,Un. Dealer D randomly selects a t−1 degree polynomial fx=a0+a1x+⋯+at−1xt−1modp, where the secret s=f0=a0, and all coefficients, ai, i=0,1,…,t−1, belong to the finite field GFp with p>s. D calculates n shares, yi=fxi, i=1,2,…,n, where xi is a public identifier for each participant Ui. Then, each share yi is secretly distributed to the corresponding participant Ui.


### 3.1.2. Secret Reconstruction

Assume that there aret participants, U1,U2,…,Ut, reconstructing the secret s. Participants release their shares and recover the secret by using the Lagrange interpolating formula, s=f0=∑i=1tfxi∏r=1,r≠it−xr/xi−xrmodp.


## 3.1.1. Share Generation

Suppose there aren participants, U=U1,U2,…,Un. Dealer D randomly selects a t−1 degree polynomial fx=a0+a1x+⋯+at−1xt−1modp, where the secret s=f0=a0, and all coefficients, ai, i=0,1,…,t−1, belong to the finite field GFp with p>s. D calculates n shares, yi=fxi, i=1,2,…,n, where xi is a public identifier for each participant Ui. Then, each share yi is secretly distributed to the corresponding participant Ui.


## 3.1.2. Secret Reconstruction

Assume that there aret participants, U1,U2,…,Ut, reconstructing the secret s. Participants release their shares and recover the secret by using the Lagrange interpolating formula, s=f0=∑i=1tfxi∏r=1,r≠it−xr/xi−xrmodp.


## 4. Model of Our Multigroup Key Agreement Scheme

The model of the proposed multigroup key agreement scheme for IoT HCS is presented in this section, which contains system model and security model.


### 4.1. System Model

There is a KGC in our proposed protocol for IoT HCS, and it is assumed that there aren users U1,U2,…,Un participating in multigroup communication. The system model of our proposed protocol is illustrated in Figure 1. These users can be doctors, patient, caretaker, ambulance, and hospital. KGC is responsible for user registration and managing all registered users, including adding users and deleting users. In the IoT HCS, if there is no trusted KGC, all members of the group participating in the communication will negotiate to generate multiple group keys before communication in order to exchange information securely. Generally, self-organized multiple group keys generation should be performed by all group members. Hence, group session keys can only be generated by members in the same group.Figure 1
Multiple-group applications in IoT HSC.During the registration phase of the proposed protocol, each userUi is secretly assigned a long-term secret generated by KGC. Next, self-organized multigroup keys generation will be performed by all group members. In other words, when accepting the key agreement request initiated by one of the users to multiple groups, each user select one value for each group he joins and transfer each value secretly to the corresponding group members. Then, each user uses the values received from other group members, who belong to the same group, to recover the polynomial and the corresponding group key and further authenticates that this group key is the same with other group members. Later, members in the group use the generated self-organizing multigroup key for secure communication.Public key calculation uses a large modulus, such as at least 1024 bits in RSA. In comparison, polynomial encryption uses a small modulus, only 160 bits. Therefore, our protocol based on polynomial encryption is more efficient and computationally faster. In addition, conventional group key agreement protocols need a mutually trusted KGC generate all group keys for multigroups. This method relies on trusted servers and will incur communication and storage overhead in IoT HCS. The problem with the trusted server is that if it is attacked, the network will be completely insecure. In order to address the problem, self-organized multigroup keys generation is performed by all group members. This makes our protocol very effective and practical.


### 4.2. Security Model

We briefly describe the security model to evaluate the security of the proposed scheme.


#### 4.2.1. Type of Adversaries

Our protocol mainly analyzes two types of adversaries, internal and external. An internal attacker refers to a legitimate member of the group, so the group key is known to him. The internal attacker may attempt to obtain the long-term secret keys of other members, which allows him to impersonate other members for secure communication. In addition, internal attackers may also obtain other group keys without authorizing him to know and leak them out. On the other hand, group keys that are not allowed to be known by outsiders may be maliciously obtained by an external attacker. The confidentiality of the group key affects the success rate of this attack. We will explain in detail that our scheme can resist these attacks in the following security analysis.


#### 4.2.2. Security Features

The following security features need to be satisfied:(a)
Key confidentiality: it is computationally infeasible for external attackers to obtain any group key.(b)
Key authentication: the generated group key is required to be authenticated by group members, which is the same with the corresponding group members.(c)
Key independence: unauthorized users are not able to obtain other group keysK″=K−K′ based on the known subset of group keys K′⊂K.(d)
Forward secrecy: ensure that members who have left cannot know the new communication message.(e)
Backward secrecy: ensure that new members cannot know the historical communication message.


## 4.1. System Model

There is a KGC in our proposed protocol for IoT HCS, and it is assumed that there aren users U1,U2,…,Un participating in multigroup communication. The system model of our proposed protocol is illustrated in Figure 1. These users can be doctors, patient, caretaker, ambulance, and hospital. KGC is responsible for user registration and managing all registered users, including adding users and deleting users. In the IoT HCS, if there is no trusted KGC, all members of the group participating in the communication will negotiate to generate multiple group keys before communication in order to exchange information securely. Generally, self-organized multiple group keys generation should be performed by all group members. Hence, group session keys can only be generated by members in the same group.Figure 1
Multiple-group applications in IoT HSC.During the registration phase of the proposed protocol, each userUi is secretly assigned a long-term secret generated by KGC. Next, self-organized multigroup keys generation will be performed by all group members. In other words, when accepting the key agreement request initiated by one of the users to multiple groups, each user select one value for each group he joins and transfer each value secretly to the corresponding group members. Then, each user uses the values received from other group members, who belong to the same group, to recover the polynomial and the corresponding group key and further authenticates that this group key is the same with other group members. Later, members in the group use the generated self-organizing multigroup key for secure communication.Public key calculation uses a large modulus, such as at least 1024 bits in RSA. In comparison, polynomial encryption uses a small modulus, only 160 bits. Therefore, our protocol based on polynomial encryption is more efficient and computationally faster. In addition, conventional group key agreement protocols need a mutually trusted KGC generate all group keys for multigroups. This method relies on trusted servers and will incur communication and storage overhead in IoT HCS. The problem with the trusted server is that if it is attacked, the network will be completely insecure. In order to address the problem, self-organized multigroup keys generation is performed by all group members. This makes our protocol very effective and practical.


## 4.2. Security Model

We briefly describe the security model to evaluate the security of the proposed scheme.


### 4.2.1. Type of Adversaries

Our protocol mainly analyzes two types of adversaries, internal and external. An internal attacker refers to a legitimate member of the group, so the group key is known to him. The internal attacker may attempt to obtain the long-term secret keys of other members, which allows him to impersonate other members for secure communication. In addition, internal attackers may also obtain other group keys without authorizing him to know and leak them out. On the other hand, group keys that are not allowed to be known by outsiders may be maliciously obtained by an external attacker. The confidentiality of the group key affects the success rate of this attack. We will explain in detail that our scheme can resist these attacks in the following security analysis.


### 4.2.2. Security Features

The following security features need to be satisfied:(a)
Key confidentiality: it is computationally infeasible for external attackers to obtain any group key.(b)
Key authentication: the generated group key is required to be authenticated by group members, which is the same with the corresponding group members.(c)
Key independence: unauthorized users are not able to obtain other group keysK″=K−K′ based on the known subset of group keys K′⊂K.(d)
Forward secrecy: ensure that members who have left cannot know the new communication message.(e)
Backward secrecy: ensure that new members cannot know the historical communication message.


## 4.2.1. Type of Adversaries

Our protocol mainly analyzes two types of adversaries, internal and external. An internal attacker refers to a legitimate member of the group, so the group key is known to him. The internal attacker may attempt to obtain the long-term secret keys of other members, which allows him to impersonate other members for secure communication. In addition, internal attackers may also obtain other group keys without authorizing him to know and leak them out. On the other hand, group keys that are not allowed to be known by outsiders may be maliciously obtained by an external attacker. The confidentiality of the group key affects the success rate of this attack. We will explain in detail that our scheme can resist these attacks in the following security analysis.


## 4.2.2. Security Features

The following security features need to be satisfied:(a)
Key confidentiality: it is computationally infeasible for external attackers to obtain any group key.(b)
Key authentication: the generated group key is required to be authenticated by group members, which is the same with the corresponding group members.(c)
Key independence: unauthorized users are not able to obtain other group keysK″=K−K′ based on the known subset of group keys K′⊂K.(d)
Forward secrecy: ensure that members who have left cannot know the new communication message.(e)
Backward secrecy: ensure that new members cannot know the historical communication message.


## 5. The Proposed Protocol for Multigroup Communications

Suppose that there are a total ofn users participating in multigroup communication U1,U2,…,Un. Before receiving system services, users need to register with KGC. KGC is responsible for user registration and managing all registered users, including adding users and deleting users. Before group members communicate, the session key of each group is distributed to the corresponding members of the same group in a secure manner, which ensures the security of communication. Generally, the session key of each group is determined by all corresponding members of the group according to the membership to which they belong. Hence, group session keys can only be generated by members in the same group.Table1 illustrates the symbols used in this paper is shown in Table 1. There are three stages in the proposed multigroup communication protocol, namely the initialization phase of KGC, the registration phase, and the multigroup key agreement phase. Users participating in multigroup communication are recorded as U1,U2,…,Un, and these groups are recorded as G1,G2,…,Gm. A multigroup table is determined in Table 2, where if Ui (1≤i≤n) joins the group Gk (1≤k≤m), then the corresponding unit aik=1, else aik=0. Here we define the rank of a user, Ui, as the number of nonzero elements in (ai1,ai2,…,aim) and define the rank of a group, Gk, as the number of nonzero elements in (a1k,a2k,…,ank).Table 1
Notation table.
NotationDescriptionUiUseriKGCKey generation centerpA safe large prime withp>nfxA univariate polynomialgA generator ofGFpGiGroupiKiSecret group communication keyih⋅One-way hash functionUiThe rank of userUiGkThe rank of groupGkTable 2
Multigroup description.
UsersGroupsG1G2…Gk…GmU1a11a12…a1k…a1mU2a21a22…a2k…a2m…………………Uiai1ai2…aik…aim…………………Unan1an2…ank…anmThe detailed multigroup keys establishment is as follows:Initialization of KGC. First, the KGC selects a large prime p, a generator g of GFp, and constructs a secure one-way hash function h⋅ based on the domain GFp. These parameters p, g, and h⋅ are published by the KGC.User Registration. Every user who needs multigroup key agreement service must first register with KGC. KGC is responsible for managing all registered users and updating the number of users in real time. After receiving the user’s registration request, KGC generates a long-term secret, xi∈GFp, for user Ui and distributes it to Ui secretly and publishes gxi, where xi≠xj, and i,j∈1,…,n. Later in real-time operation, multigroup keys will be calculated by the members of the group participating in the communication using their long-term secrets and used for secure communication between group members.Multigroup Keys Establishment. In the IoT HCS, if there is no trusted KGC, then self-organized multigroup keys generation should be performed by all group members. Upon receiving multigroup keys agreement request for these groups G1,G2,…,Gm from any group member, all involved group members will establish the m corresponding group keys K1,K2,…,Km as the following steps:Step 1. The initiator broadcasts a multigroup keys establishment request for these groups G1,G2,…,Gm, where each group Gk=Uk1,Uk2,…,UkGk, k∈1,…,m and k1,k2,…,kGk∈1,…,n.Step 2. Each participating group member Ui (1≤i≤n) responds by broadcasting the list of his involved groups, Gi1,Gi2,…,GiUi, i1,i2,…,iUi∈1,…,m.Step 3. Each member Ui (1≤i≤n) selects and broadcasts a random challenge, ri∈GFp.Step 4. According to the multigroup table, if aik=1 for 1≤k≤m, then each member Ui (1≤i≤n), needs to randomly select a corresponding value Rik∈GFp, which is used to compute the group key Kk. Altogether Ui should select Ui such values.Step 5. Each member Ui uses his secret share xi, his challenge ri, and the public value gxj+rj to calculate the pairwise shared secret keys between Ui and Uj, ki,j=gxj+rjxi+ri, where i≠j for i,j∈1,2,…,n. Then, if aik=1 and ajk=1 for 1≤k≤m, Ui sends the corresponding Rik secretly to Uj as ci,j=Eki,jRik, 1≤i≤n, where Eki,jRik represents the encryption of Rik using the key ki,j.Step 6. After receiving ciphertext, cj,i (i≠j for i,j∈1,2,…,n) from each member Uj, Ui computes Rjk=Dkj,icj,i, where Dkj,icj,i refers to decrypt cj,i using the key kj,i=ki,j=gxj+rjxi+ri. Then, for each group Gk (k∈1,2,…,m) that Ui joins, Ui will altogether obtain Gk points l,Rlk, where alk=1 for 1≤l≤n. According to these Gk points, user Ui generates a (Gk−1) degree polynomial fkx for each group Gk and select the constant term of fkx as the group key Kk. Then, Ui broadcasts Ui such values hKk to all group members, where alk=1 for 1≤k≤m.Step 7. Each member Ui checks whether these broadcasting hKk for 1≤k≤m are identical, respectively. If they are identical, Ui, for 1≤i≤n, authenticates that these m group keys K1,K2,…,Km are valid. If some of these group keys are not identical, the corresponding group members will replay this protocol again. All computations are performed in GFp.After successfully completing the above steps,m group keys K1,K2,…,Km associated with G1,G2,…,Gm, respectively, are self-established among all group members. Then, group members can use these group keys K1,K2,…,Km for secure multigroup communication.


## 6. Security Analysis

### 6.1. Correctness

In Step 6,Ui will altogether obtain Gk points l,Rlk from the group Gk he joined, where alk=1 for 1≤l≤n, and k∈1,…,m. According to these points Gk, user Ui can calculate a (Gk−1) degree polynomial fkx for each group Gk by using the Lagrange interpolation formula and select the constant term of fkx as the group key Kk. Then Ui broadcasts Ui such values hKk to all group members, where aik=1 for 1≤k≤m. In Step 7, each member Ui checks whether these broadcasting hKk for 1≤k≤m are identical, respectively. If they are identical, Ui (1≤i≤n) authenticates that these m group keys K1,K2,…,Km are valid.


### 6.2. Security

The security of the proposed protocol is discussed by analyzing the following security features:(1)
The proposed scheme can guarantee the freshness, confidentiality, and independence of the key and provide verification for the key.(2)
This scheme is able to withstand attacks that occur on synchronous and asynchronous networks.(3)
The forward and backward safety are guaranteed in this scheme. Forward security refers to the protection of new keys from being obtained by leaving members. Backward security means that new members who join the group cannot obtain the previous key.(4)
Internal attacks and external attacks cannot be achieved in this scheme. The internal attacker does not know other group keys except the key of the group he belongs to. All group keys are not obtained by external attackers.Theorem 1.
The proposed protocol can ensure the freshness, confidentiality and independence of the key, and provide verification for the key.Proof.
Key freshness is satisfied since for each request to generate multigroup key, there arem new group keys K1,K2,…,Km associated with G1,G2,…,Gm, where each group’s session key Kk (k∈1,2,…,m) is decided by all corresponding group members according to the membership to which they belong. Hence, the group session key can only be negotiated by members belonging to the group. In addition, each group member, Ui, uses Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul, to generate a (Gk−1) degree polynomial fkx and the constant term of fkx is the group key Kk for group Gk.
Key confidentiality is guaranteed by secret sharing protocol. The secret key of each group is decided by all members participating in the communication in the group according to the memberships that they belong to. These group members will interact with each other by fresh pairwise keys, which are computed using their long-term secrets xi and random challenges ri. Hence, the group session key can only be negotiated by members belonging to the group.
Key authentication is provided by the value hK1,hK2,…,hKm, which is generated by one-way hash function in Step 6, with the group keys K1,K2,…,Km as input. The secret group key is determined by all members participating in the communication in the group. Besides, the group key cannot be forged by an internal attacker because it is decided by all corresponding group members according to the memberships that they belong to.
Key independence is provided. It means that the group member cannot obtain any other group key information that he has not authorized from the corresponding group key that he has obtained. This is because each group key Kk (k∈1,2,…,m) is computed by Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul. The proof process is given in detail in Theorem 5.Theorem 2.
The proposed protocol is able to withstand attacks in synchronous and asynchronous networks.Proof.
Group members will interact with each other by fresh pairwise keys, which are computed using their long-term secretsxi and random challenges ri. Each group key Kk (k∈1,2,…,m) reconstruction is based on Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul. There is only a list of groups G1,G2,…,Gm, the parameters p, g, h⋅, and gxi, and random challenges ri∈GFp available. In real-time operation, multigroup keys generation is performed by all involved group members. It is impossible for an attacker to get information related to the key from the asynchronously released values. The proof process is given in detail in Theorems 4 and 5.Theorem 3.
The forward and backward secrecy are guaranteed in the proposed scheme, which means that the leaving members are unable to obtain the new group key, and the newly joined member does not know the past key.Proof.
When the group members change, such as a member leaving the group or a new member joining, in step 1, the list of groupsG1,G2,…,Gm will be updated in real time. Group key in multigroup session is decided by all corresponding group members according to the memberships that they belong to. Members in the group can only get the session key of the group they are currently in. In other words, new keys will not be obtained by the leaving members. And the previous key cannot be obtained by newly joined group members. Therefore, the proposed protocol guarantees both the forward and backward security of multigroup keys.
Our proposed scheme divides adversaries into two types. One type of adversary is external attacker, which refers to members outside the group. An external attacker may attempt to obtain a private group key that is not allowed to be known by user outside the group. The confidentiality of the key guarantees that external attackers cannot achieve this kind of attack. In addition, our scheme allows any user to send a request to KGC to obtain the service of multigroup key establishment. Then an external attacker may pretend to be other legitimate members of the group to request the service of key establishment. However, the information related to the group key cannot be obtained by an external attacker through this attack. Because the proposed scheme guarantees that members who are not authorized cannot obtain the group key. The other type of adversary refers to internal attackers. They are authorized to access the group key of their group, but they try to obtain the secrets shared by other members with KGC. Therefore, it is necessary to protect the secrets shared by other members with KGC from inside attackers.Theorem 4.
(outsider attack). Suppose there is an adversary impersonating a member of a group. Our scheme guarantees that the attacker cannot acquire the corresponding group key and share the key with other members of the group.Proof.
In our scheme, any attacker is able to impersonate another member to request services from KGC and get a response message. However, it is guaranteed that only legitimate members of the group can obtain the secret key of the group. In our proposed scheme, group members will interact with each other by fresh pairwise keys, which are computed using their long-term secretsxi and random challenges ri. Each group key Kk (k∈1,2,…,m) reconstruction is based on Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul. There is only a list of groups G1,G2,…,Gm, the parameters p, g, h⋅, and gxi, and random challenges ri∈GFp available. The polynomial-based secret sharing scheme, the difficulty of the discrete logarithm problem, and the one-way nature of the hash function protect the secret group key from being acquired by an attacker.
Group members cannot obtain information about other keys that are not allowed to know based on the recovered secret group key. This is because each group key can only be calculated by the long-term secret calculation of the corresponding member in the group. Hence,key independence is guaranteed in our protocol.
The possibility of an attacker successfully negotiating the leaked group key with other members by replaying the eavesdropped communication message is negligible. This is because the fresh pairwise keys are computed using their random challengesri and each group key Kk (k∈1,2,…,m) reconstruction is based on Gk points l,Rlk, where Rlk is randomly selected by Ul. The parameters ri and Rlk are different in each round of communication. Thus, our protocol is able to withstand the replay attack.Theorem 5.
(insider attack). Suppose the proposed scheme has been performed many times. The secretx∈K shared by group members and KGC is not known to all other members.Proof.
The group key in our protocol will be generated by members of the group participating in the communication. Each group’s session key is decided by all corresponding group members according to the memberships that they belong to. These group members will interact with each other by fresh pairwise keys, which are computed using their long-term secrets. However, the secretx∈K shared by group members and KGC is not known by outsiders.
Our scheme does not authenticate the user who sent the service request. Internal attackers can request services from KGC and pretend to be a member of the group to initiate a challenge. Suppose that there is an adversaryUi, he sends a group key agreement service request to the group including himself and member Utarget and forges the group member’s challenge rtarget. Although the adversary Ui can obtain the group key, the value xtarget is not known to him, since xtarget is protected in ki,target=gxtarget+rtargetxi+ri due to the difficulty of discrete logarithm problem. Thus, the internal attacker can only obtain the secret group key of the group and cannot know the long-term secrets of other members in the group. Therefore, the insider attack cannot be implemented in the proposed protocol.


## 6.1. Correctness

In Step 6,Ui will altogether obtain Gk points l,Rlk from the group Gk he joined, where alk=1 for 1≤l≤n, and k∈1,…,m. According to these points Gk, user Ui can calculate a (Gk−1) degree polynomial fkx for each group Gk by using the Lagrange interpolation formula and select the constant term of fkx as the group key Kk. Then Ui broadcasts Ui such values hKk to all group members, where aik=1 for 1≤k≤m. In Step 7, each member Ui checks whether these broadcasting hKk for 1≤k≤m are identical, respectively. If they are identical, Ui (1≤i≤n) authenticates that these m group keys K1,K2,…,Km are valid.


## 6.2. Security

The security of the proposed protocol is discussed by analyzing the following security features:(1)
The proposed scheme can guarantee the freshness, confidentiality, and independence of the key and provide verification for the key.(2)
This scheme is able to withstand attacks that occur on synchronous and asynchronous networks.(3)
The forward and backward safety are guaranteed in this scheme. Forward security refers to the protection of new keys from being obtained by leaving members. Backward security means that new members who join the group cannot obtain the previous key.(4)
Internal attacks and external attacks cannot be achieved in this scheme. The internal attacker does not know other group keys except the key of the group he belongs to. All group keys are not obtained by external attackers.Theorem 1.
The proposed protocol can ensure the freshness, confidentiality and independence of the key, and provide verification for the key.Proof.
Key freshness is satisfied since for each request to generate multigroup key, there arem new group keys K1,K2,…,Km associated with G1,G2,…,Gm, where each group’s session key Kk (k∈1,2,…,m) is decided by all corresponding group members according to the membership to which they belong. Hence, the group session key can only be negotiated by members belonging to the group. In addition, each group member, Ui, uses Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul, to generate a (Gk−1) degree polynomial fkx and the constant term of fkx is the group key Kk for group Gk.
Key confidentiality is guaranteed by secret sharing protocol. The secret key of each group is decided by all members participating in the communication in the group according to the memberships that they belong to. These group members will interact with each other by fresh pairwise keys, which are computed using their long-term secrets xi and random challenges ri. Hence, the group session key can only be negotiated by members belonging to the group.
Key authentication is provided by the value hK1,hK2,…,hKm, which is generated by one-way hash function in Step 6, with the group keys K1,K2,…,Km as input. The secret group key is determined by all members participating in the communication in the group. Besides, the group key cannot be forged by an internal attacker because it is decided by all corresponding group members according to the memberships that they belong to.
Key independence is provided. It means that the group member cannot obtain any other group key information that he has not authorized from the corresponding group key that he has obtained. This is because each group key Kk (k∈1,2,…,m) is computed by Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul. The proof process is given in detail in Theorem 5.Theorem 2.
The proposed protocol is able to withstand attacks in synchronous and asynchronous networks.Proof.
Group members will interact with each other by fresh pairwise keys, which are computed using their long-term secretsxi and random challenges ri. Each group key Kk (k∈1,2,…,m) reconstruction is based on Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul. There is only a list of groups G1,G2,…,Gm, the parameters p, g, h⋅, and gxi, and random challenges ri∈GFp available. In real-time operation, multigroup keys generation is performed by all involved group members. It is impossible for an attacker to get information related to the key from the asynchronously released values. The proof process is given in detail in Theorems 4 and 5.Theorem 3.
The forward and backward secrecy are guaranteed in the proposed scheme, which means that the leaving members are unable to obtain the new group key, and the newly joined member does not know the past key.Proof.
When the group members change, such as a member leaving the group or a new member joining, in step 1, the list of groupsG1,G2,…,Gm will be updated in real time. Group key in multigroup session is decided by all corresponding group members according to the memberships that they belong to. Members in the group can only get the session key of the group they are currently in. In other words, new keys will not be obtained by the leaving members. And the previous key cannot be obtained by newly joined group members. Therefore, the proposed protocol guarantees both the forward and backward security of multigroup keys.
Our proposed scheme divides adversaries into two types. One type of adversary is external attacker, which refers to members outside the group. An external attacker may attempt to obtain a private group key that is not allowed to be known by user outside the group. The confidentiality of the key guarantees that external attackers cannot achieve this kind of attack. In addition, our scheme allows any user to send a request to KGC to obtain the service of multigroup key establishment. Then an external attacker may pretend to be other legitimate members of the group to request the service of key establishment. However, the information related to the group key cannot be obtained by an external attacker through this attack. Because the proposed scheme guarantees that members who are not authorized cannot obtain the group key. The other type of adversary refers to internal attackers. They are authorized to access the group key of their group, but they try to obtain the secrets shared by other members with KGC. Therefore, it is necessary to protect the secrets shared by other members with KGC from inside attackers.Theorem 4.
(outsider attack). Suppose there is an adversary impersonating a member of a group. Our scheme guarantees that the attacker cannot acquire the corresponding group key and share the key with other members of the group.Proof.
In our scheme, any attacker is able to impersonate another member to request services from KGC and get a response message. However, it is guaranteed that only legitimate members of the group can obtain the secret key of the group. In our proposed scheme, group members will interact with each other by fresh pairwise keys, which are computed using their long-term secretsxi and random challenges ri. Each group key Kk (k∈1,2,…,m) reconstruction is based on Gk points l,Rlk, where alk=1 for 1≤l≤n and Rlk is randomly selected by Ul. There is only a list of groups G1,G2,…,Gm, the parameters p, g, h⋅, and gxi, and random challenges ri∈GFp available. The polynomial-based secret sharing scheme, the difficulty of the discrete logarithm problem, and the one-way nature of the hash function protect the secret group key from being acquired by an attacker.
Group members cannot obtain information about other keys that are not allowed to know based on the recovered secret group key. This is because each group key can only be calculated by the long-term secret calculation of the corresponding member in the group. Hence,key independence is guaranteed in our protocol.
The possibility of an attacker successfully negotiating the leaked group key with other members by replaying the eavesdropped communication message is negligible. This is because the fresh pairwise keys are computed using their random challengesri and each group key Kk (k∈1,2,…,m) reconstruction is based on Gk points l,Rlk, where Rlk is randomly selected by Ul. The parameters ri and Rlk are different in each round of communication. Thus, our protocol is able to withstand the replay attack.Theorem 5.
(insider attack). Suppose the proposed scheme has been performed many times. The secretx∈K shared by group members and KGC is not known to all other members.Proof.
The group key in our protocol will be generated by members of the group participating in the communication. Each group’s session key is decided by all corresponding group members according to the memberships that they belong to. These group members will interact with each other by fresh pairwise keys, which are computed using their long-term secrets. However, the secretx∈K shared by group members and KGC is not known by outsiders.
Our scheme does not authenticate the user who sent the service request. Internal attackers can request services from KGC and pretend to be a member of the group to initiate a challenge. Suppose that there is an adversaryUi, he sends a group key agreement service request to the group including himself and member Utarget and forges the group member’s challenge rtarget. Although the adversary Ui can obtain the group key, the value xtarget is not known to him, since xtarget is protected in ki,target=gxtarget+rtargetxi+ri due to the difficulty of discrete logarithm problem. Thus, the internal attacker can only obtain the secret group key of the group and cannot know the long-term secrets of other members in the group. Therefore, the insider attack cannot be implemented in the proposed protocol.


## 7. Performance Evaluation

By comparing with the recently proposed multigroup key agreement scheme [34, 37] based on public key encryption, the performance of our scheme is evaluated in this section. Then we show the comparison between our protocol and the latest multigroup key establishment protocols.Compared with the public-key-based multigroup key establishment schemes [34, 37], our protocol has the following advantages:(a)
Flexible and convenient network structures do not require a central server, such as peer-to-peer network. In P2P network, ‘peers’ are the nodes or computer system that are connected to each other. Files or resources can be shared directly between the system on the network, without the need of any central server. Conventional group key agreement schemes require a central server, namely trusted KGC, to generate all group keys for multigroups. This method needs to set up a trusted server, so it will incur the overhead costs in communications and storages in sensor networks. In addition, if the trusted server is compromised, the network will be insecure. To overcome this drawback, in our protocol, KGC-free multigroup keys generation is performed by all group members.(b)
In the public key broadcast-based scheme [34, 37], the broadcast key needs to be updated when the user changes, which increases the cost of the scheme. In comparison, KGC is responsible for managing member changes in our secret sharing scheme. If a new user joins the group, he only needs to register with KGC and obtain the long-term secret distributed by KGC in a secure way. This process will not affect the long-term secrets of other existing members. In addition, the member’s departure only requires KGC to delete the user without regenerating the key.(c)
It is well known that symmetric key encryption is a way that each pair of users shares a symmetric key, but this way only provides confidentiality. Further, key distribution and management is a bottleneck in symmetric key cryptography, which produces huge communication and storage cost. Hence, public key encryption appeared, which can provide confidentiality, authenticity, and nonrepudiation but with high computation cost due to very large modulus and modular exponentiation operations. Compared with public key operations producing high computation cost, bivariate polynomial-based approach can provide not only authentication and information-theoretic security but also with lower computation cost. At the same time, compared with symmetric key distribution process that needs huge communication cost, bivariate polynomial-based approach is really efficient while providing authentication. In our protocol, the polynomial calculation uses a small modulus, only 160 bits. In comparison, public key calculations not only require a larger modulus (for example, at least 1024 bits in RSA) but also use modular exponentiation, pairing, and scalar multiplication operations (such as ECC-based schemes). Therefore, the calculation efficiency of polynomials is higher than that of public key calculations.Meanwhile, Table3 compares our proposed scheme with the latest multigroup key agreement schemes, which demonstrate that our protocol has the optimal performance.Table 3
Comparison with latest multigroup key establishment protocols.
Park et al. [34]Hsu et al. [38]Naresh et al. [37]OursMultiple group keys establishment at one timeYesYesYesYesTrusted server neededYesYesYesNoComputations for encryption and decryptionRSA-basedPolynomial-basedElliptic curve cryptography- (ECC-) basedPolynomial-basedRekeying overhead neededYesNoYesNo


## 8. Conclusions

We present an efficient and flexible KGC-free polynomial-based multiple group keys establishment protocol for IoT HCS in this paper. The proposed protocol can generate multiple group keys for all group members at one time. In addition, there is no need for a trusted KGC in the process of group keys establishment, and each user can join multiple groups at the same time using only one share reserved. Meanwhile, the security of the proposed protocol is strictly analyzed. Finally, we compare this protocol with the latest multigroup key establishment protocols in performance analysis, which indicates that our KGC-free polynomial-based multiple group keys establishment protocol is fairly attractive for efficient and flexible IoT HCS.



---

*Source: 7703466-2021-09-22.xml*