# A novel authenticated group key distribution scheme.

1. IntroductionDistributing a group key to all group members is a complicated task especially in a dynamic group where members may join and leave at any time. When any member joins/leaves the group, it needs to update and redistribute the group key to all group members, in order to ensure that a leaving member cannot learn about the new group keys after he leaves the group and a new member cannot learn about the previous group keys after he joins the group. In last decades, group key management had received much attention and was always a research focus. Therefore, lots of group key management schemes have been proposed. Generally speaking, these schemes can be roughly classified into three categories: a centralized key distribution scheme, a distributed key agreement scheme, and a hybrid group key management scheme.

In centralized key distribution schemes [1-9], all group members trust a centralized key management center, which generates and distributes the group keys and is also responsible to update the group key when group members join or leave the group. One of the most known centralized key distribution schemes was the logical key hierarchy (LKH) [1,2], which reduced the rekey messages and encryption operations from O(N) to O(logN), where N was the number of group members. An improvement in the binary key tree was the one- way function tree (OFT) [3] in which an internal node key was generated from its children node keys. In comparison with the top-down LKH method, the bottom-up OFT algorithm approximately halved the number of bits that needed to be broadcast to members in order to rekey after a member was added or evicted. Furthermore, Perrig et al. [4] proposed an Efficient Large-group Key (ELK) distribution scheme. It was similar to OFT in the sense that intermediate keys were generated from its children, but pseudo-random functions (PRFs) were used rather than one-way functions, thus it further reduced the size of rekey messages for each member join from logN to 0. However, for a member join, the manager had to re-compute all auxiliary keys of the key tree.

In distributed key agreement schemes [10-21], all group members contribute to the generation of group keys and are equally responsible for the rekeying and distribution of group keys. In 1976, Diffie and Hellman [10] first described a method for two parties to agree upon a shared key in such a way the key would be unavailable to eavesdroppers. Thereafter, there were many distributed key agreement schemes, where most distributed key agreement schemes were the natural generalizations of the DH key agreement scheme. Well known schemes among these were perhaps the works of Ingemarsson et al. [11], Burmester and Desmedt [12], Steiner et al. [13], Joux et al. [14] and Kim et al. [15]

In hybrid group key management schemes [22-26], the authors make the best use of the individual advantages of both the centralized key distribution scheme and the distributed key agreement scheme. For example, Kwak et al. [25] presented a hybrid group key management scheme, which combined the LKH [1,2] and the tree-based group Diffie-Hellman (TGDH) schemes [15], and thus avoided the single point of failure problems of the LKH with much more enhanced performance than the TGDH.

In addition, there were also some novel group key management schemes for emerging networks. For example, in 2011, N.T.T. Huyen, et al. [27] presented two approaches for the polynomical pre-distribution scheme by exploiting the signal range and the deployment error, which are especially suitable for sensor networks. In 2013, to overcome the high frequency of group rekeying, D.H. Je et al. [28] proposed a novel group key management scheme, which is very suitable for vehicle networks. Above all, their proposed subscription- period-aware key management scheme can greatly reduce the communication, computation, and storage complexity in multicast group rekeying from O(N) to O(1), where Nis the number of vehicles in a single group rekeying process.

In this paper, we mainly focus on the centralized key distribution schemes, which are more suitable for a large and dynamic multicast group due to low computation and communication costs. In early proposed group key schemes, the main secure goal is to protect the confidentiality of a broadcast key or re-key message, but lack of authentication. So these schemes simplify the security problem by assuming a passive adversary. To protect against active adversaries, most existed schemes can be transformed to the corresponding authenticated group key schemes using public key cryptographic techniques as the compiler of Katz and Yung [16]. However, the management of the public keys in a large and dynamic group is also a heavy burden. Thus, to seek an efficient authenticated group key distribution scheme without using public key cryptographic techniques becomes a very significant work in secure group communications.

In this paper, we present a novel authenticated group key distribution scheme for large and dynamic multicast groups without employing traditional symmetric and asymmetric cryptographic techniques. The security of our scheme is mainly based on the basic theories for solving linear equations. Compared with other centralized key distribution schemes of Key trees, or hierarchical key structures, our scheme has four highlighted advantages: 1) Our proposed scheme is not based on any difficult assumption; 2) When any group member joins/leaves the group, the number of auxiliary secrets (or keys) required to be updated is O(1) instead of O(logN); 3) In order to obtain the group key, the computation cost of each group member is very low because it only needs to compute one inner product instead of other complex cryptographic operations; 4) It can provide group key authentication without using encryption and signature techniques.

