# Key Management Schemes for Multilayer and Multiple Simultaneous Secure Group Communication

Authors: R. Aparna; B. B. Amberker
Journal: ISRN Communications and Networking
 (2012)

---

## Abstract

Many emerging applications are based on group communication model and many group communications like multimedia distribution and military applications require a security infrastructure that provides multiple levels of access control for group members. The group members are divided into a number of subgroups and placed at different privilege levels based on certain criteria. A member at higher level must be capable of accessing communication in its own level as well as its descendant lower levels but not vice versa. In this paper we propose a key management scheme for this multilayer group communication. We achieve substantial reduction in storage and encryption cost compared to the scheme proposed by Dexter et al. We also address periodic group rekeying. Applications like scientific discussion and project management may lead to a scenario in which it is necessary to set up multiple secure groups simultaneously, and few members may be part of several secure groups. Managing group keys for simultaneous secure groups is critical. In this paper we propose a novel key management scheme for multiple simultaneous groups.


---

## Body

## 1. Introduction

Many emerging applications like secure audio and visual broadcasts, pay-per-view, scientific discussion, and teleconferencing are based on group communication model. Several users participate in these applications, and multicast communication is an efficient means of distributing data to a large group of participants [1–3] since it reduces the demands on network and bandwidth resources. But, the communication among these participants must be carried out confidentially. Thus, a common key known as group key or secret key must be established with all the users in the group, so that any group member can encrypt the message using this key, and all others can decrypt the message using the same key. The group, being dynamic in nature, allows member join and leave events. Efficiently managing group key for large, dynamically changing groups is a difficult problem. Every time when a new member joins the group, the group key must be changed in order to provide backward access control (i.e., new members should not be able to access past communication). Similarly, when a user leaves the group, the group key must be changed so that leaving member cannot have access to future communication that takes place between remaining group members, known as forward access control. This group key updating process is referred to as rekeying.Rekeying process involves changing the group key whenever there is a membership change and distributing it among the members of the group in a secure manner. To communicate changed key among group members securely, rekey messages are constructed, encrypted, and multicast to the group. The overhead involved in rekey operation, that is, key updation, number of encryptions performed, and communication cost must be minimum and should be independent of the group size, which improves scalability.Several secure group key management techniques have been proposed to support scalable secure multicasting [4–10]. In a typical multicast key management scheme, there is a trusted third party, known as Key Distribution Center (KDC). This single trusted centralized entity is responsible for generating and distributing keys securely to the group members. Among the schemes which involve KDC [7, 11–15], the scheme proposed by Wong et al. in [7] is efficient and is widely used since it improves scalability. The scheme uses a hierarchical tree structure in which users are maintained at the leaf level, and every user is assigned with keys along the path of its location till the root. Besides group key, the KDC shares auxiliary keys that are used solely for the purpose of updating the group key and other auxiliary keys. In addition, every user shares a private key that is known by itself and the KDC. These schemes are referred to as key-based schemes.Hierarchical tree structure is also used in Centralized Key Management with Secret Sharing (CKMSS) [16, 17]. In this scheme, KDC considers a t degree (t is a nonzero positive integer) polynomial with the constant term of the polynomial being the secret key. It computes t distinct shares known as prepositioned information and stores them at the users. To compute the group key, (t+1) shares of the polynomial are required, and this (t+1)th share is sent as an activating share by the KDC. Once the group key is computed, it is used until a member joins or leaves the group. For every membership change (join/leave), to perform rekey operation, KDC multicasts an activating share to enable the members to compute new group key. These schemes are called share-based schemes.Both the key-based and share-based schemes discussed above are designed for managing keys for a group of users enjoying same privilege and are not suitable for handling multilayer and multiple SGC scenario. But, for certain applications, it is necessary to have multilayer group communication scenario where members in the system have different privileges. In some applications a memberu in the system may be part of several groups. In this paper, we address the above two cases of Secure Group Communication (SGC) and propose key management schemes.We organize the paper as follows: Section2 focuses on the applications of multilayer SGC and highlights the schemes proposed to address such scenario in detail. Section 3 concentrates on our scheme to manage multilayer hierarchy. We discuss initial key computation, rekeying during join/leave operation, periodic rekeying. In section 4 we compare the performance of our scheme with Dexter et al. scheme. Section 5 deals with setting up multiple groups, initial key computation, and rekeying. Section 6 presents authentication to multiple SGC, and we conclude the paper in Section 7.


## 2. Applications of Multilayer SGC

(i) In multimedia applications, we can consider two categories of receivers: high-definition television (HDTV) and traditional television. Users with HDTV receivers can form one subgroup and others with traditional television receiver can form another subgroup. Users with traditional television receivers can receive the normal format, while the users with HDTV receiver can receive both the normal format and the extra information needed to achieve HDTV resolution. Thus, there are two layers, group with HDTV receiver forms higher layer subgroup and the one with traditional television receiver forms lower layer subgroup. This application requires a multilayer SGC scenario.(ii) In multicast scalable video service, the video is encoded into3 quality levels: basic quality level, medium quality level, and best quality level. Here, the users can be classified into 3 different layers based on the quality of the video they purchase: base layer (BL), enhancement layer 1 (EL1), and enhancement layer 2 (EL2). The users purchasing the basic video quality level belong to BL group, users purchasing the medium quality level belong to both BL and EL1 groups, whereas the users purchasing the best quality level belong to all the three, that is, BL, EL1, and EL2 groups. Thus, users with access to higher-quality video service must also have access to lower-quality ones.(iii) Military troop contains different categories like Captains, Lieutenants, Sergeants, Corporals, Soldiers, and so forth, and this requires a hierarchical group communication model. Captains are at the highest layer, Lieutenants at the second higher level layer, Sergeants at a layer below Lieutenants, Corporals at the next lower layer, and Soldiers must be at the lowest layer as considered in [18]. Soldiers should be able to communicate only with other Soldiers (peer members), whereas Sergeants can communicate with other Sergeants as well as with Corporals and Soldiers. Similarly Captains should have access to all the communications that take place between different classes.(iv) In project management, a single project is divided into multiple modules, and set of users are made to design a particular module. Users involved in handling one module form one secure group. This may lead to a scenario in which it is necessary to set up multiple secure groups simultaneously.To manage the above type of scenarios, a naive solution is to extend key-based and share-based tree structure, by using independent trees for each layer. But, this is inefficient and does not scale well when there are many layers. Hence, there is a need to have a multigroup key management scheme that exploits the overlap in the memberships of different layers. Two key management schemes have been developed to provide hierarchical access control. The scheme proposed in [19, 20] is key-based, where each layer has its own session key and whenever there is a membership change in any layer, corresponding session key is changed and securely transmitted to appropriate group members. The scheme proposed in [21] is share based. For each layer, a polynomial of degree t is considered, and t distinct shares of this polynomial are stored at the members of that layer (prepositioned information) and KDC sends (t+1)th share as an activating share so that members can compute group key for that layer. Whenever there is a membership change in any layer, KDC just sends a different activating share to the members of that layer so that they can compute a new group key for that layer.In [18], a military application is considered to illustrate multilayer secure group communication. Military officers belonging to different categories (Captains, Lieutenants, Sergeants, Corporals, Soldiers, etc.) are divided into subgroups and are hierarchically placed one above the other. Higher layer officials can have access to the communication between its descendant lower-layer subgroups. To provide this feature, it uses a one-way hash function H(·) to compute a chain of keys. The main idea of using H(·) function is to relate layers' keys in such a way, that is, knowing a key of its own layer, a member can compute keys of lower layers. Thus, Captains are given with random key K, for the Lieutenants H(K) is given, for Sergeants H(H(K))=H2(K) is sent, Corporals are assigned with H3(K), and Soldiers with H4(K). Captains can access the communication between the Sergeants, by computing the key H2(K).In [19, 20], Sun and Liu used tree-based hierarchical approach to handle broadcasting multimedia applications in different layers to different groups of users.To the best of our knowledge, only SGC within a single group is addressed in the literature. A SGC among multiple groups is not addressed in the literature. In this paper we address key management schemes for multilayer and multiple groups and our schemes can be used for the applications explained above.


