# Self-Healing Group Key Distribution Facilitating Source Authentication Using Block Codes

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

---

## Abstract

Secure group key distribution is essential for many group-oriented applications such as sensor networks, multimedia broadcast services, and Internet of Things (IoT) scenarios. There are several challenges and requirements in designing secure group key distribution. Among them, computational efficiency, communication efficiency, adaptability to dynamic group membership change, robustness to various security threats, self-healing capacities, and source authentication are desirable. It is very challenging to design an efficient group distribution that satisfies all the requirements and challenges. Based on block codes, we propose an efficient self-healing group key distribution that facilitates both message source authentication and secure group key distribution, where the source identification and authentication can facilitate intrusion detection and identification. Both the privacy of the group key and the authentication of message sources are computationally secure. To the best of our knowledge, it is the first codes-based scheme that satisfies all the above requirements and facilitates message source authentication. The merits of the proposed scheme include the following: (1) it is highly efficient in terms of computation and communication, (2) it provides self-healing capacities for unstable environments, (3) it is very robust to various security threats and attacks, (4) it facilitates both message source authentication and secure group key distribution, and (5) it greatly improves the communication performance, compared to the state-of-the-art schemes. The security properties are analyzed, and the performance evaluations confirm its efficiency and practicality.


---

## Body

## 1. Introduction

Various group-oriented services such as audio/video broadcasting, conferencing, collective working, Internet-of-Things (IoT) scenarios, military operations, and rescue missions have been popular, and many new group-oriented services such as location-based social services are booming. To protect the confidentiality of the group-oriented services, it is common to encrypt the contents using the group keys, and only the authorized entities can access the contents using the keys. However, it is very challenging to design and deploy suitable group key distribution/agreement schemes to satisfy all the requirements of these services.To facilitate group key sharing in group-oriented services, one approach is group key distribution and the other is group key agreement. In a group key agreement scheme, a set of entities co-operatively generate the group key. In a group key distribution scheme, a trusted third party called Group Manager (GM) determines the group key and securely distributes the key to those legitimate entities. For those scenarios where either infrastructure or semi-infrastructure is available, group key distribution is preferred owing to the efficiency and easy deployment/maintenance. From the perspectives of how the membership structure is formed, group key distribution/agreement schemes can be divided into two categories. One category is for structured membership where the members of a group are predetermined or quite stably maintained. Examples are such as the broadcasting in a hierarchical tree [1] or some grouping of devices in an IoT scenario [2]. The other category is for those scenarios where the membership of a group dynamically changes. This paper focuses on group key distribution for the dynamic membership. Several metrics are commonly adopted to evaluate these group key distribution schemes. Computational complexity and communication complexity are two important metrics as they affect the cost of the implementations, the energy consumption, the efficiency, the lifespan of batteries, etc.For those services with dynamic membership, easy and efficient updating of the group keys for each session is necessary. In those scenarios with dynamic membership and unreliable connections, the function of self-healing allows the authorized entities to easily recover the previous group keys when they reconnect the networks later. Some wireless networks such as mobile ad-hoc networks and some IoT scenarios are likely to be unreliable and highly dynamic in the sense that nodes might move in and out of the range, switch to the sleep mode to extend the battery lifetime, or being disconnected from the networks due to attackers’ disruption. In these scenarios, the system divides the lifetime of the group key distribution into successive time windows called epochs, where each epoch owns a different group key and those legitimate nodes are allowed to derive the group keys for the authorized epochs. A group key distribution scheme with the self-healing property allows a legitimate user (or node) to recover the lost group keys of the previous authorized epochs, even if some previous key distribution packets are lost. When it later reconnects the network, it can recover the lost group keys without requesting additional information from the GM.The robustness against various security threats and attacks (such as collusion attacks, replay attacks, and impersonation attacks) should be ensured. All the above requirements have been studied and many group key distribution schemes have been designed accordingly.However, the key function of source identification/authentication in a group-oriented service has been commonly neglected. In conventional group key distribution schemes, any legitimate entity can use the group key to encrypt the messages such that only authorized entities can decrypt and access the contents; however, the receivers cannot authenticate the source (the origin) of the messages since all legitimate entities access the same group key. The function of source identification and authentication is crucial for many group-oriented services where compromised entities need to be revoked. For example, many IoT devices are resource-limited and are vulnerable to being captured and being compromised; in such environments, it is very important that the intrusion detection system should continuously monitor the traffics to detect and identify the possible compromised devices. One another example is the group communications in military operations, where those captured entities need to be quickly detected and revoked [3]. With source authentication, it greatly facilitates the detection and identification of the compromised devices/entities. Similar scenarios and requirements exist in other group communications. The group communication with message source identification and authentication greatly improves the transmission efficiency, protects the privacy, and facilitates intrusion detection and identification.Message Queue Telemetry Transport (MQTT) is one of the most popular IoT communication protocols. Chien et al. [4] proposed a secure MQTT group communication, but the scheme does not provide source authentication. In Wireless Sensor Networks (WSNs), TESLA also needs the source authentication in the multicast scenarios [5, 6]. Kim et al. addressed the source authentication issue in Cyber-Physical Systems (CPS) such as smart grids [7]. Chan et al. tackled the challenge of source authentication in the group-based 3D streaming service [8]. Unfortunately, the conventional self-healing group key distribution study neglects this crucial function. This makes these conventional schemes functionally incomplete or security-weak for scenarios where authentication is crucial or desirable.This paper, based on block codes [9], proposes a new self-healing group key distribution scheme with the source authentication function. The merits of the scheme include the following: (1) it exhibits excellent performance in terms of computation and communication, (2) it easily supports dynamic membership, (3) it provides self-healing capacities to cope with unreliable connections, (4) it facilitates both group key distribution as well as source message authentication, and (5) it greatly improves communication performance, compared to the state-of-the-art schemes. The rest of this paper is organized as follows. Section 2 discusses the related work. Section 3 introduces the preliminaries of Chien’s block codes-based secret sharing. Section 4 presents the proposed scheme. Section 5 analyzes the security. Section 6 evaluates the performance. Finally, the conclusions are given in Section 7.


## 2. Related Work