2. Preliminaries

2.1 The secure goals of group key management

Referring to the literatures [4,9], we first review four secure goals of group key management: Group Key Confidentiality, Forward Secrecy, Backward Secrecy and Group Key Authentication.

1. Group Key Confidentiality is to protect the group key such that it can only be recovered by authorized group members; but not by any unauthorized user.

2. Forward Secrecy is to guarantee that a passive adversary who knows a contiguous subset of old group keys cannot discover subsequent group keys. This property ensures that a member cannot learn about the new group keys after he leaves the group.

3. Backward Secrecy is to guarantee that a passive adversary who knows a subset of group keys cannot discover preceding group keys. This property ensures that a new member cannot learn about the previous group keys after he joins the group.

4. Group key authentication is to provide assurance to authorized group members that the group key is distributed by GKGC; but not by an active attacker.

When any group member joins/leaves a group, obviously it needs to execute a rekeying (updating group key) procedure in order to maintain the forward secrecy and backward secrecy.

2.2 The basic theories for solving linear equations

There are lots of basic theories involved in solving linear equations. In the following section, we only introduce two theorems related to this paper.

Theorem 1. The necessary and sufficient condition for the solvability of linear equations A[??] = [??] is that the rank of the coefficient matrix A is equal to that of the augmented matrix [bar.A]. That is, r(A) = r([bar.A]). Where A is an m x n matrix, [??] an n- dimensional vector and [??] an m-dimensional vector.

Theorem 2. Furthermore, for the solvable linear equations A[??] = [??], if r(A) = n, there exists a unique solution; if r(A) < n, there exist infinitely many solutions. Furthermore, for the solvable linear equations A[??] = [??] over [Z.sub.p], if r(A) < n, there exist at least p solutions, where p is a large prime integer and [Z.sub.p] = {0,1,2, ..., p - 1}.

3. Proposed Scheme

3.1 Model

Our model is a hierarchical tree structure, as shown in Fig. 1. In our model, a large group is divided into several subgroups which are independent of each other. Each subgroup is managed by a subgroup key manager (SGKM), and then all SGKMs are managed by a group key generator center (GKGC), which is responsible for generating, distributing and updating group keys for secure communications by all group members.

The hierarchical model described above is especially suitable for secure multicast communications in some "client-server" networks, such as e-commerce systems, where the GKGC is the electronic trade center or server center, each SGKM is a region agent, and all members are clients. In order to decrypt the encryption messages broadcasted by the center, all authorized clients (i.e., members) need to subscribe to a shared group key with their respective region agents in advance.

3.2 Group Initialization

In the following protocols, we assume that the GKGC manages t SGKMs and each SGKM, has [s.sub.i], members (1 [less than or equal to] i [less than or equal to] t), as shown in Fig. 1. Group initialization consists of two main processes: the Initial Parameters Generation, and the SGKMs and Members Registration. The detailed description is as follows:

The Initial Parameters Generation. The GKGC first selects a large prime p and a secure one-way hash function H (*) and announces them to all group members publicly. Then, he privately generates an m x n matrix A (1 < m [less than or equal to] n and n > t) and another m-dimensional column vector [??] over [Z.sub.p], such that there exist at least p solutions of the linear equations A[??] = [??] over Zp (i.e., it implies r(A) < n). The detailed algorithm of generating the matrix A and vector [??] is as follows.

Algorithm of generating A and [??] 1. Randomly generate an m x n matrix A over [Z.sub.p]. 2. Verify that r(A) < n using Gaussian elimination method, or else goto 1 and restart. 3. Randomly generate an n-dimensional vector [[??].sub.0] over [Z.sub.p]. 4. Compute [??] = A[[??].sub.0]. //It guarantees that r(A) = r([bar.A]) in A[??] = [??]. 5. Output (A and [??]). // Therefore, there exist at least p solutions of the linear equations A[??] = [??] over [Z.sub.p].

Similarly, each SGKM, (1 [less than or equal to] i [less than or equal to] t) privately generates an [m.sub.i] x [n.sub.i] matrix [A.sub.i] (1 < [m.sub.i] [less than or equal to] [n.sub.i] and [n.sub.i] > [s.sub.i]) and another [m.sub.i]-dimensional column vector [[??].sub.i] over [Z.sub.p], such that there exist at least p solutions of the linear equations [A.sub.i] [??] = [[??].sub.i] over [Z.sub.p].