### 2.1. Multilayer Secure Group Communication

Multilayer key management scheme proposed in [19, 20] uses the following model: a set of users U={u1,u2,…,uN} is partitioned into M subsets (subgroups) P1,P2,…,PM such that members of Pi and can communicate with each other. However, members of Pi can communicate with members of Pj, i>j, but not vice versa, 1≤i,j≤M. We say that the members of subgroup Pi are at layer i and members of subgroup Pi belong to subgroup Pj, i>j. Members of subgroup Pi overlap with the members of subgroup Pj, i>j. Figure 1 illustrates the arrangement of different subgroups Pi in layered approach, i=1,2,…,M.Figure 1
Subgroups arranged into different privilege layers.To manage keys for multiple layers in traditional hierarchical tree-based key management scheme, a separate key tree is constructed for each layer. Although it is easy to implement using independent trees, a substantial overhead is introduced in managing the keys due to the overlapping membership in different layers.In order to manage the keys of all the subgroups, independent trees are integrated into one key graph in [19, 20], and it uses a key-based scheme to manage the keys. In [21], integrated key graph as in [19, 20] is used, but for key management it uses share-based scheme. The key management scheme proposed in [21] is explained as follows:  (1)
KDC fixes the security parametert,(2)
KDC constructs a Logical Key Tree (LKT) as in [7] for the subgroup Pi at layer i. For a secure group with Si users, there are at most 2Si-1 nodes in LKT and the height of the LKT, is ⌈log2Si⌉,(3)
for each node in LKT of subgroupPi, KDC selects randomly t-1 number of distinct points (xkji,ykji) in GF(p) (where GF refers to Galois Field) called  prepositioned shares, i∈{1,2,…,M}, j=1,2,…,t-1, k=1,2,…,2Si-1. To each user u∈Pi, KDC sends  securely(t-1)log2Si shares pertaining to the shares for the nodes along the path from leaf node u till root,(4)
KDC selects another point(xt,yt) called activating share (AS) and broadcasts it to the members of all the layers in the system,(5)
a member of the subgroupPi constructs log2Si number of polynomials of degree (t-1) using the corresponding shares it has received from KDC and AS, i=1,2,…,M and evaluates each polynomial at 0 to get the keys, and(6)
KDC also constructs polynomial of degree(t-1) for each node k in the LKT of Pi using the t-1 points (xkji,ykji) and AS and evaluates at 0 to get the corresponding key for that node.In this scheme, each key is computed by constructing at-1 degree polynomial using t-1 different prepositioned shares and a common activating share. In this scheme, each user ui is required to store prepositioned shares of the nodes from leaf to the root.


## 2.1. Multilayer Secure Group Communication

Multilayer key management scheme proposed in [19, 20] uses the following model: a set of users U={u1,u2,…,uN} is partitioned into M subsets (subgroups) P1,P2,…,PM such that members of Pi and can communicate with each other. However, members of Pi can communicate with members of Pj, i>j, but not vice versa, 1≤i,j≤M. We say that the members of subgroup Pi are at layer i and members of subgroup Pi belong to subgroup Pj, i>j. Members of subgroup Pi overlap with the members of subgroup Pj, i>j. Figure 1 illustrates the arrangement of different subgroups Pi in layered approach, i=1,2,…,M.Figure 1
Subgroups arranged into different privilege layers.To manage keys for multiple layers in traditional hierarchical tree-based key management scheme, a separate key tree is constructed for each layer. Although it is easy to implement using independent trees, a substantial overhead is introduced in managing the keys due to the overlapping membership in different layers.In order to manage the keys of all the subgroups, independent trees are integrated into one key graph in [19, 20], and it uses a key-based scheme to manage the keys. In [21], integrated key graph as in [19, 20] is used, but for key management it uses share-based scheme. The key management scheme proposed in [21] is explained as follows:  (1)
KDC fixes the security parametert,(2)
KDC constructs a Logical Key Tree (LKT) as in [7] for the subgroup Pi at layer i. For a secure group with Si users, there are at most 2Si-1 nodes in LKT and the height of the LKT, is ⌈log2Si⌉,(3)
for each node in LKT of subgroupPi, KDC selects randomly t-1 number of distinct points (xkji,ykji) in GF(p) (where GF refers to Galois Field) called  prepositioned shares, i∈{1,2,…,M}, j=1,2,…,t-1, k=1,2,…,2Si-1. To each user u∈Pi, KDC sends  securely(t-1)log2Si shares pertaining to the shares for the nodes along the path from leaf node u till root,(4)
KDC selects another point(xt,yt) called activating share (AS) and broadcasts it to the members of all the layers in the system,(5)
a member of the subgroupPi constructs log2Si number of polynomials of degree (t-1) using the corresponding shares it has received from KDC and AS, i=1,2,…,M and evaluates each polynomial at 0 to get the keys, and(6)
KDC also constructs polynomial of degree(t-1) for each node k in the LKT of Pi using the t-1 points (xkji,ykji) and AS and evaluates at 0 to get the corresponding key for that node.In this scheme, each key is computed by constructing at-1 degree polynomial using t-1 different prepositioned shares and a common activating share. In this scheme, each user ui is required to store prepositioned shares of the nodes from leaf to the root.


## 3. Proposed Key Management Scheme for Multilayer SGC