Group key distribution schemes [1, 2] are designed for fixed membership scenarios and do not support the dynamic membership.In 2002, Staddon et al. [10] first introduced the self-healing group key distribution with the dynamic membership for the unreliable connection scenarios; they defined the schemes, gave the lower bounds on the implementations, and proposed some constructions. Liu et al. [11] later generalized the definitions and gave some efficient constructions. Blundo et al. [12] slightly modified the definitions, designed some more efficient schemes, explored the lower bounds, and pointed out the weaknesses in some schemes in [10]. Blundo et al. [13] further modified the definitions and gave the new lower bounds on the implementations. Sáez [14] generalized the schemes in two aspects: (1) a general access structure instead of threshold-based ones; (2) a coalition of users can sponsor a user outside the group for one session. Daza et al. [15] noticed that the parameter settings of Dutta–Mulhopadhyay’s works [16, 17] contradicted the lower bounds reported by [12, 13] and found the security flaws. The works in [10–14] mainly focused on the unconditional secure schemes while those in [10, 12] also gave some computational secure schemes. The schemes in [3, 18–26] mainly focused on designing computationally secure self-healing group key distributions with more flexible access structure or with improved efficiency.Tian et al. [24], based on the mathematic structures used, classified the self-healing group key schemes [3, 14, 15, 18–28] into several categories: polynomial-based schemes, exponential arithmetic-based schemes, vector space-based schemes, and pairing-based schemes. Among these approaches, pairing-based schemes demand higher computational cost. Rams and Pacyna did a survey of some earlier self-healing group key distribution schemes [28]. Some of them are restricted by the limitation of access structure expression; for example, these schemes only support the threshold-based access structures. Additionally, some are vulnerable to the collusion attacks. Vadlamudi and Vadlamudi [27] recently proposed a block codes-based scheme that facilitates the communication of any sets of users; the number and the set of revoked users are not constrained; a revoked user is allowed to rejoin the group in any of the later sessions, resist collusion attacks, and provide forward-and-backward secrecy. However, the scheme needs to transmit the new generator matrices in each session, which demands lots of communication overheads. Additionally, the scheme does not provide message source authentication.Vijayakumar et al. [29] proposed an efficient key distribution scheme for the Internet pay-TV systems, using only simple computations; the Internet pay-TV key distribution schemes are similar to our scenarios where the service providers need to refresh the group keys for a set of dynamic groups of legitimate users, but there are some key differences between the two scenarios: (1) there is only one message source (the service provider) in the Internet pay-TV key distribution schemes; (2) due to the nature of the grouping of the services, the systems usually adopt some kinds of key hierarchy or tree structures to tackle the key distribution. Vijayakumar et al. [30] proposed a Chinese Remainder Theory-based distributed group key management scheme which supports the dynamic membership change for the unstructured peer-to-peer networks; the scheme reduces the computational complexity in each user side by slightly increasing the storage space of the peer users. The authors in [31] proposed a new Greatest Common Divisor-based key distribution protocol which aims at reducing the computational complexity and the amount of information stored in the Group Center and the group members; the self-healing function and the message source authentication function were not considered in the requirements. Wang et al. [32] proposed a mutual-healing group key distribution scheme in which the nodes can recover the lost group keys both securely and timely in the Unmanned Aerial Vehicles Ad-Hoc Network (UAANET); the mutual-healing function is efficiently achieved by adopting a private blockchain.Based on block codes, Chien proposed a multisecret sharing scheme [33] and a dynamic-weight multisecret sharing scheme [34]. A unified approach, based on block codes, for both threshold-based secret sharing and general-access-structure secret sharing was proposed in [35]. Inspired by Chien’s block-codes-based secret sharing and Vadlamudi–Vadlamudi’s work [27], we will propose a new self-healing group key distribution scheme with the source authentication function. To the best of our knowledge, this is the first codes-based self-healing group distribution scheme that provides the flexible authorized group and also facilitates message source authentication.


## 3. Preliminaries

The notations used in this paper are summarized in Table1.Table 1
The notations.
U=U1,U2,…,UNThe set of usersGj; nj=GjGj⊂U, the set of authorized users in session j; nj=Gj denotes the number of users in GjM, Mjnj,kj, and Mn,kGenerator matrix for block codes, wheren denotes the block length and k denotes the information length; Mjnj,kj denotes the generator matrix for session j, which is a submatrix of Mn,kki;gkj; rjki: secret key of user Ui; gkj: group key for session j; rj: a random nonceh1,;h2Secure keyed one-way hash functionsh1,: 0,1l1x0,1l2⟶0,1l3, where l1/l2, respectively, denotes the bit length of ki/random nonce; one-way hash functionh2:0,1l3⟶GF2mseedj,i0=h1ki,rjThe seed value for userUi′s hash chains at session jseedj,isseedj,is=h2sh1ki,rj=h2sseedj,i0, where h2s denotes applying h2s times; s is the maximum number of encryptions each member can send in each sessiond = d1,d2,…,dktInformation symbolsdj = d1,d2,…,dnj+1=(gkj,seedj,1s,…,seedj,njs)Information symbols for sessionj; it consists of the group key and the authentication tokens for the participants; s denotes the maximum number of messages in session jc1,c2,..,cN−K; cjParity symbolsT = t1,t2,…Successive time epochsADAdversariesATjThe set of authentication tokens for sessionj; ATj could be used to authenticate the message sources in session jBCjBCj = {Gj,rj,c1,…,cnj}: the broadcast data BCj could be used to derive gkj and ATjMAC()Message authentication code function MAC():GF2m×0,1∗⟶0,1l4; it could be implemented, using HMAC [36]ENC/EnckmsgEncryption/encryption using the keykSecure keyed one-way hash functions [27] are defined as follows: (1) given w and r, it is easy to compute hw,r; (2) given (possibly many) pair of r and hw,r, it is hard to compute w; (3) without the knowledge of w, given (possibly many) pairs of ri and hw,ri, it is hard to compute hw,r′, for r′≠ri; (4) given w, it is hard to find two values r1 and r2 such that hw,r1 = hw,r2, but r1≠r2. We also assume that |hw,r|≤m, where | | denotes the bit length so that hw,r can be considered as an element in GF2m.Next, we briefly review the systematic block codes [38], and then, the technique based on the systematic block codes is described. A (n, k) (withn>k) linear block code over GF2m is defined by a n×k generator matrix M with symbols in GF2m and k<2m. In this paper, we denote the generator matrix as Gn,k, where n is the length and k is the dimension of the linear block codes. Denote d=d1,…,dkt as a vector of k information symbols where dis are in GF2m and superscript t means vector transpose. Then, V=Md=v1,…,vn is the corresponding code word with vis in GF2m.A systematic block code is a type of linear block codes where the firstk elements in a code word are identical to the information symbols d1,…,dk, and the last n-k elements in the code word are denoted as c1,c2,…,cn−k and called the parity symbols. In 1990, Ayanoglu et al. [38] designed a special type of systematic block code generator matrix Mn,k=Ik×kPn−k×k, where Ik×k is the k×k identity matrix and Pn−k×k is a n−k×k matrix gi−1j−1 with g being a primitive element in GF2m and k<2m. Ik×k and Pn−k×k can be represented as follows:(1)Ik×k=10…001…0::::0001,Pn−k×k=111…11gg2…gk−11g2g4…g2k−1:::::1gn−k−1gn−k−12…gn−k−1k−1.SinceV = Mn,kd, then we have(2)ci=∑j=1kgi−1j−1dj,where1≤i≤n−k.We require thatk<2m to satisfy the nonsingular requirement of matrix P [38]. The (n − k) equations in (2) can, therefore, be viewed as the linear-independent equations of indeterminants d1,d2,…,dk. If these (n - k) equations were presented with (n − k)< k, then we would not be able to uniquely determine the values for these d1,d2,…,dk. However, the remaining symbols can be recovered if some of these symbols djs are available such that the number of those missing symbols is smaller or equal to the number of equations. Based on this technique and hash functions, Chien et al. had proposed several secret-sharing schemes [33–35], and we shall propose our self-healing group key distribution scheme with source authentication.