The SGKMs and Members Registration. Furthermore, each SGKMis required to register at the GKGC as a legal region agent. During the SGKMs registration, the GKGC generates a unique n-dimensional column vector [[??].sub.i] for each [SGKM.sub.i] (1 [less than or equal to] i [less than or equal to] t), such that [[??].sub.i] satisfies the equation of A[[??].sub.i] = [??] (that is, [[??].sub.i] is a solution of the linear equations, A[??] = [??]), and then secretly sends [[??].sub.i] to the [SGKM.sub.i] as his auxiliary secret. Similarly, each member is required to register at their respective [SGKM.sub.i] for subscribing the key distribution service. During the members registration, the [SGKM.sub.i] generates a unique [n.sub.i]-dimensional column vector [[??].sub.i,j] for each member [U.sub.i,j] (1 [less than or equal to] j [less than or equal to] [s.sub.i]), such that [[??].sub.i,j] satisfies the equation of [A.sub.i] [[??].sub.i,j] = [[??].sub.i] (that is, [[??].sub.i,j] is a solution of the linear equations, [A.sub.i] [??] = [[??].sub.i]), and then secretly sends [[??].sub.i,j] to the member [U.sub.i,j] as his/her auxiliary secret.

3.3 The Group Key Generation and Distribution

The group key generation and distribution protocol (called GKG&D protocol hereafter) includes the following five steps:

Step 1. The GKGC randomly selects an m-dimensional column vector [??] over [Z.sub.p] and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then the GKGC broadcasts [??] to all SGKMs.

Step 2. Furthermore, the GKGC computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and H (gk). Here [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the inner product of the vectors [??] and [??], that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [[??].sup.T] = ([k.sub.1], [k.sub.2], ..., [k.sub.m]) and [[??].sup.T] = ([y.sub.1], [y.sub.2], ..., [y.sub.m]). Suppose that there is a public server at the GKGC, which is utilized to publish H (gk) timely. In addition, we assume that all SGKMs and group members can only browse H (gk) from the public server, but not modify it.

Step 3. Subsequently, each [SGKM.sub.i] computes g[k.sub.i] = [[??].sup.T] x [[??].sub.i] and verifies its authenticity by the equation of H(g[k.sub.i]) [??] H(gk). If the equation is true (i.e., g[k.sub.i] = gk), the [SGKM.sub.i] randomly selects [m.sub.i] - 1 integers, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], over [Z.sub.p], and then computes and further gets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by the equation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; or else, this process ends up in failure.

Step 4. Each [SGKM.sub.i] computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. and broadcasts r to his/her all members.

Step 5. After receiving the broadcasted messages from the [SGKM.sub.i], each member [U.sub.i,j] (1 [less than or equal to] j [less than or equal to] [s.sub.i]) computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and verifies whether the equation of H(u[k.sub.i,j]) [??] H(gk) is correct. If it is correct, then he/she will believe that the shared group key is u[k.sub.i,j] indeed (i.e., u[k.sub.i,j] = gk); or else, this process ends up in failure.

The correctness proofs:

Suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

In addition,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