We propose to use the key graph structure as in [19, 20]. We construct individual key trees for different layers and then integrate them. We use the same model that is explained for Dexter et al. scheme and try to reduce the amount of storage required at both KDC and users [22]. For auxiliary keys, we use random elements, and we compute the group keys as described below.KDC fixes the security parametert, computes, and distributes the keys and shares as follows:  (1)
KDC selects randomlyt-1 number of points (xi,yi) in GF(p) called  prepositioned shares, i=1,2,…,t-1 and an  activating share (AS) and sends  securely to the members of all the subgroups P1,P2,…,PM,(2)
KDC constructs LKT for the subgroupP1 at layer 1 with the  subgroup keyG1. The key G1 is obtained by constructing a polynomial P(x) of degree t-1 using the t-1 points (xi,yi) and AS and evaluating at 0 to get G1=P1(0). KDC sends  secretly to each user u of P1, all the auxiliary keys along the path of LKT from leaf u to the root,(3)
KDC selects group share(xgj,ygj) for the subgroup Pj and sends secretly to the members of the subgroup Pj,Pj+1,…,PM, j=2,3,…,M, and(4)
KDC constructs LKT for the subgroupPj at layer j with the subgroup key Gj. The key Gj is obtained by constructing a polynomial Pj(x) of degree t+j-2 using t-1 prepositioned shares, AS, and j-1 group shares (xgl,ygl), l=2,3,…,j and j=2,3,…,M. It evaluates the polynomial Pj at 0 to get Gj=Pj(0). To each user u of Pj, KDC sends  secretly all the auxiliary keys along the path of LKT from leaf u to root.Figure 2 shows the hierarchical key tree structure with M layers.Figure 2
Hierarchical key tree structure for multilayer secure group communication withM  layers.Figure3 shows an example integrated key graph for three layers in which three independent groups are integrated to form a three-layer hierarchy. In Figure 3, G1, G2, and G3 represent the roots of the subgroups P1, P2, and P3, respectively.Figure 3
An example integrated key graph with auxiliary keys and group keys.We are addressing the following events:(1)
a new member joins the service,(2)
a member leaves the service, and(3)
a member moves from one service layer to another service layer.


### 3.1. Member Join Event

When a new member,unew, joins any layer i, i=1,…,M, keys along the path from the joining point till the root must be changed and conveyed to corresponding users. Instead of KDC changing the keys or sending a new activating share, we allow the members of layer i themselves to compute the new group key and auxiliary keys on their own by applying one-way hash function to the corresponding previous keys. KDC also applies one-way hash function to the previous keys on the path from the joining point till the root. Members at layers i+1 to M change the group key Gi by applying one-way hash function to previous group key Gi. For the new user, unew, KDC sends t-1 prepositioned shares (xi,yi), auxiliary keys of Pi along the path to where unew is inserted, and group key Gi and i group shares (xgi,ygi) by encrypting with the private key of unew, i=1,2,…,M.


### 3.2. Member Leave Event

If a member at layeri leaves, i=1,2,…,M, the following keys have to be changed:  (1)
keys along the path from the leaving position till root,(2)
subgroup keyGi, and(3)
subgroup keysG1,G2,…,Gi-1 of layers from 1 to i-1.KDC generates keys along the path and sends them securely to the required members of the group. KDC generates and sends a new activating share securely to the members of the subgroupsP1, P2, …, Pi. Users of group Pj construct the polynomial Pj(x) using prepositioned shares, group share, and new activating share and compute the group key Gj by evaluating the polynomial Pj(x) at 0, j=1,2,…,i.We illustrate this with the following example. From Figure3, if member u8 leaves the group, the following messages are constructed and sent to users ({Ki}Kj indicates key Ki encrypted with key Kj and AS denotes activating share) KDC→{u1tou4}:{AS}K1-4KDC→{u5,u6}:{AS}K5-8′,{K5-8′}K5-6KDC→u7:{AS}K5-8′,{K5-8′}K′7-8,{K7-8′}K7KDC→{u9tou14}:{AS}G2KDC→{u17tou19}:{AS}G3.


### 3.3. Member Moving from One Service Layer to Another

Here we encounter two cases.Case 1.
If a member moves from layeri to its higher layer j  (i<j), then it must be provided with extra group share/s meant for layers from (i+1) to j. To provide backward confidentiality for the messages communicated in the subgroups from i+1 to j, group share (xgk,ygk) of the group Pk is changed, k=i+1,i+2,…,j. KDC generates group share (xgk,ygk) and encrypts with the previous group key Gk and sends to members of the group Pk, k=i+1,i+2,…,j.Case 2.
If a member moves from layeri to its descendant layer j, (i<j), then group shares of layers from (i+1) to j must be changed. In layer j, auxiliary keys possessed by the moving member must be changed. To convey new group share (xgk,ygk) to the members of subgroup Pk, it is encrypted with the auxiliary keys at level 1 of LKT of subgroup Pk, k=i+1,i+2,…,j.Example 1.
In Figure3, if a member u12 moves from layer 2 to layer 3, it is inserted as sibling of member u19. The group share (xg3,yg3) must be changed to provide backward access control. The following messages are constructed and sent to users: KDC→{u17,u18}:{(xg3,yg3)}G3,ASKDC→u19:{(xg3,yg3)}G3,{K19-20′}K19,ASKDC→u12:{(xg3,yg3),K19-20′}K12,ASKDC→{u9,u10}:{K9-16′}K9-12′,{K9-12′}K9-10KDC→u11:{K9-16′}K9-12′, [K9-12′]K11-12′, {K11-12′}K11KDC→{u13,u14}:{K9-16′}K13-16.


### 3.4. Periodic Rekeying

If the content has very high value, even though there is no membership change, group key must be changed for all the layers periodically. This leaves the attacker with very less time to attack on the current key values. To achieve this periodic rekeying, we fix a rekey period/interval. After the expiry of each rekey interval, rekeying process is initiated. For periodic rekeying, we propose two methods.Method 1.
(i) KDC sends an activating share by encrypting it with layer1 group key, G1.
(ii) Since all the usersu1,u2,…,uN in the system belong to subgroup P1, they know the subgroup key G1 and can decrypt the activating share.
(iii) Users of subgroupPi compute new subgroup keys G1,G2,…,Gi using new activating share, prepositioned shares and group share (xgi,ygi).Method 2.
The users compute the new group key after every rekey interval by applying a one-way hash function on the current group keys. This reduces the communication and computation cost since it avoids reconstruction of the polynomial.


## 3.1. Member Join Event

When a new member,unew, joins any layer i, i=1,…,M, keys along the path from the joining point till the root must be changed and conveyed to corresponding users. Instead of KDC changing the keys or sending a new activating share, we allow the members of layer i themselves to compute the new group key and auxiliary keys on their own by applying one-way hash function to the corresponding previous keys. KDC also applies one-way hash function to the previous keys on the path from the joining point till the root. Members at layers i+1 to M change the group key Gi by applying one-way hash function to previous group key Gi. For the new user, unew, KDC sends t-1 prepositioned shares (xi,yi), auxiliary keys of Pi along the path to where unew is inserted, and group key Gi and i group shares (xgi,ygi) by encrypting with the private key of unew, i=1,2,…,M.


## 3.2. Member Leave Event

If a member at layeri leaves, i=1,2,…,M, the following keys have to be changed:  (1)
keys along the path from the leaving position till root,(2)
subgroup keyGi, and(3)
subgroup keysG1,G2,…,Gi-1 of layers from 1 to i-1.KDC generates keys along the path and sends them securely to the required members of the group. KDC generates and sends a new activating share securely to the members of the subgroupsP1, P2, …, Pi. Users of group Pj construct the polynomial Pj(x) using prepositioned shares, group share, and new activating share and compute the group key Gj by evaluating the polynomial Pj(x) at 0, j=1,2,…,i.We illustrate this with the following example. From Figure3, if member u8 leaves the group, the following messages are constructed and sent to users ({Ki}Kj indicates key Ki encrypted with key Kj and AS denotes activating share) KDC→{u1tou4}:{AS}K1-4KDC→{u5,u6}:{AS}K5-8′,{K5-8′}K5-6KDC→u7:{AS}K5-8′,{K5-8′}K′7-8,{K7-8′}K7KDC→{u9tou14}:{AS}G2KDC→{u17tou19}:{AS}G3.