## 4. Block Code-Based Group Key Distribution with Source Authentication

### 4.1. The System Model

There exist three kinds of entities. A Group Manager (GM), a set of usersU=U1,U2,…,UN, where N≤k−1, and adversaries ADs. The system consists of successive time epochs T = t1,t2,… called sessions. The GM would like to securely distribute a group key gkj and a set of authentication tokens to a set of legitimate users in each session tj∈T. Gj denotes the set of the legitimate users for session j and satisfies Gj⊂U. Our definition of self-healing group key distribution with privacy is more flexible and practical in terms of the specification of the legitimate users and revoked users than most of the previous works, and it is the same as Vadlamudi–Vadlamudi’s work [27]. We further extend the functions to include the source authentication. We list the features as follows.(1)
There are no predetermined constraints on the number of legitimate users and on the number of revoked users.(2)
The setsGjs could change in each session without any restriction, that is, any user could be in the legitimate user set or be out of the set at any session; legitimate users could be revoked at any session, and GM could let a revoked user rejoin the legitimate set at any later sessions.(3)
TheADs in each session j could consist of any outsiders and any illegitimate users U−Gj at that session; here, we define outsiders as those entities who have never been registered users of the system, but we define illegitimate users as those registered users who are illegitimate at some specific sessions. The goals of ADs are to access the contents of the group communications by deriving the group keys gkj or to compromise the authentication in the group communications.(4)
Only the legitimate users in the authorized set can access the communication contents and authenticate the source of the messages for that session.Definition 1.
D is a self-healing group key distribution with privacy and message source authentication if(1)
Gj is the set of the authorized users for session j; for any Ui∈Gj, the group key gkj and the authentication tokens ATj can be efficiently determined using BCj and ki.(2)
gkj and ATj cannot be learned from the broadcasts {BC1,…} or the personal keys {k1,…,kN} alone.(3)
For any revoked userUi¯∈R=U−Gj and any adversary AD, it is computationally infeasible to compute gkj and ATj, using the broadcast BCj and its secret keys.(4)
For any coalition of the revoked usersUi¯∈R=U−Gj and any adversary AD, it is computationally infeasible to compute gkjandATj, using the broadcast BCj and their secret keys.(5)
LetC be a coalition of any users Ui¯∈R=U−Gj, and let gkC−ATC be the set of all the group keys and authentication tokens they are authorized to access. Then, C cannot derive gkj and ATj corresponding to Gj, using the broadcasts, their secret keys, and gkC−ATC.(6)
D is self-healing if a user Ui∈Gj can derive gkj and ATj for any j<j′, using ki and BCj′.(7)
D provides message source authentication, if the legitimate users Ui∈Gj can use the tokens in ATj to authenticate the message source of an encryption Encgkjmsg.
Please note that the above property 5 implies and extends the forward secrecy and the backward secrecy in the previous works in the sense that we allow any coalition of illegitimate usersU−Gj∪AD, and there are no constraints on the users joining the group or being revoked from the legitimate group.


### 4.2. The Proposed Scheme

The scheme consists of four phases: initialization phase, group key distribution phase, group key recovery phase, and group communication with authentication phase.


#### 4.2.1. Initialization Phase

GM sets up a systematic block code with a generator matrixMn,k as specified in Section 2, a keyed one-way hash function h1,, and a one-way hash function h2. GM publishes the parameters Mn,k, h1,, and h2. For each user Ui∈U, GM selects a secret key ki and securely distributes ki to Ui.


#### 4.2.2. Group Key Distribution Phase

LetGj⊂U be the authorized user set for a session j∈T, where nj=Gj denotes the number of users in Gj. To simplify the following presentation, let us suppose Gj=U1,U2,…,Unj be the set of legitimate users for session j. GM selects a random group key gkj and a nonce rj and computes seedj,i0=h1ki,rj for each user Ui∈Gj. It computes seedj,is=h2sh1ki,rjwheres is the maximum number of messages transmitted by each user in one session and h2s denotes applying h2s times. gkj is used as the group key, while seedj,is being the authentication token for Ui∈Gj.GM preparesdj = d1,d2,…,dnj+1=(gkj,seedj,1s,…,seedj,njs) as the information to be broadcast and prepares the generator matrix M2nj+1,nj+1 as specified in the preliminaries. GM generates Cj=c1,…,cnj=Pnj×nj+1dj, where the parities are specified as follows:(3)cl=∑u=1nj+1gt−1u−1du,where1≤l≤nj.Finally, GM broadcastsBCj defined by equation (4). For self-healing, GM broadcasts the data defined by equation (5), where a window of p previous sessions is included; as our system does not limit the number of sessions it supports and can continuously run without a specified end, it is reasonable that the messages for long time ago are not interesting to the current entities; the selection of the window size p should depend on the scenarios and the application context. Please note that Vadlamudi–Vadlamudi’s scheme [27] needs to distribute the new generator matrix and the new hash function in each session, but our scheme does not need to redistribute the generator matrix and the one-way hash because each generator matrix in one session is just a subpart of the generator matrix specified in equation (1). In each session, the GM just uses one subpart of the matrix in equation (1). The GM and the authorized users can easily determine the subpart, based on nj=|Gj|:(4)BCj=Gj,rj,c1,…,cnj,(5)BCj−p,…,BCjfor a window ofp+1sessions.


#### 4.2.3. Group Key Recovery Phase

When a userUi∈Gj receives the broadcast BCj, he prepares seedj,i0=h1ki,rj and seedj,is. With the recovered value of seedj,is, now the set of nj linear-independent equations in (2) has only nj unknown variables, and they can be solved by Ui, that is, Ui can recover all the secrets dj = d1,d2,…,dnj+1 = (gkj,seedj,1s,…,seedj,njs). This can be easily implemented, using the matrix multiplications.


#### 4.2.4. Group Communication with Authentication Phase