By Eqs. 1 and 2, it is obvious that g[k.sub.i] = gk for i = 1 to t, that is, g[k.sub.1] = g[k.sub.2] = ... = g[k.sub.t] = gk. Similarly, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Thus, there must exist [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Please note that the above computations are all over [Z.sub.p].

To sum up, u[k.sub.i,j] = gk for j = 1 to [s.sub.i] and i = 1 to t. That is, all group members obtain a shared group key [g.sub.k].

3.4 Rekeying

In order to maintain the forward secrecy and backward secrecy, a rekeying procedure must be executed when the GKGC withdraws/adds any SGKM or any member joins/leaves the group.

Withdrawing any SGKMs. Suppose that the GKGC wants to withdraw the jth SGKM (i.e., [SGKM.sub.j], 1 [less than or equal to] j [less than or equal to] t). Then the group key must be updated. The rekeying procedure includes two steps as follows:

In the first step, the GKGC needs to renews his auxiliary secrets A and [??]. He first founds the linear equations as Eq. 5 by all [[??].sub.i] s of the remaining SGKMs, and then recomputes A and [??] as new unknowns by using Gaussian elimination method in Eq.5. Please note that [[??].sub.i], [[??].sub.2], ..., [[??].sub.j-1], [[??].sub.j+1], ..., [[??].sub.t] are t-1 known vectors in the following linear equations.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

Since the matrix A is m x n dimension and the vector [??] is m dimension, obviously there exist m x n + m unknown variables while there are only (t - 1) x m equations in Eq.5. Thus there must be infinitely many solutions of A and [??] in Eq.5 because the number of unknown values is far more than that of equations. Furthermore, the GKGC computes a new particular solution of A and [??] by Eq.5, which is different from the old solution, such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (i [not equal to] j) but [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the second step, the GKGC regenerates the group key gk based on the new auxiliary secrets A and [??] by executing the GKG&D protocol again. That is, the GKGC randomly selects a new vector [??] over [Z.sub.p], recomputes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], broadcasts [??] to all remaining SGKMs, and renews H (gk) in the public server. Furthermore, each remaining [SGKM.sub.i] computes and verifies their respective subgroup key g[k.sub.i] by the new broadcasted message from the GKGC. At last, all members obtain the new group key gk by the same method as the initial group key generation and distribution in the GKG&D protocol.

Adding a new SGKM. Suppose that the new SGKM is marked as [SGKM.sub.t+1]. Similarly, the group key must be updated. Since t < n, so t + 1 [less than or equal to] n. After adding a new SGKM, it still satisfies the property that the column number of the matrix A is greater than or equal to that of the SGMKs. So, when a new [SGKM.sub.t+1] requests to join the group, the GKGC only needs to generate another unique [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and secretly sends it to the [SGKM.sub.t+1] while other secret [[??].sub.i] s are unaltered. Then the GKGC again executes the GKG&D protocol to update the group key.

Please note that it must satisfy t [less than or equal to] n in this dynamic protocol in order to prevent the collusion attacks (see Theorem. 5). In case of t = n, if adding a new SGMK, it needs to regenerate A by using the similar method as withdrawing any SGMKs, such that the column number of the matrix A is greater than that of the SGMKs.

Removing any member: Suppose that a member [U.sub.i,j] of the [SGKM.sub.i] requests to leave the group. After confirming his leaving, the [SGKM.sub.i] needs to renew old secrets {[A.sub.i], [[??].sub.i]} in order to protect backward secrecy. Similarly, the [SGKM.sub.i] first creates the similar linear equations like Eq.5 by the secrets ([[??].sub.i,j] s) of all remaining members and then recomputes {[A.sub.i], [[??].sub.i]} as unknowns. Furthermore, the [SGKM.sub.i] requests the GKGC to update the group key due to his member leaving. At last, the GKGC again executes the GKG&D protocol to renew the group key.

Adding a new member: Suppose that a new member, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], requests to join the subgroup of the [SGKM.sub.i]. After receiving a join request message of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the [SGKM.sub.i] first performs the register procedure to verify the identity of new member. If the [SGKM.sub.i] agrees his join request, the [SGKM.sub.i] generates another unique [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and secretly sends it to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, the [SGKM.sub.i] again requests the GKGC to update the group key due to his new member joining. At last, the GKGC executes the GKG&D protocol to renew the group key.

In addition, in order to reduce the overhead of high frequent joins and leaves, we can consider rekeying in a batch as the method in the literature [5].

4. Analysis

4.1 Security Analysis

We have proved the correctness of the above proposed scheme. Furthermore, we focus on their security analysis, which sees Theorem 3, 4 and 5 in detail.

Theorem 3. The proposed scheme achieves four security goals of group key management: 1) Group Key Confidentiality, 2) Forward Secrecy, 3) Backward Secrecy, 4) Group key authentication.