## 3.3. Member Moving from One Service Layer to Another

Here we encounter two cases.Case 1.
If a member moves from layeri to its higher layer j  (i<j), then it must be provided with extra group share/s meant for layers from (i+1) to j. To provide backward confidentiality for the messages communicated in the subgroups from i+1 to j, group share (xgk,ygk) of the group Pk is changed, k=i+1,i+2,…,j. KDC generates group share (xgk,ygk) and encrypts with the previous group key Gk and sends to members of the group Pk, k=i+1,i+2,…,j.Case 2.
If a member moves from layeri to its descendant layer j, (i<j), then group shares of layers from (i+1) to j must be changed. In layer j, auxiliary keys possessed by the moving member must be changed. To convey new group share (xgk,ygk) to the members of subgroup Pk, it is encrypted with the auxiliary keys at level 1 of LKT of subgroup Pk, k=i+1,i+2,…,j.Example 1.
In Figure3, if a member u12 moves from layer 2 to layer 3, it is inserted as sibling of member u19. The group share (xg3,yg3) must be changed to provide backward access control. The following messages are constructed and sent to users: KDC→{u17,u18}:{(xg3,yg3)}G3,ASKDC→u19:{(xg3,yg3)}G3,{K19-20′}K19,ASKDC→u12:{(xg3,yg3),K19-20′}K12,ASKDC→{u9,u10}:{K9-16′}K9-12′,{K9-12′}K9-10KDC→u11:{K9-16′}K9-12′, [K9-12′]K11-12′, {K11-12′}K11KDC→{u13,u14}:{K9-16′}K13-16.


## 3.4. Periodic Rekeying

If the content has very high value, even though there is no membership change, group key must be changed for all the layers periodically. This leaves the attacker with very less time to attack on the current key values. To achieve this periodic rekeying, we fix a rekey period/interval. After the expiry of each rekey interval, rekeying process is initiated. For periodic rekeying, we propose two methods.Method 1.
(i) KDC sends an activating share by encrypting it with layer1 group key, G1.
(ii) Since all the usersu1,u2,…,uN in the system belong to subgroup P1, they know the subgroup key G1 and can decrypt the activating share.
(iii) Users of subgroupPi compute new subgroup keys G1,G2,…,Gi using new activating share, prepositioned shares and group share (xgi,ygi).Method 2.
The users compute the new group key after every rekey interval by applying a one-way hash function on the current group keys. This reduces the communication and computation cost since it avoids reconstruction of the polynomial.


## 4. Comparison

Storage at Each User
In Dexter et al. scheme [21], each user u∈Pi stores the shares of the keys along the path from leaf to the root, i=1,2,…,M. If there are Si users in Pi, then height of the tree is ⌈log2Si⌉. Thus each user u∈Pi stores (t-1)⌈log2Si⌉ number of elements.
In our scheme, each useru∈Pi stores (t-1) prepositioned shares, an activating share, i number of group shares and ⌈log2Si⌉ auxiliary keys.Storage at KDC
KDC is required to store shares of all the keys in the system. For a total ofN users in the system, there are at most 2N-1 nodes. Thus, storage required at KDC in Dexter et al. scheme is (t-1)(2N-1). In our scheme there are t+M-1 shares and 2N-M-1 auxiliary keys in the system. Hence KDC is required to store only 2N+t-2 elements.Encryption Cost
In Dexter et al. scheme, if a member leaves any layeri, i=1,…,M, in order to change the keys along the path till the root, corresponding prepositioned shares must be changed, which leads to (t-1)⌈log2Si⌉ encryptions. Also, prepositioned shares meant for different layers must be changed, which results in (t-1)i encryptions. Hence, the number of elements encrypted is (t-1)(⌈log2Si⌉+i). Whereas in our scheme, keys along the path and an activating share are encrypted; thus, it is just (⌈log2Si⌉+it) encryptions.Computation Cost
In Dexter et al. scheme [21], the group key for each layer i is computed by constructing a (t-1)  degree polynomial and evaluated at 0. In our scheme, as we move up the hierarchy, degree of the polynomial is incremented by 1. Though it requires more amount of computation as compared to (t-1) degree polynomial, it improves the resistance of the system to attack; hence, the system is more secure.Table1 gives the comparison of our scheme with the scheme proposed by Dexter et al. [21] in terms of storage and encryption cost.Table 1
Comparison of storage and encryption cost.
Dexter et al. scheme
Our scheme
Storage at KDC
(
t
-
1
)
(
2
N
-
1
)
2
N
+
t
-
2
Storage at each user of layeri
(
t
-
1
)
(
⌈
log
2
S
i
⌉
+
i
)
t
+
⌈
log
2
S
i
⌉
+
i
-
1
Number of elements encrypted during leave from layeri
(
t
-
1
)
(
⌈
log
2
S
i
⌉
+
i
)
⌈
log
2
S
i
⌉
+
i
tTable2 compares the performance of our scheme with Dexter et al. scheme [21]. To have fair comparison we consider 4 layers N1, N2, N3, and N4 and a polynomial of degree 5, that is, t-1=5. N1 is the layer at lower privilege level, and N4 is at higher privilege level.Table 2
Performance of multilayer SGC.
Number of users in different layers
Number of keys at server
Number of keys at each user
N
1
N
2
N
3
N
4
Dexter et al. scheme
Our scheme(% saving)
Dexter et al. scheme
Our scheme (% saving)
l
1
l
2
l
3
l
4
l
1
l
2
l
3
l
4
128
64
64
32
2860
592 (79)
40
40
45
45
12  (70)
12  (70)
13 (71)
13 (71)
4096
1024
512
64
56940
11408  (80)
65
60
60
50
17 (73)
16 (73)
16 (73)
14 (72)
2
15
2
12
64
16
369420
73904 (80)
80
70
45
40
20 (75)
18 (74)
13  (71)
12 (70)
2
20
2
15
2
10
2
7
10824940
2165008 (80)
105
85
65
55
25 (76)
21 (75)
17 (73)
15 (72)Consider an example with128 users at layer N1, 64 users each at layers N2 and N3, and 32 users at layer N4. Heights of the trees at layers N1, N2, N3, and N4 are 7, 6, 6, and 5, respectively. Number of keys stored at KDC in Dexter et al. scheme is (t-1)(2N-1) at each layer which sums up to be 2860, whereas in our scheme we get only 588 keys at the KDC which is computed as 2N+t-2.In Dexter et al. scheme, users at layerN1 store h1+i=7+1 sets of prepositioned information, namely, 8*5=40 keys. Users at layer N2 store 6+2=8 sets of prepositioned information, users at layer N3 store 6+3=9 sets of prepositioned information, and users of layer N4 store 5+4=9 sets of prepositioned information. In our scheme, the number of keys at different layers N1, N2, N3, and N4 is only 12, 12, 13, and 13, respectively.In Table2 we also have recorded the percentage of savings achieved in our scheme. From the values recorded in Table 2, it is clear that we achieve substantial savings in storage and encryption cost as compared to Dexter et al. scheme. For instance, for a secure group with 4096 users and with a fixed security parameter t=10, we achieve 80% savings in storage at KDC and about 73% savings in storage at the users.