Any legitimate userUi∈Gj can use the group key gkj to encrypt its message msg and successively use seedj,is−l, where l=1,…,s is a MAC (Message Authentication Code) key to generate the MAC.The encryption ENC and the message authentication code MAC are specified as follows:(6)mac=MACseedj,is−l,msg,ENC=EncgkjUi,msg,mac,seedj,is−l,where Ui broadcasts {ENC} in its lth encryption in session j.Any legitimate userUi∈Gj can use the group key to decrypt the encryption and verify the source by checking whether both the verification equations in (7) hold. If the verifications succeed, then Ui accepts the message msg and is convinced of the source of the message. It stores the authentication token seedj,is−l for verifying the message in the next encryption:(7)seedj,is−l+1=h2seedj,is−l,mac=MACseedj,is−l,msg.


## 4.1. The System Model

There exist three kinds of entities. A Group Manager (GM), a set of usersU=U1,U2,…,UN, where N≤k−1, and adversaries ADs. The system consists of successive time epochs T = t1,t2,… called sessions. The GM would like to securely distribute a group key gkj and a set of authentication tokens to a set of legitimate users in each session tj∈T. Gj denotes the set of the legitimate users for session j and satisfies Gj⊂U. Our definition of self-healing group key distribution with privacy is more flexible and practical in terms of the specification of the legitimate users and revoked users than most of the previous works, and it is the same as Vadlamudi–Vadlamudi’s work [27]. We further extend the functions to include the source authentication. We list the features as follows.(1)
There are no predetermined constraints on the number of legitimate users and on the number of revoked users.(2)
The setsGjs could change in each session without any restriction, that is, any user could be in the legitimate user set or be out of the set at any session; legitimate users could be revoked at any session, and GM could let a revoked user rejoin the legitimate set at any later sessions.(3)
TheADs in each session j could consist of any outsiders and any illegitimate users U−Gj at that session; here, we define outsiders as those entities who have never been registered users of the system, but we define illegitimate users as those registered users who are illegitimate at some specific sessions. The goals of ADs are to access the contents of the group communications by deriving the group keys gkj or to compromise the authentication in the group communications.(4)
Only the legitimate users in the authorized set can access the communication contents and authenticate the source of the messages for that session.Definition 1.
D is a self-healing group key distribution with privacy and message source authentication if(1)
Gj is the set of the authorized users for session j; for any Ui∈Gj, the group key gkj and the authentication tokens ATj can be efficiently determined using BCj and ki.(2)
gkj and ATj cannot be learned from the broadcasts {BC1,…} or the personal keys {k1,…,kN} alone.(3)
For any revoked userUi¯∈R=U−Gj and any adversary AD, it is computationally infeasible to compute gkj and ATj, using the broadcast BCj and its secret keys.(4)
For any coalition of the revoked usersUi¯∈R=U−Gj and any adversary AD, it is computationally infeasible to compute gkjandATj, using the broadcast BCj and their secret keys.(5)
LetC be a coalition of any users Ui¯∈R=U−Gj, and let gkC−ATC be the set of all the group keys and authentication tokens they are authorized to access. Then, C cannot derive gkj and ATj corresponding to Gj, using the broadcasts, their secret keys, and gkC−ATC.(6)
D is self-healing if a user Ui∈Gj can derive gkj and ATj for any j<j′, using ki and BCj′.(7)
D provides message source authentication, if the legitimate users Ui∈Gj can use the tokens in ATj to authenticate the message source of an encryption Encgkjmsg.
Please note that the above property 5 implies and extends the forward secrecy and the backward secrecy in the previous works in the sense that we allow any coalition of illegitimate usersU−Gj∪AD, and there are no constraints on the users joining the group or being revoked from the legitimate group.


## 4.2. The Proposed Scheme

The scheme consists of four phases: initialization phase, group key distribution phase, group key recovery phase, and group communication with authentication phase.


### 4.2.1. Initialization Phase

GM sets up a systematic block code with a generator matrixMn,k as specified in Section 2, a keyed one-way hash function h1,, and a one-way hash function h2. GM publishes the parameters Mn,k, h1,, and h2. For each user Ui∈U, GM selects a secret key ki and securely distributes ki to Ui.


### 4.2.2. Group Key Distribution Phase

LetGj⊂U be the authorized user set for a session j∈T, where nj=Gj denotes the number of users in Gj. To simplify the following presentation, let us suppose Gj=U1,U2,…,Unj be the set of legitimate users for session j. GM selects a random group key gkj and a nonce rj and computes seedj,i0=h1ki,rj for each user Ui∈Gj. It computes seedj,is=h2sh1ki,rjwheres is the maximum number of messages transmitted by each user in one session and h2s denotes applying h2s times. gkj is used as the group key, while seedj,is being the authentication token for Ui∈Gj.GM preparesdj = d1,d2,…,dnj+1=(gkj,seedj,1s,…,seedj,njs) as the information to be broadcast and prepares the generator matrix M2nj+1,nj+1 as specified in the preliminaries. GM generates Cj=c1,…,cnj=Pnj×nj+1dj, where the parities are specified as follows:(3)cl=∑u=1nj+1gt−1u−1du,where1≤l≤nj.Finally, GM broadcastsBCj defined by equation (4). For self-healing, GM broadcasts the data defined by equation (5), where a window of p previous sessions is included; as our system does not limit the number of sessions it supports and can continuously run without a specified end, it is reasonable that the messages for long time ago are not interesting to the current entities; the selection of the window size p should depend on the scenarios and the application context. Please note that Vadlamudi–Vadlamudi’s scheme [27] needs to distribute the new generator matrix and the new hash function in each session, but our scheme does not need to redistribute the generator matrix and the one-way hash because each generator matrix in one session is just a subpart of the generator matrix specified in equation (1). In each session, the GM just uses one subpart of the matrix in equation (1). The GM and the authorized users can easily determine the subpart, based on nj=|Gj|:(4)BCj=Gj,rj,c1,…,cnj,(5)BCj−p,…,BCjfor a window ofp+1sessions.


### 4.2.3. Group Key Recovery Phase

When a userUi∈Gj receives the broadcast BCj, he prepares seedj,i0=h1ki,rj and seedj,is. With the recovered value of seedj,is, now the set of nj linear-independent equations in (2) has only nj unknown variables, and they can be solved by Ui, that is, Ui can recover all the secrets dj = d1,d2,…,dnj+1 = (gkj,seedj,1s,…,seedj,njs). This can be easily implemented, using the matrix multiplications.


### 4.2.4. Group Communication with Authentication Phase