Proof. 1) Group Key Confidentiality is guaranteed by the security of the public message H(gk) and the broadcast message [??]. Here, we assume that H(*) is a secure one- way hash function. Therefore, any unauthorized users cannot obtain the group key gk only from the public message H (gk). Similarly, for any unauthorized users, he/she cannot get the group key gk only from the broadcast message [??], because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [[??].sub.i] and [??] are unknown, and [??] is randomly and secretly generated by the GKGC. 2) Forward Secrecy is guaranteed by the rekeying procedure. Whenever an SGKM, or a member, leaving the group, it needs to update not only the group key but also the auxiliary secrets {A, [??]}, or {[A.sub.i], [[??].sub.i]}. Thus, the leaving SGKM or member cannot learn about new group keys after he leaves the group since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. 3) Backward Secrecy is guaranteed by the fact that the group key is always updated whenever new SGKM or member joining the group. 4) Key Authentication is provided through the value of H (gk) generated by the GKGC who owns the secrets {A, [??]}. For any active attacker, it is impossible to forge a broadcast vector [[??].sup.*] without the secrets A and [??], such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (i.e., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all j. Please note that H (gk) is published at the public server of the GKGC, and can only be modified by the GKGC.

Theorem 4 (Outsider attack). Our scheme is secure against outsider attack.

Proof. 1) Firstly, we assume that an outsider active attacker who impersonates the GKGC to broadcast a forged key or rekeying message in order to share a group key with all group members. As the above analysis in Theorem 3, it is impossible for the attacker to successfully pass the authenticity verification (i.e., for a forged [[??].sup.*], obviously it must be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] because he can't modified H(gk) at the public server of the GKGC. Secondly, we assume that an outsider active attacker who impersonates a group member for requesting a group key service. In our scheme, each member needs to beforehand subscribe the group key service, and then obtains the respective secret [[??].sub.i,j] which is shared with the manager, [SGKM.sub.i]. Thus, legal group key service requests from group members can be authenticated by their respective secret [[??].sub.i,j]. At last, the attacker cannot obtain any secret information of the group key direct from the broadcasted key messages due to the confidentiality of group keys analyzed above in Theorem 3. 2) In addition, the value of [??] are obviously different for every rekeying process because [??] is randomly generated, and thus our scheme is secure against the replay attack. Therefore, our scheme is secure against outsider attack.

Theorem 5 (Insider attack). Our scheme is secure against insider attack.

Proof. For each [SGMK.sub.i], he only knows his secret vector [[??].sub.i]. By his secret vector [[??].sub.i] and the broadcasted vector [??], obviously, [SGMK.sub.i] can obtain the value of g[k.sub.i] by computing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which is the shared group key (i.e., g[k.sub.i] = gk). However, he cannot get any secret information about the matrix A and the vector [??], because [[??].sup.T] = ([k.sub.1], [k.sub.2], ..., [k.sub.m]) is randomly and secretly selected by the GKGC. Similarly, each member cannot obtain any secret information about the matrix [A.sub.i] and the vector [[??].sub.i]. Furthermore, our scheme is secure against the collusion attacks of the insider SGKMs or members. Especially, we assume that all t SGKMs try to get the secrets of the GKGC (i.e., A and [??]) with colluding each other. In order to achieve this aim, they collude to found the following equations by their respective secret [[??].sub.i] s:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

However, for these colluding SGKMs, there are m x n + m unknown variables while there are only t x m equations (t [less than or equal to] n) in Eq.6. Thus, they do not obtain any secret information of A and [??] only from Eq.6 based on the basic theories for solving linear equations. Similarly, all subgroup members cannot get any secret information about [A.sub.i] and [[??].sub.i] yet. In fact, even if all SGKMs and all group members collude to perform this attack they cannot obtain the secrets of the GKGC, and furthermore they cannot impersonate the GKGC to authorize a new SGKM or update group keys.

4.2 Performance Analysis

By Theorem 5, there are at most n SGKMs in our proposed scheme in order to resist the collusion attacks of all SGKMs. In the following section, we assume that there are just n SGKMs in a group and each SGKM lso has n group members. Thus, there are total [n.sup.2] group members in a group.

In our proposed scheme, whenever a member joins the group, the [SGKM.sub.i] only needs to generate new member's secret [[??].sub.i,j] based on his secret linear equations, and further requests the GKGC to update the group key. Whenever a member leaves the group, the SGKM, only needs to renew his auxiliary secret ([A.sub.i], [[??].sub.i]) based on the known linear equations, and further requests the GKGC to update the group key. In the updating the group key (i.e., GKG&D) procedure, it only takes one multiplication of the vector and the matrix for the GKGC, two inner products for the [SGKM.sub.i]and one inner product for each member, respectively, instead of other complex cryptographic operations. Table 1 shows the main computation costs of LKH[1,2], OFT[3], ELK[4], HL[9] and our proposed scheme, where E, D, R, H, F, P, M, S denote the computation costs of encryption, decryption, random key generation, hashing, pseudo-random function, the N-degree interpolating polynomial, scalar multiplication and a particular solution of the linear equations, respectively. From Table 1, the most complex computation of our scheme is to solve a particular solution of the linear equations. Please note that it is not to compute all general solutions. As we know, it is easier to compute a particular solution than the general solution. Compared with other group key management schemes, obviously the computation costs of our scheme are lower, especially for group members.