## 5. Multiple Simultaneous SGC

A project may be divided into several modules, and each module may be assigned to a group of members. It may be necessary for some members to deal with two or more modules depending on the requirement. It is required that each module should be developed confidentially so that members developing a particular module must communicate among themselves securely. Hence, each group should have a group key, and members belonging to two or more groups should possess group keys of all those groups for which they are members. We develop a key management scheme for such multiple SGC with efficient storage, computation, and communication costs [23].


### 5.1. Key Management Scheme

We consider a set of usersU={u1,u2,…,uN} and M subgroups P1,P2,…,PM such that some users are present in more than one subgroup. For each subgroup Pi, a logical key tree is constructed, i=1,2,…,M. The height of the tree for subgroup Pi depends on the number of users in Pi. If there are Ni (Ni≤N) number of users in group Pi, then the height is hi=⌈log2Ni⌉. An user ui is assigned with a private key Ki, i=1,2,…,N and auxiliary keys along the path from ui to root of the key tree. This section deals about initial group setup and computation of group key(s).


### 5.2. Initial Group Setup and Group Key Computation

Our scheme is based on centralized key management scheme using logical key tree (LKT) approach as proposed in [7]. Hence, we assume a trusted KDC which is responsible for initial group(s) setup and rekeying operations. Users in the system are provided with unique identification number, and the groups are assigned with group numbers. To begin with we allow the KDC to fix the security parameter t.  (1)
Userui, i=1,2,…,N who would like to join the group Pj, j=1,2,…,M sends a join request to KDC. The KDC generates and sends a unique private key Ki, i=1,2,…,N to the requesting user ui over a secure channel (we assume that, at the initial stage, a secure channel is established between KDC and the joining user). Hence, every user shares a private key with the KDC.(2)
KDC selects randomlyt-2 number of points (xi,yi) in GF(p) called  prepositioned basic shares, i=1,2,…,t-2 and (xt,yt) as activating share (AS). These shares are sent  securely to the members of all the subgroups P1,P2,…,PM.(3)
KDC selects randomlyM points (xgi,ygi) in GF(p) called  prepositioned group shares distinct from the previously selected points and sends (xgi,ygi) securely to the members of the subgroup Pi, i=1,2,…,M.(4)
KDC constructs LKT for the groupPi with the group key Gi. The key Gi is obtained by constructing a polynomial Pi(x) of degree t-1 using the shares (xi,yi) of step 2 and the prepositioned group share (xgi,ygi). The group key is Gi=Pi(0), i=1,2,…,M. KDC sends  secretly to each user u of Pi, all the auxiliary keys along the path of LKT from the leaf u to the root.(5)
If an useru is a member of j number of groups (1≤j≤M), it is provided with (t-2) prepositioned basic shares along with AS and j number of prepositioned group shares. It constructs j distinct polynomials. A polynomial Pk(x) is constructed by using t-1 shares of step 2 and prepositioned group share (xgk,ygk), k=1,2,…,j. Thus, it can construct j distinct polynomials just by using one distinct group share.Figure4 shows an example key tree structure with 3 groups, namely, P1, P2, and P3 set up simultaneously. Group P1 comprises of eight members u1,u2,…,u8, group P2 contains u6, u8, u9, and u10 as its members, whereas members u5, u11, u12, u13, u14, and u15 belong to group P3. In Figure 4, u-nodes represent users, and K-nodes represent keys. Key nodes K1 through K15 are private keys of users u1 through u15, respectively, and remaining K-nodes in the figure represent auxiliary keys. G1, G2, and G3 are the group keys of the groups P1, P2, and P3, respectively.Figure 4
Key tree structure for multiple groups.For example, let us considert=4,  p=41 and the (t-2) prepositioned basic shares as (1,28), (2,23) and AS as (4,4). Assume that KDC sends (3,11), (3,8), and (3,5) as the prepositioned group share for the members of the groups P1,P2, and P3, respectively. Hence, the members of the group Pi, i=1,2,3, now possess t; that is, 4 shares with them, and they can construct (t-1) degree polynomial and evaluate it at 0 to get the group key. Thus the members of group P1 get the group key G1 as 14, members of P2 get the group key G2 as 2, and G3 is computed by members of P3 as 34. Hence, user U5, for instance, can compute group keys for both the groups P1 and P3.


### 5.3. Member Join Event

If a new userunew wants to join the group Pi(1≤i≤M), it sends a join request to KDC. KDC finds a location for the user unew in the LKT of Pi and inserts it. To provide backward access control, keys along the path from the point of insertion till one level below the root are changed and communicated to the corresponding users. In order to change the group key Gi of Pi, KDC picks a new value of group share (xgi,ygi), encrypts it with the previous group key Gi, and sends it to the users of the group Pi. For the user unew, KDC sends keys along the path from unew to root, prepositioned shares (basic shares and group share) and AS after encrypting with the private key of unew. The new user constructs the polynomial and evaluates it at 0 to get the group key Gi.For instance, if a new useru16 sends a join request to join the group P3, KDC inserts u16 at the location as shown in Figure 5. KDC changes the key K1417 to K1417′ and picks a new value for group share, say (xg3′,yg3′). To convey changed keys and share to corresponding users, KDC constructs the following rekey messages: KDC→{u14,u15}:{K1417′}K1415,{(xg3′,yg3′)}G3KDC→{u5,u11,u12,u13}:{(xg3′,yg3′)}G3KDC→{u16}:{K1617,K1417′,(xg3′,yg3′)}K16.Figure 5
Key tree structure for multiple groups after useru16 joins the group P3.Now, suppose that if useru17 sends join requests to join two groups P2 and P3, the LKT looks as in Figure 6 after inserting u17 to both the groups of Figure 5. KDC constructs the following rekey messages to convey changed keys and group shares: KDC
→{u14,u15}:{K1417′′}K1415,  {(xg3′′,yg3′′)}G3′KDC
→{u5,u11,u12,u13}:{(xg3′′,yg3′′)}G3′KDC
→{u16}:{K1417′′}K1417′,  {K1417′}K16,  {(xg3′′,yg3′′)}G3′KDC
→{u6,u8,u9,u10}:{K610,(xg2′,yg2′)}G2KDC
→{u17}:{K17-2,K17-1, K1617′,K1417′′, (xg3′′,yg3′′)}K17.Figure 6
Key tree structure for multiple groups after useru17 joins the groups P2 and P3.If a member joins a groupGi with Ni members, then at most ⌈log2Ni⌉ keys are changed. To convey changed keys to the members of the group, ⌈2log2Ni⌉ encryptions are performed and ⌈log2Ni⌉ rekey messages are constructed. In general, if a member joins j number of groups, ∑i=1j‍log2Ni keys are changed, 2∑i=1j‍log2Ni encryptions are performed, and ∑i=1j‍log2Ni rekey messages are constructed.