Any legitimate userUi∈Gj can use the group key gkj to encrypt its message msg and successively use seedj,is−l, where l=1,…,s is a MAC (Message Authentication Code) key to generate the MAC.The encryption ENC and the message authentication code MAC are specified as follows:(6)mac=MACseedj,is−l,msg,ENC=EncgkjUi,msg,mac,seedj,is−l,where Ui broadcasts {ENC} in its lth encryption in session j.Any legitimate userUi∈Gj can use the group key to decrypt the encryption and verify the source by checking whether both the verification equations in (7) hold. If the verifications succeed, then Ui accepts the message msg and is convinced of the source of the message. It stores the authentication token seedj,is−l for verifying the message in the next encryption:(7)seedj,is−l+1=h2seedj,is−l,mac=MACseedj,is−l,msg.


## 4.2.1. Initialization Phase

GM sets up a systematic block code with a generator matrixMn,k as specified in Section 2, a keyed one-way hash function h1,, and a one-way hash function h2. GM publishes the parameters Mn,k, h1,, and h2. For each user Ui∈U, GM selects a secret key ki and securely distributes ki to Ui.


## 4.2.2. Group Key Distribution Phase

LetGj⊂U be the authorized user set for a session j∈T, where nj=Gj denotes the number of users in Gj. To simplify the following presentation, let us suppose Gj=U1,U2,…,Unj be the set of legitimate users for session j. GM selects a random group key gkj and a nonce rj and computes seedj,i0=h1ki,rj for each user Ui∈Gj. It computes seedj,is=h2sh1ki,rjwheres is the maximum number of messages transmitted by each user in one session and h2s denotes applying h2s times. gkj is used as the group key, while seedj,is being the authentication token for Ui∈Gj.GM preparesdj = d1,d2,…,dnj+1=(gkj,seedj,1s,…,seedj,njs) as the information to be broadcast and prepares the generator matrix M2nj+1,nj+1 as specified in the preliminaries. GM generates Cj=c1,…,cnj=Pnj×nj+1dj, where the parities are specified as follows:(3)cl=∑u=1nj+1gt−1u−1du,where1≤l≤nj.Finally, GM broadcastsBCj defined by equation (4). For self-healing, GM broadcasts the data defined by equation (5), where a window of p previous sessions is included; as our system does not limit the number of sessions it supports and can continuously run without a specified end, it is reasonable that the messages for long time ago are not interesting to the current entities; the selection of the window size p should depend on the scenarios and the application context. Please note that Vadlamudi–Vadlamudi’s scheme [27] needs to distribute the new generator matrix and the new hash function in each session, but our scheme does not need to redistribute the generator matrix and the one-way hash because each generator matrix in one session is just a subpart of the generator matrix specified in equation (1). In each session, the GM just uses one subpart of the matrix in equation (1). The GM and the authorized users can easily determine the subpart, based on nj=|Gj|:(4)BCj=Gj,rj,c1,…,cnj,(5)BCj−p,…,BCjfor a window ofp+1sessions.


## 4.2.3. Group Key Recovery Phase

When a userUi∈Gj receives the broadcast BCj, he prepares seedj,i0=h1ki,rj and seedj,is. With the recovered value of seedj,is, now the set of nj linear-independent equations in (2) has only nj unknown variables, and they can be solved by Ui, that is, Ui can recover all the secrets dj = d1,d2,…,dnj+1 = (gkj,seedj,1s,…,seedj,njs). This can be easily implemented, using the matrix multiplications.


## 4.2.4. Group Communication with Authentication Phase

Any legitimate userUi∈Gj can use the group key gkj to encrypt its message msg and successively use seedj,is−l, where l=1,…,s is a MAC (Message Authentication Code) key to generate the MAC.The encryption ENC and the message authentication code MAC are specified as follows:(6)mac=MACseedj,is−l,msg,ENC=EncgkjUi,msg,mac,seedj,is−l,where Ui broadcasts {ENC} in its lth encryption in session j.Any legitimate userUi∈Gj can use the group key to decrypt the encryption and verify the source by checking whether both the verification equations in (7) hold. If the verifications succeed, then Ui accepts the message msg and is convinced of the source of the message. It stores the authentication token seedj,is−l for verifying the message in the next encryption:(7)seedj,is−l+1=h2seedj,is−l,mac=MACseedj,is−l,msg.


## 5. Security Analysis and Verification

In this section, we prove that the proposed scheme satisfies the group key distribution privacy of Definition1 in Theorem 1 and the message source authentication of Definition 1 in Theorem 2.Theorem 1.
The proposed scheme satisfies the group key privacy of Definition1, if the one-way hash and the keyed one-way hash function are secure.Proof.
Since any single illegitimate user (including a revoked user) for sessionj is not stronger than the coalition of all illegitimate users in breaking the privacy, we directly prove the security against the coalition.
LetC be a coalition of any users Ui¯∈R=U−Gj, and let gkC−ATC be the set of all the group keys and authentication tokens they are authorized to access.
Now we assume that the coalition can derive the group keygkj, using their secret keys, the broadcasts, and gkC−ATC. Then, the set of nj equations in (2) will have only nj unknown variables {seedj,1s,…,seedj,njs}. As these equations are constructed as independent equations, the coalition can uniquely determine the values of these variables, that is, they can derive {seedj,1s,…,seedj,njs}, where seedj,is=h2sh1ki,rj and Ui∈Gj. It violates the security property of the one-way hash function and the keyed one-way hash function: (a) without the secret key ki, one cannot compute h1ki,rj no matter how many pairs {h1ki,rj′,rj′} with rj′≠rj he gets; (b) without the secret h1ki,rj, one cannot compute h2sh1ki,rj for s≥1. So the coalition cannot derive the group key.Theorem 2.
The proposed scheme provides the message source authentication if the MAC function and the one-way hashh2() are secure.Proof.
For each encryption in sessionj, the sender needs to prepare mac=MACseedj,is−l,msg and ENC=EncgkjUi,m˜,mac,seedj,is−l and broadcasts ENC. Any legitimate user Ui′∈Gj can use the group key to derive the message, mac and seedj,is−l. Then, Ui′ verifies whether the two equations, seedj,is−l+1=h2seedj,is−l and mac=MACseedj,is−l,msg, hold. As long as the MAC function and the one-way hash h2() are secure, it ensures the authentication of the message source.□
After the theorems, the security properties of our scheme can be analyzed from the following different perspectives.(i)
Only the authorized user can derive the group key and the authentication tokens.Given the public values in equations (2)–(4), we can see that (nj+1), the number of unknown symbols, is larger than the number of independent equations in (2). So, an adversary has no way to derive the secrets. On the contrary, any legitimate user Ui∈Gj can calculate one value of the information seedj,i=h1ki,rj and seedj,is. With this value seedj,is, now the number of independent equations equals the number of unknown values, and Ui can solve the equations and derive all the values dj = d1,d2,…,dnj+1 = (gkj,seedj,1s,…,seedj,njs).(ii)
Only the authorized user can decrypt the encryptions and validate the source of the messages.Since a legitimate userUi∈Gj can acquire the group key and tokens, dj = d1,d2,…,dnj+1 = (gkj,seedj,1s,…,seedj,njs), from the broadcast, he can decrypt the encryptions using the group key gkj. From the content {Ui,msg,mac,seedj,is−l}, Ui derives the message msg, the authentication token seedj,is−l, and mac. Using the token and mac, Ui can validate, using the verification equations in (7), the source of the message, as h2 is a one-way hash, and HMAC is applied on the new seed and the message content to have the MAC.(iii)
The self-healing property.From the broadcast in equation (5), any legitimate user can derive the group keys and the authentication tokens corresponding to those sessions he is authorized, even if he loses the connections in those sessions. In our scheme, a window of p previous sessions is included; the selection of the window size p should depend on the scenarios and the application context.(iv)
Anywise forward/backward secrecy.To derive the group key and authentication codes in a session, one should prepare at least one seed∈seedj,1s,…,seedj,njs. Assume a user Ui∈Gj is authorized in session j but not authorized in another session j′(j≠j′); of course, Ui can prepare the seedj,i=h1ki,rj and seedj,is in the authorized session j to solve equation (2). But, for session j′ where Ui is not belonging to Gj′, Ui has no way to get any value ∈(seedj′,1s,…,seedj′,nj′s) and cannot solve equation (2) for session j′. This limits Ui’s capacities of recovering the group keys and tokens in only those authorized sessions.(v)
Anywise collusion resistance.In our scheme, the only way to derive the group keys and tokens for sessionj is to prepare at least one seed ∈seedj,1s,…,seedj,njs. Fortunately, any collusion without the help of at least one authorized user in session j cannot derive any seed and the group key from the broadcast. This ensures the collusion resistance.