Furthermore, in our proposed scheme, for GKGC, the communication cost is mainly used to broadcast key or rekeying. The size of the broadcasted key or rekeying message (mainly including an n-dimensional vector [??]) is nL, where the constant L is the size of the group key. In addition, each SGKM needs to broadcast an nL-size message to his group members in order to transfer the group key. For the storage cost, it involves three kinds of participants: GKGC, SGKM and group member in our scheme. For GKGC, SGKM and group member, it needs to store {A, [??] and all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and all [[??].sub.i,j] s}, and {[[??].sub.i,j]}, respectively. The detailed comparisons are listed in Table 2. In addition, please note that we can let m = 2 (1 < m [less than or equal to] n) to reduce the storage cost.

In addition, the proposed scheme can be easily and naturally extended into the single-level and multi-level architecture, as shown in Fig. 2 and Fig. 3, respectively. In Fig. 2, the GKGC directly utilize a linear equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to distribute the group keys to all group members. As the literature [9], the single-level architecture is only suitable for a group with a small group size. Assume that there are N group members in Fig. 2. Then the GKGC needs to broadcast a message containing N elements to all group members, which is lower than the HL scheme [9] (including N points). Especially, our scheme has better computation complexity than their scheme because each member only needs to compute N scalar multiplications (i.e., one inner product) instead of an N-degree interpolating polynomial. In Fig. 3, each internal node uses a secret linear equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to transfer the group key message from his parent node to his all child nodes, where the internal nodes can also be group members (i.e., group members play the part of the internal nodes). When any group member or internal node joins/leaves the group, the number of auxiliary secrets required to be updated in the secret tree is O(1) instead of O(log N), which is just required in the key tree methods, such as LKH, OFT and ELK.

Furthermore, in order to extend more group members, we may first build multiple groups managed by different GKGCs using the method proposed above, respectively, and further combine these groups into a larger group using a well-known distribution key agreement scheme (see Fig. 4), such as BD [12], TDH [14] and TGDH [15]. Thus it becomes a hybrid group key management scheme. In this hybrid scheme, all GKGCs first agree a group key using a distribution key agreement scheme and then propagate it to their respective group members using the proposed distribution method above.

5. Conclusion

We have presented an authenticated group key management scheme, which is divided into two or multiple levels to achieve it based on the basic theories for solving linear equations. This scheme is suitable for secure multicast communications in some client- server networks due to its higher efficiency, flexibility and adaptability. Especially, our scheme has some good advantages as follows.

1) For the GKGC, when adding/removing any group member, he does not need to do anything else except updating the group key. Furthermore, when updating the group key it only needs to broadcast new group key information to all SGKMs. In addition, even if adding/removing any SGKM it is also easy to implement it because the most complex computation is to solve a particular solution of the linear equations, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2) For the SGKMs, it is very easy to recover the group keys, and further it only needs to broadcast different subgroup key information to their respective members when transferring the group key. In addition, when adding/removing any SGKM it does not need to update the remaining SGKMs' auxiliary secrets (i.e., [[??].sub.i] s).

3) For group members, it takes very low computation cost to recover the group key because it only needs to compute an inner product instead of other complex cryptographic operations, and when adding/removing any member it does not need to update the remaining members' auxiliary secrets (i.e., [[??].sub.i,j] s).

4) Our scheme provides authenticated information used for the authentication of the group key without employing symmetric and asymmetric cryptographic operations.

http://dx.doi.org/10.3837/tils.2016.02.027

This work was supported by National Natural Science Foundation of China (Nos. 61173187, 61173188 and 11301002), the Natural Science Foundation of Anhui Province (Nos. 11040606M141 and 1408085QF107), and the 211 Project of Anhui University (Nos.33190187 and 17110099).

References

[1] D. Wallner, E. Harder, and R. Agee, "Key management for multicast: Issues and architecture," IETF RFC 2627, June 1999. Article (CrossRef Link)

[2] C.K. Wong, M.G. Gouda, and S.S. Lam, "Secure group communications using key graphs," IEEE/ACM Transactions on Networking, vol. 8, no. 1, pp. 16-30, 2000. Article (CrossRef Link)