### 5.4. Member Leave Event

A member may leave the group either voluntarily or KDC may forcibly expel the member from the group. In any case, the keys known to leaving member in the LKT must be changed to provide forward confidentiality. If a memberul wants to leave the group Pi(1≤i≤M), it sends a leave request to KDC. Here, we encounter two cases.Case 1.
Iful belongs to only one group Pi,(i)
KDC removes the corresponding user-node and private key-node from LKT,(ii)
KDC changes the keys along the path from leaving point till one level below the root inPi selects new group share (xgi,ygi) and conveys to corresponding users in Pi.Case 2.
Iful belongs to more than one group,  (i)
KDC detachesul from the group Pi,(ii)
KDC changes the keys along the path from leaving point till one level below the root inPi selects new group share (xgi,ygi) and conveys to corresponding users in Pi.For example, consider the multiple groups scenario as in Figure6. Now, if user u5 wants to leave the group P3, it sends a leave request to KDC. KDC detaches u5 from the LKT of P3 and changes the keys along the path as shown in Figure 7, and to convey changed keys it constructs the following rekey messages: KDC→{u14,…,u17}:{(xg3′′′,yg3′′′)}KK1417′′KDC→{u12,u13}:{(xg3′′′,yg3′′′)}K1113,{K1113}K1213KDC→u11:{(xg3′′′,yg3′′′)}K1113, {K1113}K11-1, {K11-1}K11.Figure 7
Key tree structure for multiple groups after useru5 leaves the group P3.If a member leaves the groupPi, which contains Ni members, then ⌈log2Ni⌉ values are changed, ⌈2log2Ni⌉ number of encryptions are performed, and ⌈log2Ni⌉ rekey messages are constructed to convey changed keys to the members of the group.


### 5.5. Member Moving from One Secure Group to Another

There are two cases.Case 1.
A memberum wants to move from group Pi to the group Pj.(i)
um sends a move request to KDC.(ii)
This request is interpreted as member leave event for the groupPi and member join event for group Pj.(iii)
KDC detachesul from the LKT of the group Pi.(iv)
To provide forward access control for groupPi, KDC changes the keys along the path from the leaving point till one level below the root in the LKT of group Pi.(v)
KDC insertsunew in LKT of the group Pj.(vi)
To provide backward access control in groupPj, KDC changes the keys along the path from insertion point till the root in LKT of group Pj.(vii)
To change group keys of the groupsPi and Pj, KDC changes group shares (xgi,ygi) and (xgj,ygj).(viii)
KDC conveys securely changed keys and group shares to corresponding members of the groupsPi and Pj.Case 2.
A memberum∈Pi wants to join the group Pj.(i)
um sends a join request to KDC.(ii)
KDC insertsum in the LKT of group Pj.(iii)
To provide backward access control in groupPj, KDC changes the keys along the path from insertion point till the root in the LKT of group Pj.(iv)
To change group key ofPj, KDC changes group share (xgj,ygj).(v)
KDC conveys securely changed keys and group share to corresponding members of the groupPj.To illustrate the member-moving scenario, consider Figure7 and assume that user u4 wants to move from group P1 to group P2. It sends to KDC the move request. KDC inserts u4 in the group P2 as shown in Figure 8 and changes the keys K34 and K14 in group P1 and the keys K17-1, K17-2 in group P2. It picks new values for group shares (xg1,yg1) and (xg2,yg2), and, in order to convey changed keys and shares securely, it constructs the following rekey messages: KDC→{u1,u2}:{K13}K12,{(xg1′,yg1′)}K13KDC→u3:{K13}K3-1,{K3-1}K3,{(xg1′,yg1′)}K13KDC→{u5,u7}:{(xg1′,yg1′)}K58KDC→{u6,u8}:{(xg1′,yg1′)}K58,{(xg2′,yg2′)}G2′KDC→{u9,u10}:{(xg2′,yg2′)}G2′KDC→u17:{K417-2}K417-1, {K417-1}K17, {(xg2′,yg2′)}G2′KDC→u4:{K417-2}K417-1,{K417-1,(xg2′,yg2′)}K4.Figure 8
Key tree structure for multiple groups after useru4 moves from group P1 to group P2.Thus, when a member moves from one group withNi members to another group with Nj members, ⌈log2Ni+log2Nj⌉ keys are changed, ⌈2(log2Ni+log2Nj)⌉ encryptions are performed, and ⌈log2Ni+log2Nj⌉ rekey messages are constructed.


### 5.6. Storage

If there areNi users in group Pi, then the height of the LKT for Pi is ⌈log2Ni⌉. A user u of the group Pi stores ⌈log2Ni⌉-1 auxiliary keys, (t-1) prepositioned shares and an AS. If a user u is a member of j number of groups, it needs to store ∑i=1j‍(⌈log2Ni⌉-1) auxiliary keys, (t-2+j) prepositioned shares, and an AS. Thus, even though a particular user belongs to all the M groups in the system, it needs to store at most ∑i=1M‍⌈log2Ni⌉+t-2 elements from GF(p) and can compute keys for all the groups.We plot the graphs to depict the percentage of savings achieved in storage cost and encryption cost when compared to Dexter et al. scheme. The graph in Figure9 shows the percentage of savings achieved in storage at KDC. It is plotted for different values of the security parameter t. Figures 10 and 11 show the percentage of savings with users in different layers. They are plotted by keeping the value of t as 5 and 10, respectively. From the graphs it is clear that the storage savings at KDC varies from 75% to 95% and with the users it varies from 68% to 73%. Figures 12 and 13 show the percentage savings in encryption cost that are plotted by keeping the value of t as 5 and 10, respectively. Savings in encryption cost vary from 45% to 85%, and it is observed that the the percentage of savings is proportional to the value of t. As we move from lower layers to higher layers, the cost of savings decreases.Figure 9
Storage cost: percentage savings at the KDC.Figure 10
Storage cost: percentage savings at the users witht=5.Figure 11
Storage cost: percentage savings at the users witht=10.Figure 12
Encryption cost: percentage savings witht=5.Figure 13
Encryption cost: percentage savings witht=10.


## 5.1. Key Management Scheme

We consider a set of usersU={u1,u2,…,uN} and M subgroups P1,P2,…,PM such that some users are present in more than one subgroup. For each subgroup Pi, a logical key tree is constructed, i=1,2,…,M. The height of the tree for subgroup Pi depends on the number of users in Pi. If there are Ni (Ni≤N) number of users in group Pi, then the height is hi=⌈log2Ni⌉. An user ui is assigned with a private key Ki, i=1,2,…,N and auxiliary keys along the path from ui to root of the key tree. This section deals about initial group setup and computation of group key(s).


## 5.2. Initial Group Setup and Group Key Computation