## 6. Performance Evaluations

We first summarize the functions of several related schemes in Table2. From the summarized table, we find that, even though all these schemes tackle the group key distribution challenges, the supported functions and the application scenarios of them are quite different; the differences in the application scenarios affect the design, the security properties, and the models very much. For example, the scheme [29] is designed for the pay-TV system where the group key updating is triggered by both its membership change and its subscription change, while the key updating of most of other schemes being triggered periodically or being triggered by membership change; the scenario also motivates its design of the hierarchical key structure; it does not need to consider the source authentication since there is only one message source in the pay-TV systems. The scheme [30] is designed for the P2P networks, where the group key management is partially distributed; even though the scheme might seem computationally efficient, we notice that the number of group member is predetermined, the number affects the initial public parameters, and the size of one single encryption expands linearly as the number increases. It is interesting that there are a group of schemes [32] that aim at providing the mutual-healing function which facilitates a node recover the lost keys from the group manager or from its neighbors. Therefore, to have a fair comparison among group key distribution schemes, we have to examine the application scenarios, the supported functions, and the performance.Table 2
Comparison of the functionalities of the related schemes.
SchemeNo. of revoked usersAuthorized groupRevoked users rejoining a later sessionSource authenticationSelf-healingOther key features[12, 13]Predetermined before deploymentNot flexibleNot allowedNot providedYesUS[14]Predetermined before deploymentNot flexibleNot allowedNot providedYesUS[3, 19]Predetermined before deploymentNot flexibleNot allowedNot providedYesCS[39]Predetermined before deploymentNot flexibleYes but with different identityNot providedYesCS[27]Not predeterminedFlexibleAllowedNot providedYesCS; GKUPMC[29]Not predeterminedFlexibleAllowedNot required1Not considerHKS; GKUMCSC.[30]Not predetermined but the number of group members is predeterminedFlexibleAllowedNot providedNot considerPDGKM; GKUMC; the size of the encryption expands linearly with the number of the members[32]Not predeterminedFlexibleAllowedNot providedMutual healing2GKUMC[31]Not predeterminedFlexibleAllowedNot providedNot considerGKUMC[26]Not predeterminedFlexibleAllowedNot providedYesGKUMC[21]PredeterminedNot flexibleNot allowedNot providedYesGKUMC[22]PredeterminedNot flexibleNot allowedNot providedYesGKUPMCOursNot predeterminedFlexibleAllowedProvidedYesGKUPMCIn a pay-TV system, there is only one message source. A node can recover the lost keys from the ground station and the neighbors. CS: computationally secure; US: unconditionally secure. GKUMC: Group Key Updating triggered by Membership Change; GKUPMC: Group Key Updating Periodically and triggered by Membership Change; GKUMCSC: Group Key Updating triggered by Membership Change and Subscription Change; HKS: Hierarchical Key Structure; PDGKM: Partially Distributed Group Key Management.In this paper, we focus on those systems which support flexible authorized group expression and flexible member-revoking condition, and a revoked-member could rejoin the system at a later session because such kinds of systems have wider application scenarios and have greater practical application potentials. The schemes [26, 27, 29, 31, 32] and our scheme have these flexible functions. Among the schemes, only our scheme provides the source authentication, which is very important in many applications.Now we evaluate the computational complexity and the communication complexity. A comparison table among several related schemes is given in Table3.Table 3
The comparisons of the computation/communication overhead of related schemes.
SchemeCommunication overhead of one single sessionCommunication overhead of self-healing ofw-sessionsGM’s computations in group key distributionUser’s computations in group key recoveryStorage of private data in a node[22]maxt+2v,n¯+3v+j+1Len ∼=(nm + m+1)LenForjth session: j+2JTh+t+j+2Tmul+JTenc+j+JTexp∼ = 3mTh+n+m+2Tmul+mTenc+2mTexp7Tmul+4Texp+1Tinv+3Th+Tdec2Len[21]t+1v+1Len+v+jLen ∼=((n+1)m+2m + 1)LenjTh+2jTdec+2nj+j+2Tmul+j+1Texp+TinvjTh+jTdec+6Tmul+j+3Texp+TinvLen[26]3lognLenlognTh+Tdec2m(1+1/2m−n/2logn−1)ThlognLen[31]7LenDoes not provide self-healing3 + 1TGCD1+Tinv+Tdiv3 Len[30]O(n′) broadcast ∼ = O(n′)LenO(n′) broadcast for one session of a n′-member batch join1∼ = O(n′)LenNot applicableO(n′) Tadd for a n′-member leave; O(n′) (Tmul+ Tadd) for a n′-member join2 Len[27](3n¯+1) Len + one generator matrix∼ = O(n¯2)Len∑j∈w−sessions3n¯+11matrix∼ = O(wn¯2)LenTmatrix_gen+Tmatrix_m+n¯Th∼ = O(n¯3.3737)TmulTmatrix_gen+Tmatrix_m+1Th∼ = O(n¯3.3737)Tmul1 LenOurs(2n¯+1) Len∑j∈w−sessions2Gj+1Len ∼ = O (wn¯) LenTmatrix_m+n¯(s+1)Th∼ = O(n¯2.3737)TmulTmatrix_m+(s+1)Th∼ = O(n¯2.3737)Tmul1 Len(1)n′ denotes the number of leaving members in a batch leave; n denotes the number of total members. n¯ denotes the number of members in one session; m denotes the maximum number of sessions; Len denotes the bit length for one scalar value such as one key and one identity; w denotes the number of sessions to recover the keys. (2) t denotes the maximum number of revoked users; v denotes the number of sessions in which there are users joining the group (v < j), where j is the index of the current session; Gj denotes the number of members in the jth session. (3) j denotes the jth session (could be replaced with O(m)); J denotes the number of sessions with joining users (could be replaced with O(m)), where m is the maximum number of sessions; Q denotes the number of neighbors around the request node. (4) Th denotes the computational cost for one hashing; Tmul denotes the cost for one modular multiplication; Tadd denotes the cost for one modular addition/subtraction; Tmatrix_m denotes the computational cost for one matrix multiplication, which is O(n2.3737)Tmul; Tmatrix_gen denotes the cost for one new matrix generation, which is O(n3.3737); Texp denotes the cost for one exponentiation operation; Tinv denotes the cost for one modulo inversion operation; Tdiv denotes the cost for one modulo division operation; Tη denotes the cost for one η() which is the group key broadcast message generation [30]; Ts denotes the cost for one asymmetric signature generation; Tv denotes the cost for one asymmetric signature verification; Te/Td denotes the cost for one asymmetric encryption/decryption; Tdec denotes the cost for one symmetric encryption/decryption; TGCD denotes the cost for one Greatest Common Divisor operation.