[3] M. Sheng, J. Zhu, and G. Cui, "A hybrid group key management scheme for two- layered Ad Hoc networks," in Proc. of 9th International Conferences on Information Technology (ICIT'06), IEEE Computer Society, India, pp. 83-84, 2000. Article (CrossRef Link)

[4] A. Perrig, D.X. Song, and J.D. Tygar, "Elk, a new protocol for efficient large-group key distribution," in Proc. of IEEE Symposium on Security and Privacy, pp. 247-262, 2001. Article (CrossRef Link)

[5] X.S. Li, Y.R. Yang, M.G. Gouda, and S.S. Lam, "Batch rekeying for secure group communications," in Proc. of International World Wide Web Conference (WWW). pp. 525-534, 2001. Article (CrossRef Link)

[6] Y.R. Chen, J.D. Tygar and W.G. Tzeng, "Secure Group Key Management Using Uni-Directional Proxy Re-Encryption Schemes," in Proc. of IEEE INFOCOM 2011, pp. 1952-1960, 2011. Article (CrossRef Link)

[7] J.A.M. Naranjo, N. Antequera, L.G. Casado, J.A. Lopez-Ramos, "A suite of algorithmes for key distribution and authentication in centralized secure multicast environments," Journal of Computational and Applied Mathematics, vol. 236, no. 12, pp. 3042-3051, 2012. Article (CrossRef Link)

[8] P. Vijayakumar, S. Bose, A. Kannan, "Centralized key distribution protocol using the greatest common divisor method," Computer & Mathematics with Applications, vol. 65, no. 9, pp. 1360-1368, 2013. Article (CrossRef Link)

[9] L. Harn and C. L. Lin, "Authenticated Group Key Transfer Protocol Based on Secret Sharing," IEEE Transactions on Computers, vol. 59, no. 6, pp. 842-846, 2010. Article (CrossRef Link)

[10] W. Diffie, M. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644-654, 1976. Article (CrossRef Link)

[11] I. Ingemarsson, D.T. Tang, C.K. Wong, "A conference key distribution system," IEEE Transactions on Information Theory, vol. 28, no. 5, pp. 714-719, 1982. Article (CrossRef Link)

[12] M. Burmester, Y. Desmedt, "A secure and efficient conference key distribution system," Advances in Cryptology--EUROCRYPT 1994, Lecture Notes in Computer Science, vol. 950, pp. 275-286, 1994. Article (CrossRef Link)

[13] M. Steiner, G. Tsudik, M. Waidner, "Key agreement in dynamic peer groups," IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 8, pp. 769-780, 2000. Article (CrossRef Link)

[14] A. Joux, "A One Round Protocol for Tripartite Diffie-Hellman," Journal of Cryptology, vol. 17, no. 4, pp. 263-276, 2004. Article (CrossRef Link)

[15] Y. Kim, A. Perrig, and G. Tsudik, "Tree-based group key agreement," ACM T. Inf. and System Security (TISSEC), vol. 7, no. 1, pp. 60-96, 2004. Article (CrossRef Link)

[16] J. Katz, M. Yung, "Scalable protocols for authenticated group key exchange," Advances in cryptology--CRYPTO 2003. Lecture notes in computer science, vol. 2729. Springer- Verlag, pp. 110-25, 2003. Article (CrossRef Link)

[17] Q. Wu, Y. Mu, W. Susilo, B. Qin, J. Domingo-Ferrer, "Asymmetric Group Key Agreement," in Proc. of EUROCRYPT 2009, LNCS, vol. 5479, Springer-Verlag, pp. 153-170, 2009. Article (CrossRef Link)

[18] L. Zhang, Q.H. Wu, B. Qin, et al., "Provably secure one-round identity- based authenticated asymmetric group key agreement protocol," Information Sciences, vol. 181, no. 19, pp. 4318-4329, 2011. Article (CrossRef Link)

[19] L. Zhang, Q.H. Wu, B. Qin, et al., "Asymmetric group key agreement protocol for open networks and its application to broadcast encryption," Computer Networks, vol. 55, no. 15, pp. 3246-3255, 2011. Article (CrossRef Link)

[20] S. Jarecki, J. Kim and G. Tsudik, "Flexible Robust Group Key Agreement," IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 5, pp. 879-886, 2011. Article (CrossRef Link)

[21] X.X. Lv, H. Li and B.C. Wang, "Group key agreement for secure group communication in dynamic peer systems," Journal of Parallel and Distributed Computing, vol. 72, no. 10, pp. 1195-1200, 2012. Article (CrossRef Link)

[22] A. Ballardie, "Scalable Multicast Key Distribution," RFC 1949, 1996. Article (CrossRef Link)

[23] S. Mittra, "Iolus: A framework for scalable secure multicasting," in Proc. of the ACM SIGCOMM, vol. 27, 4 (New York, Sept.) ACM, New York, pp. 277-288, 1997. Article (CrossRef Link)

[24] L.R. Dondeti, S. Mukherjee, and A. Samal, "Scalable secure one-to-many group communication using dual encryption," Computer Communications, vol. 23, no. 17, pp. 1681-1701, 2000. Article (CrossRef Link)

[25] A.T. Sherman and D.A. McGrew, "Key establishment in large dynamic groups using one-way function trees," IEEE Transactions on Software Engineering, vol. 29, no. 5, pp. 444-458, 2003. Article (CrossRef Link)

[26] D.W. Kwak, J.W. Kim, "A Decentralized Group Key Management Scheme for the Decentralized P2P Environment," IEEE Communications Letters, vol. 11, no. 6, pp. 555-557, 2007. Article (CrossRef Link)

[27] N.T.T. Huyen, M. Jo, T.D. Nguyen and E.N. Huh, "A beneficial analysis of deployment knowledge for key distribution in wireless sensor networks," Security and Communication Networks, vol. 5, no. 5, pp. 485-495, 2012. Article (CrossRef Link)

[28] D.H. Je, Y.H. Choi, S.W. Seo, "Subscription-Period-Aware Key Management for Secure Vehicular Multicast Communications," IEEE Transaction on Vehicular Technology, vol. 62, no. 9, pp. 4213-4227, 2013. Article (CrossRef Link)

Run-hua Shi received the Ph.D. degree from University of Science and Technology of China in 2011. He is currently a Professor with Anhui University, and a visiting fellow at the School of Computing and Information Technology, University of Wollongong. His current research interest includes classical and quantum cryptography, in particular, privacy-preserving multiparty computation.

Hong Zhong received the Ph.D. degree from University of Science and Technology of China in 2005. She is currently a Professor with Anhui University. Her main research works focus on wireless network and network security.

Shun Zhang received the Ph.D. degree from Beijing Normal University in 2012. He is currently an associate professor with Anhui University. His current research interest includes computational complexity and quantum computation.

Run-hua Shi, Hong Zhong and Shun Zhang

School of Computer Science and Technology, Anhui University, Hefei, 230601,

China

[e-mail: shirh@ahu.edu.cn, zhongh@mail.ustc.edu.cn and shzhang27@163.com]

* Corresponding author: Run-hua Shi

Received August 17, 2015; revised November 1, 2015; revised December 11, 2015; accepted December 22, 2015; published February 29, 2016

Table 1. The main computation costs of LKH, OFT, ELK, HL and our proposed scheme LKH OFT ELK Join GKGC (2E+R)logN (2E+2H+F)logN ElogN+(2N-1)F+R SGKM -- -- -- Old member D logN D logN D logN New member D logN (D+H) logN 2FlogN Leave GKGC (2E+R)logN (E+H+F)logN (2E+7F)logN SGKM -- -- -- Member D logN (D+F) logN (D+4F)logN HL Ours Join GKGC NP+1R+1H (mn+n)M+1H SGKM -- 1S+2nM+1H Old member 1P+1H nM+1H New member 1P+1H nM+1H Leave GKGC NP+1R+1H (mn+n)M+1H SGKM -- 1S+2nM+1H Member 1P+1H nM+1H Table 2. The communication and storage costs of LKH, OFT, ELK, HL and our proposed scheme LKH OFT ELK Communication Join 2logNL logNL 0 (broadcast) Leave 2logNL logNL logNL Storage GKGC (2N-1)L (2N-1)L (2N-1)L SGKM -- -- -- Member logNL (logN+1)L logNL HL Ours Communication Join (2N+1)L nL (broadcast) Leave (2N+1)L nL Storage GKGC 2NL (m+mn+nn)L SGKM -- (m+n+mn+nn)L Member 2L nL

Printer friendly Cite/link Email Feedback | |

Author: | Shi, Run-hua; Zhong, Hong; Zhang, Shun |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Feb 1, 2016 |

Words: | 6528 |

Previous Article: | LCT: a lightweight cross-domain trust model for the mobile distributed environment. |

Next Article: | Dynamic scheduling method for cooperative resource sharing in mobile cloud computing environments. |

Topics: |