Our scheme is based on centralized key management scheme using logical key tree (LKT) approach as proposed in [7]. Hence, we assume a trusted KDC which is responsible for initial group(s) setup and rekeying operations. Users in the system are provided with unique identification number, and the groups are assigned with group numbers. To begin with we allow the KDC to fix the security parameter t.  (1)
Userui, i=1,2,…,N who would like to join the group Pj, j=1,2,…,M sends a join request to KDC. The KDC generates and sends a unique private key Ki, i=1,2,…,N to the requesting user ui over a secure channel (we assume that, at the initial stage, a secure channel is established between KDC and the joining user). Hence, every user shares a private key with the KDC.(2)
KDC selects randomlyt-2 number of points (xi,yi) in GF(p) called  prepositioned basic shares, i=1,2,…,t-2 and (xt,yt) as activating share (AS). These shares are sent  securely to the members of all the subgroups P1,P2,…,PM.(3)
KDC selects randomlyM points (xgi,ygi) in GF(p) called  prepositioned group shares distinct from the previously selected points and sends (xgi,ygi) securely to the members of the subgroup Pi, i=1,2,…,M.(4)
KDC constructs LKT for the groupPi with the group key Gi. The key Gi is obtained by constructing a polynomial Pi(x) of degree t-1 using the shares (xi,yi) of step 2 and the prepositioned group share (xgi,ygi). The group key is Gi=Pi(0), i=1,2,…,M. KDC sends  secretly to each user u of Pi, all the auxiliary keys along the path of LKT from the leaf u to the root.(5)
If an useru is a member of j number of groups (1≤j≤M), it is provided with (t-2) prepositioned basic shares along with AS and j number of prepositioned group shares. It constructs j distinct polynomials. A polynomial Pk(x) is constructed by using t-1 shares of step 2 and prepositioned group share (xgk,ygk), k=1,2,…,j. Thus, it can construct j distinct polynomials just by using one distinct group share.Figure4 shows an example key tree structure with 3 groups, namely, P1, P2, and P3 set up simultaneously. Group P1 comprises of eight members u1,u2,…,u8, group P2 contains u6, u8, u9, and u10 as its members, whereas members u5, u11, u12, u13, u14, and u15 belong to group P3. In Figure 4, u-nodes represent users, and K-nodes represent keys. Key nodes K1 through K15 are private keys of users u1 through u15, respectively, and remaining K-nodes in the figure represent auxiliary keys. G1, G2, and G3 are the group keys of the groups P1, P2, and P3, respectively.Figure 4
Key tree structure for multiple groups.For example, let us considert=4,  p=41 and the (t-2) prepositioned basic shares as (1,28), (2,23) and AS as (4,4). Assume that KDC sends (3,11), (3,8), and (3,5) as the prepositioned group share for the members of the groups P1,P2, and P3, respectively. Hence, the members of the group Pi, i=1,2,3, now possess t; that is, 4 shares with them, and they can construct (t-1) degree polynomial and evaluate it at 0 to get the group key. Thus the members of group P1 get the group key G1 as 14, members of P2 get the group key G2 as 2, and G3 is computed by members of P3 as 34. Hence, user U5, for instance, can compute group keys for both the groups P1 and P3.


## 5.3. Member Join Event

If a new userunew wants to join the group Pi(1≤i≤M), it sends a join request to KDC. KDC finds a location for the user unew in the LKT of Pi and inserts it. To provide backward access control, keys along the path from the point of insertion till one level below the root are changed and communicated to the corresponding users. In order to change the group key Gi of Pi, KDC picks a new value of group share (xgi,ygi), encrypts it with the previous group key Gi, and sends it to the users of the group Pi. For the user unew, KDC sends keys along the path from unew to root, prepositioned shares (basic shares and group share) and AS after encrypting with the private key of unew. The new user constructs the polynomial and evaluates it at 0 to get the group key Gi.For instance, if a new useru16 sends a join request to join the group P3, KDC inserts u16 at the location as shown in Figure 5. KDC changes the key K1417 to K1417′ and picks a new value for group share, say (xg3′,yg3′). To convey changed keys and share to corresponding users, KDC constructs the following rekey messages: KDC→{u14,u15}:{K1417′}K1415,{(xg3′,yg3′)}G3KDC→{u5,u11,u12,u13}:{(xg3′,yg3′)}G3KDC→{u16}:{K1617,K1417′,(xg3′,yg3′)}K16.Figure 5
Key tree structure for multiple groups after useru16 joins the group P3.Now, suppose that if useru17 sends join requests to join two groups P2 and P3, the LKT looks as in Figure 6 after inserting u17 to both the groups of Figure 5. KDC constructs the following rekey messages to convey changed keys and group shares: KDC
→{u14,u15}:{K1417′′}K1415,  {(xg3′′,yg3′′)}G3′KDC
→{u5,u11,u12,u13}:{(xg3′′,yg3′′)}G3′KDC
→{u16}:{K1417′′}K1417′,  {K1417′}K16,  {(xg3′′,yg3′′)}G3′KDC
→{u6,u8,u9,u10}:{K610,(xg2′,yg2′)}G2KDC
→{u17}:{K17-2,K17-1, K1617′,K1417′′, (xg3′′,yg3′′)}K17.Figure 6
Key tree structure for multiple groups after useru17 joins the groups P2 and P3.If a member joins a groupGi with Ni members, then at most ⌈log2Ni⌉ keys are changed. To convey changed keys to the members of the group, ⌈2log2Ni⌉ encryptions are performed and ⌈log2Ni⌉ rekey messages are constructed. In general, if a member joins j number of groups, ∑i=1j‍log2Ni keys are changed, 2∑i=1j‍log2Ni encryptions are performed, and ∑i=1j‍log2Ni rekey messages are constructed.


## 5.4. Member Leave Event

A member may leave the group either voluntarily or KDC may forcibly expel the member from the group. In any case, the keys known to leaving member in the LKT must be changed to provide forward confidentiality. If a memberul wants to leave the group Pi(1≤i≤M), it sends a leave request to KDC. Here, we encounter two cases.Case 1.
Iful belongs to only one group Pi,(i)
KDC removes the corresponding user-node and private key-node from LKT,(ii)
KDC changes the keys along the path from leaving point till one level below the root inPi selects new group share (xgi,ygi) and conveys to corresponding users in Pi.Case 2.
Iful belongs to more than one group,  (i)
KDC detachesul from the group Pi,(ii)
KDC changes the keys along the path from leaving point till one level below the root inPi selects new group share (xgi,ygi) and conveys to corresponding users in Pi.For example, consider the multiple groups scenario as in Figure6. Now, if user u5 wants to leave the group P3, it sends a leave request to KDC. KDC detaches u5 from the LKT of P3 and changes the keys along the path as shown in Figure 7, and to convey changed keys it constructs the following rekey messages: KDC→{u14,…,u17}:{(xg3′′′,yg3′′′)}KK1417′′KDC→{u12,u13}:{(xg3′′′,yg3′′′)}K1113,{K1113}K1213KDC→u11:{(xg3′′′,yg3′′′)}K1113, {K1113}K11-1, {K11-1}K11.Figure 7
Key tree structure for multiple groups after useru5 leaves the group P3.If a member leaves the groupPi, which contains Ni members, then ⌈log2Ni⌉ values are changed, ⌈2log2Ni⌉ number of encryptions are performed, and ⌈log2Ni⌉ rekey messages are constructed to convey changed keys to the members of the group.


## 5.5. Member Moving from One Secure Group to Another