### 6.1. The Communication Complexity

The communication overheads are listed in the 2nd column and the 3rd column in Table 3, where the 2nd column lists the overheads for one group key updating session and the 3rd column lists the costs for a w-session recovery. For some schemes which do not provide the key updating for one single session, we merge the 2nd column and the 3rd column into one column in the table. The 6th column lists the secret storage space in a node. To simplify the comparison, we let Len denote the bit length for one key or one identity for all the schemes, despite the variations of the bit lengths in the corresponding schemes and scenarios. We use the symbol “∼ = ” to denote the asymptotic complexity which could further simplify the overhead estimation to capture the asymptotic complexity.From the table, we can see that the schemes [26, 31] require the less communication overheads for one single session; however, we should notice that it does not have significant value to examine each individual performance metric (such as Column 2, Column 3, and Column 6) because the schemes aim at quite different application scenarios and provide quite different functions. The schemes [27] and our scheme require moderate communication overheads, as their overheads are linear to the size of the number of the legitimate members in that session.Among the schemes, we have to emphasize the comparison between our scheme and Vadlamudi–Vadlamudi’s scheme [27] because the two schemes have the same application scenarios and they all adopt the coding-based mechanisms. In this regard, we note that Vadlamudi–Vadlamudi’s scheme [27] needs to distribute the generator matrices for each session; but our scheme does not need to renew the generator matrices because each generator matrix in one session is just a subpart of the generator matrix specified in equation (1); the GM and the authorized users can easily determine the subparts, based on the number nj.The communication overhead of the GM’s broadcast of our scheme for sessionj consists of Gj, one random nonce, and nj parities, where nj is the number of authorized users in session j. It sums up to 2nj + 1 numbers in equation (4). For the self-healing property in equation (5), it totally sums up to ∑t∈w−session2nt+1 numbers, which is of order O(wn¯), where w denotes the number of sessions to recover and n¯ denotes the number of members in a session. The communication overhead of one encryption in the group communication with the authentication phase consists of one encryption of four numbers in equation (6). Vadlamudi–Vadlamudi’s scheme [27] for session j only is 2nj2+5nj+2 numbers; for the self-healing broadcasting of Vadlamudi–Vadlamudi’s scheme, it is ∑t=1∼j2nt2+5nt+2 numbers, which is of order O(wn¯2).


#### 6.1.1. The Computational Complexity of Group Key Distribution/Recovery

The Columns 4 and 5, respectively, list the computational overheads of the GM and one member for recovering the group keys. In the table, the schemes [26, 30, 31] require the less computational overheads for recovering the keys; however, we note two points: (1) there exist many implicit communication overheads for securely transmitting membership authorization/authentication messages in [30]; (2) it does not have significant value to only examine these performance metrics individually (like Column 4 and Column 5), as the scenarios and the supported functions of these schemes vary a lot. Among the related schemes, our scheme and Vadlamudi–Vadlamudi’s scheme [27] have the same scenarios and adopt the same coding mechanisms. We, therefore, emphasize on the two schemes in the following comparison.We first evaluate that of our scheme. Both the operations in performing the encryptions/decryptions of group keys and tokens in equation (2) and in the group key recovery phase involve the computations of seedj,is and the matrix multiplications. To prepare njseedj,is, it requires njs+1 hashes: O(njs) hashes, where nj is the number of authorized users in that session and s is the specified maximum number of encryptions in one session. To calculate the parities in equation (2), the complexity of matrix multiplication is O(n¯2.3737) [38]. To derive the group key and tokens in one session, Ui performs s+1 hashes and one matrix multiplication. For each encryption/decryption and the validation of the source of a message in the group communication with the authentication phase, one performs one encryption/decryption and one hash operation.Vadlamudi–Vadlamudi’s work [27] specifies two possible implementations for the matrix preparation and the transmission, where one implementation reduces the cost of the GM, at the additional cost of the receivers. Since both the two implementations demand higher cost than our scheme, here we only consider the case of which the GM prepares the whole matrix by itself; and, we focus on estimating the asymptotic notation of the complexities without being caught in lengthy and tedious computations. This highlights the comparison of the asymptotic complexities. For Vadlamudi–Vadlamudi’s scheme, the GM additionally needs the matrix preparation in each session, which roughly equals n times the cost of the corresponding matrix multiplication. So, it totally needs O(n¯3.3737) operations. In a short summary, our scheme greatly improves both the communication overheads and the computational complexity, compared to its counterpart [27].


## 6.1. The Communication Complexity

The communication overheads are listed in the 2nd column and the 3rd column in Table 3, where the 2nd column lists the overheads for one group key updating session and the 3rd column lists the costs for a w-session recovery. For some schemes which do not provide the key updating for one single session, we merge the 2nd column and the 3rd column into one column in the table. The 6th column lists the secret storage space in a node. To simplify the comparison, we let Len denote the bit length for one key or one identity for all the schemes, despite the variations of the bit lengths in the corresponding schemes and scenarios. We use the symbol “∼ = ” to denote the asymptotic complexity which could further simplify the overhead estimation to capture the asymptotic complexity.From the table, we can see that the schemes [26, 31] require the less communication overheads for one single session; however, we should notice that it does not have significant value to examine each individual performance metric (such as Column 2, Column 3, and Column 6) because the schemes aim at quite different application scenarios and provide quite different functions. The schemes [27] and our scheme require moderate communication overheads, as their overheads are linear to the size of the number of the legitimate members in that session.Among the schemes, we have to emphasize the comparison between our scheme and Vadlamudi–Vadlamudi’s scheme [27] because the two schemes have the same application scenarios and they all adopt the coding-based mechanisms. In this regard, we note that Vadlamudi–Vadlamudi’s scheme [27] needs to distribute the generator matrices for each session; but our scheme does not need to renew the generator matrices because each generator matrix in one session is just a subpart of the generator matrix specified in equation (1); the GM and the authorized users can easily determine the subparts, based on the number nj.The communication overhead of the GM’s broadcast of our scheme for sessionj consists of Gj, one random nonce, and nj parities, where nj is the number of authorized users in session j. It sums up to 2nj + 1 numbers in equation (4). For the self-healing property in equation (5), it totally sums up to ∑t∈w−session2nt+1 numbers, which is of order O(wn¯), where w denotes the number of sessions to recover and n¯ denotes the number of members in a session. The communication overhead of one encryption in the group communication with the authentication phase consists of one encryption of four numbers in equation (6). Vadlamudi–Vadlamudi’s scheme [27] for session j only is 2nj2+5nj+2 numbers; for the self-healing broadcasting of Vadlamudi–Vadlamudi’s scheme, it is ∑t=1∼j2nt2+5nt+2 numbers, which is of order O(wn¯2).


### 6.1.1. The Computational Complexity of Group Key Distribution/Recovery

The Columns 4 and 5, respectively, list the computational overheads of the GM and one member for recovering the group keys. In the table, the schemes [26, 30, 31] require the less computational overheads for recovering the keys; however, we note two points: (1) there exist many implicit communication overheads for securely transmitting membership authorization/authentication messages in [30]; (2) it does not have significant value to only examine these performance metrics individually (like Column 4 and Column 5), as the scenarios and the supported functions of these schemes vary a lot. Among the related schemes, our scheme and Vadlamudi–Vadlamudi’s scheme [27] have the same scenarios and adopt the same coding mechanisms. We, therefore, emphasize on the two schemes in the following comparison.We first evaluate that of our scheme. Both the operations in performing the encryptions/decryptions of group keys and tokens in equation (2) and in the group key recovery phase involve the computations of seedj,is and the matrix multiplications. To prepare njseedj,is, it requires njs+1 hashes: O(njs) hashes, where nj is the number of authorized users in that session and s is the specified maximum number of encryptions in one session. To calculate the parities in equation (2), the complexity of matrix multiplication is O(n¯2.3737) [38]. To derive the group key and tokens in one session, Ui performs s+1 hashes and one matrix multiplication. For each encryption/decryption and the validation of the source of a message in the group communication with the authentication phase, one performs one encryption/decryption and one hash operation.Vadlamudi–Vadlamudi’s work [27] specifies two possible implementations for the matrix preparation and the transmission, where one implementation reduces the cost of the GM, at the additional cost of the receivers. Since both the two implementations demand higher cost than our scheme, here we only consider the case of which the GM prepares the whole matrix by itself; and, we focus on estimating the asymptotic notation of the complexities without being caught in lengthy and tedious computations. This highlights the comparison of the asymptotic complexities. For Vadlamudi–Vadlamudi’s scheme, the GM additionally needs the matrix preparation in each session, which roughly equals n times the cost of the corresponding matrix multiplication. So, it totally needs O(n¯3.3737) operations. In a short summary, our scheme greatly improves both the communication overheads and the computational complexity, compared to its counterpart [27].


## 6.1.1. The Computational Complexity of Group Key Distribution/Recovery

The Columns 4 and 5, respectively, list the computational overheads of the GM and one member for recovering the group keys. In the table, the schemes [26, 30, 31] require the less computational overheads for recovering the keys; however, we note two points: (1) there exist many implicit communication overheads for securely transmitting membership authorization/authentication messages in [30]; (2) it does not have significant value to only examine these performance metrics individually (like Column 4 and Column 5), as the scenarios and the supported functions of these schemes vary a lot. Among the related schemes, our scheme and Vadlamudi–Vadlamudi’s scheme [27] have the same scenarios and adopt the same coding mechanisms. We, therefore, emphasize on the two schemes in the following comparison.We first evaluate that of our scheme. Both the operations in performing the encryptions/decryptions of group keys and tokens in equation (2) and in the group key recovery phase involve the computations of seedj,is and the matrix multiplications. To prepare njseedj,is, it requires njs+1 hashes: O(njs) hashes, where nj is the number of authorized users in that session and s is the specified maximum number of encryptions in one session. To calculate the parities in equation (2), the complexity of matrix multiplication is O(n¯2.3737) [38]. To derive the group key and tokens in one session, Ui performs s+1 hashes and one matrix multiplication. For each encryption/decryption and the validation of the source of a message in the group communication with the authentication phase, one performs one encryption/decryption and one hash operation.Vadlamudi–Vadlamudi’s work [27] specifies two possible implementations for the matrix preparation and the transmission, where one implementation reduces the cost of the GM, at the additional cost of the receivers. Since both the two implementations demand higher cost than our scheme, here we only consider the case of which the GM prepares the whole matrix by itself; and, we focus on estimating the asymptotic notation of the complexities without being caught in lengthy and tedious computations. This highlights the comparison of the asymptotic complexities. For Vadlamudi–Vadlamudi’s scheme, the GM additionally needs the matrix preparation in each session, which roughly equals n times the cost of the corresponding matrix multiplication. So, it totally needs O(n¯3.3737) operations. In a short summary, our scheme greatly improves both the communication overheads and the computational complexity, compared to its counterpart [27].


## 7. Conclusions

In this paper, we have proposed a new self-healing group key distribution which facilitates message source authentication, based on the systematic block codes. The contributions of this submission are listed as follows. (1) To the best of our knowledge, this is the first codes-based self-healing group key distribution scheme that provides message source authentication. (2) The determination of the authorized-user set is flexible; that is, any user is allowed to join the authorized set at any sessions and is allowed to leave the set at any sessions. (3) The communication overhead is greatly reduced, by eliminating the transmission of the generator matrix. (4) The computation is highly efficient, as it only involves one matrix multiplication and several hashing operations. (5) The scheme provides forward/backward secrecy. These merits make the proposed scheme much attractive and practical than its counterparts in many application scenarios.



---

*Source: 2942568-2021-06-30.xml*