There are two cases.Case 1.
A memberum wants to move from group Pi to the group Pj.(i)
um sends a move request to KDC.(ii)
This request is interpreted as member leave event for the groupPi and member join event for group Pj.(iii)
KDC detachesul from the LKT of the group Pi.(iv)
To provide forward access control for groupPi, KDC changes the keys along the path from the leaving point till one level below the root in the LKT of group Pi.(v)
KDC insertsunew in LKT of the group Pj.(vi)
To provide backward access control in groupPj, KDC changes the keys along the path from insertion point till the root in LKT of group Pj.(vii)
To change group keys of the groupsPi and Pj, KDC changes group shares (xgi,ygi) and (xgj,ygj).(viii)
KDC conveys securely changed keys and group shares to corresponding members of the groupsPi and Pj.Case 2.
A memberum∈Pi wants to join the group Pj.(i)
um sends a join request to KDC.(ii)
KDC insertsum in the LKT of group Pj.(iii)
To provide backward access control in groupPj, KDC changes the keys along the path from insertion point till the root in the LKT of group Pj.(iv)
To change group key ofPj, KDC changes group share (xgj,ygj).(v)
KDC conveys securely changed keys and group share to corresponding members of the groupPj.To illustrate the member-moving scenario, consider Figure7 and assume that user u4 wants to move from group P1 to group P2. It sends to KDC the move request. KDC inserts u4 in the group P2 as shown in Figure 8 and changes the keys K34 and K14 in group P1 and the keys K17-1, K17-2 in group P2. It picks new values for group shares (xg1,yg1) and (xg2,yg2), and, in order to convey changed keys and shares securely, it constructs the following rekey messages: KDC→{u1,u2}:{K13}K12,{(xg1′,yg1′)}K13KDC→u3:{K13}K3-1,{K3-1}K3,{(xg1′,yg1′)}K13KDC→{u5,u7}:{(xg1′,yg1′)}K58KDC→{u6,u8}:{(xg1′,yg1′)}K58,{(xg2′,yg2′)}G2′KDC→{u9,u10}:{(xg2′,yg2′)}G2′KDC→u17:{K417-2}K417-1, {K417-1}K17, {(xg2′,yg2′)}G2′KDC→u4:{K417-2}K417-1,{K417-1,(xg2′,yg2′)}K4.Figure 8
Key tree structure for multiple groups after useru4 moves from group P1 to group P2.Thus, when a member moves from one group withNi members to another group with Nj members, ⌈log2Ni+log2Nj⌉ keys are changed, ⌈2(log2Ni+log2Nj)⌉ encryptions are performed, and ⌈log2Ni+log2Nj⌉ rekey messages are constructed.


## 5.6. Storage

If there areNi users in group Pi, then the height of the LKT for Pi is ⌈log2Ni⌉. A user u of the group Pi stores ⌈log2Ni⌉-1 auxiliary keys, (t-1) prepositioned shares and an AS. If a user u is a member of j number of groups, it needs to store ∑i=1j‍(⌈log2Ni⌉-1) auxiliary keys, (t-2+j) prepositioned shares, and an AS. Thus, even though a particular user belongs to all the M groups in the system, it needs to store at most ∑i=1M‍⌈log2Ni⌉+t-2 elements from GF(p) and can compute keys for all the groups.We plot the graphs to depict the percentage of savings achieved in storage cost and encryption cost when compared to Dexter et al. scheme. The graph in Figure9 shows the percentage of savings achieved in storage at KDC. It is plotted for different values of the security parameter t. Figures 10 and 11 show the percentage of savings with users in different layers. They are plotted by keeping the value of t as 5 and 10, respectively. From the graphs it is clear that the storage savings at KDC varies from 75% to 95% and with the users it varies from 68% to 73%. Figures 12 and 13 show the percentage savings in encryption cost that are plotted by keeping the value of t as 5 and 10, respectively. Savings in encryption cost vary from 45% to 85%, and it is observed that the the percentage of savings is proportional to the value of t. As we move from lower layers to higher layers, the cost of savings decreases.Figure 9
Storage cost: percentage savings at the KDC.Figure 10
Storage cost: percentage savings at the users witht=5.Figure 11
Storage cost: percentage savings at the users witht=10.Figure 12
Encryption cost: percentage savings witht=5.Figure 13
Encryption cost: percentage savings witht=10.


## 6. Authenticated Secure Group Communication

Once the groups are set up, members of the group can communicate with each other securely. When a memberui, i=1,…,N of group Pj, j=1,…,M sends an encrypted message to members of Pj, they must identify that the message is from ui and also if any other user uq tries to act as ui, others must identify that it is not ui. This section briefs about the authenticated secure group communication. Protocol in Table 3 depicts authenticated communication between group members. In the protocol, the symbol ∥ denotes concatenation, and EK[m] denotes message m encrypted with key K.Table 3
Protocol for authenticated secure group communication.
(1)
u
i
→ KDC: EKi [IDi∥Pj∥T]
(2)
KDC→ui: EKi [r∥Pj∥T]
(3)
KDC→{Members ofPj}: EGj[H(r)∥IDi∥Pj∥T]
(4)
u
i
→
{
Members of
P
j
}: EGj [r∥IDi∥Pj∥T∥m]If userui, i=1,…,N wants to send a message to group members, it sends a request to KDC. Request includes identity IDi of ui, group number Pj, j=1,…,M and a time stamp value T. KDC picks a random number r from GF(p), applies hash function to compute H(r), and broadcasts [H(r)∥IDi∥Pj∥T] after encrypting with group key Gj, so that only the members of group Pj can decrypt it. KDC sends ui, the message, [r∥Pj∥T] after encrypting it with the private key of ui. Thus, the value of r is available only to ui. Now, ui in order to send a message, m, constructs the message [r∥IDi∥Pj∥T∥m], encrypts it with the group key Gj, and sends. Only members of group Pj can decrypt it and apply hash function for the received value of r to compute H(r) and verify that this value is same as the one received from KDC. If it is true, then they realize that the message is from ui as it is claimed; otherwise, they realize that some one else is trying to impersonate as ui.


## 7. Conclusion

Managing multiple groups with overlapped membership is one of the important issue in group communication scenario. In this paper we proposed a scheme for such hierarchical group key management using a combination of key-based and share-based approach. It is possible for the members at higher layers to compute the keys for its own layer along with all its descendant layers just by storing extra prepositioned information. Our scheme is secure, even if a member compromises, it is not possible to get the group key unless activating share is obtained. We reduce both storage and encryption cost compared to Dexter et al. scheme. We proposed two schemes for periodic rekeying.Managing group keys for independent simultaneous secure groups is an important issue in SGC. In this paper we considered such multiple secure groups with overlapped membership and proposed a key management scheme using a combination of key-based and share-based approach. We showed that, even if a particular user belongs to allM secure groups, it needs to store at most (Mh+t-2+M) elements from GF(p) and is able to compute keys for all the groups. Encryption cost and number of key changes are of the order of logN for membership changes (join, leave, and a member moving from one group to another). We also provided authentication for the messages communicated between group members.



---

*Source: 383218-2012-08-01.xml*