Merge Protocol. In the first round of the merge protocol, all sponsors (members associated with topmost leaf node in each tree) exchange their respective key trees containing all blinded session randoms.3 The highest-numbered member of the largest tree becomes the sponsor of the second round in the merge protocol. After refreshing its session random, this sponsor computes every (key, bkey) pair up to the intermediate node just below the root node using the blinded session randoms of the other group members. It then broadcasts the key tree with the bkeys and blinded session randoms to the other members. All members now have the complete set of bkeys, which allows them to compute the new group key. k’7 New Node k’6 ,bk6’ r 7, br7 M 7 k’5,bk’5 r 6, br6 M 6 M 1 M 2 k 7 k’4,bk’4 r 5, br5 k 3,bk 3 r’4 ,br’4 M 5 k 6,bk 6 r 7, br7 M 7 k 2,bk 2 M 4 r 5/k5, br5 / bk5 r 6, br6 r 1/k1, br1 / bk1 r 2, br2 r 3, br3 M 3 k4 k 3,bk 3 k 2,bk 2 r 4, br4 M 4 r 1/k1, br1 / bk1 r 2, br2 r 3, br3 M 3 M 5 M 6 M 1 M 2
Merge Protocol. After the network failure recovers, subgroup may need to be merged back into a single group. We now describe the merge protocol for k merging groups. In the first round of the merge protocol, each sponsor (the rightmost mem- ber of each group) broadcasts its tree with all bkeys to all other groups after updating the secret share of the sponsor and relevant [key, bkey] pairs up to the root node. Upon receiving these message, all members can uniquely and inde- pendently determine how to merge those k trees by tree management policy. Next, each sponsor computes [key, bkey] pairs on the key-path until either this computation reaches the root or the sponsor can not compute a new intermediate key. The sponsor broadcast his view of the tree to the group. All members then update their tree views with the new information. If the broadcasting sponsor computed the root key, upon receiving the broadcast, all other members can compute the root key as well.
Merge Protocol. The communication overhead of the merge protocol may appear high. However, this is not the case. Let us assume merging groups. In the first round, a sponsor in each group broadcasts its key tree after updating its session random. Upon receiving these broadcast messages, every member rebuilds a key tree which has some missing bkeys. At most paths will have missing bkeys. Propagating these bkeys requires at most rounds, since each sponsor (in each subsequent round) computes bkeys as far as it can. Therefore, a merge of groups takes at most rounds. The maximum number of messages is . The number of modular exponentions for the worst and the best case is same as that of join protocol, since rebuilding the whole key tree requires same amount of serial number of modular exponentions as joining to the leaf node. Figure 9 shows an example of two merging groups, where the sponsors and broadcast their trees ( and
Merge Protocol. After M2 computes keys and blinded keys 90
Merge Protocol. To merge number of small groups into one large group, the merge protocol runs concurrently in ⌈log2 ⌉ rounds. For each run of the protocol, we obtain a merged group of two subgroups. For example, as shown in Figure 6, six small groups {1, 2, 3, 4, 5, 6} are merged into one large group 16 in sponsor node updated −1, it will still use the old value of −1
Merge Protocol. Step 1 : All sponsors Msi in each Tsi – generate new share and compute all [key, bkey] pairs on the key-path of Tsi , ^ i k – broadcast updated tree T^si including only bkeys. Msi Ts (BKs∗ ) i −−−−−−−−−−−−→ i=1 Ci Step 2 : Every member – update key tree by adding new trees and new intermediate nodes, – remove all keys and bkeys from leaf node related to the sponsor to the root node. Each Sponsor Mst additionally – compute all [key, bkey] pairs on the key-path until it can proceed, ^ st t k – and broadcast updated tree T^st including only bkeys. Mst Ts (BK∗ ) −−−−−−−−−−−−→ i=1 Ci Step 3 to h (Until a sponsor Msj could compute the group key) : For each sponsor Mst – computes all [key, bkey] pairs on the key-path until it can proceed, ^ st t – and broadcasts updated tree T^st including only bkeys. Mst Ts (BK∗ ) −−−−−−−−−−−−→ i=1 Ci k Step h + 1 : Every member computes the group key using T^s point multiplications. The serial cost assumes parallelization within each proto- col round and presents the greatest cost incurred by any participant in a given round(or protocol). The total cost is simply the sum of all participants’ costs in a given round(or protocol). Table 6 summarizes the communication and computation costs of TGDH and our protocol. The number of current group members, merging groups and leaving members are denoted by n, k and p, respectively. The overhead of protocol depends on the tree height, the balance of the key tree, the location of the joining tree and the leaving nodes. In our analysis, we assume the worst case configuration and list the worst-case cost for TGDH and our protocol. Since we modified TGDH protocol, the number of communication is equals to TGDH except the number of rounds in merge and key length. But our proposed protocol can reduce the number of computation in each event operation because of low height of key tree. The number of pairings and point multiplications for Tree T5 <0,0> <1,0> <1,1> <1,2> <2,0> <2,1> <2,2> <2,3> <2,4> <2,5> <2,6> <2,7> <2,8> M4 M5 M6 M7 M8 M9 X00 X00 Sponsor <3,0> <3,1> <3,2> M1 M2 X0 Xxxx X00 <0,0> <1,0> <1,1> <1,2> X00 X00 X00 Tree T5 <0,0> New Intermediate Node <1,0> <1,1> <1,2> <2,0> <2,1> <2,2> <2,3> <2,4> <2,5> <2,6> <2,7> <2,8> M6 M7 M8 M9 X00 X00 <3,0> <3,1> <3,2> <3,3> <3,4> <3,5> <3,6> <3,7> M1 M2 M3 M12 M13 M15 M4 M5 New Members Current Members Fig. 5. Tree-updating in merge operation Table 6. Communication and Computation Costs Communication Computation Rounds Messages Exponentiations Pairi...
Merge Protocol. Compared to CLIQUES, the main virtue of TGDH is that it is much simpler to merge two or more groups. Multiple join can be processed as follows. The protocol assumes that m members want to join group G1. The m individual members form a TGDH group G2. Then G2 merges with G1. The protocol considers first the merge of two groups. It can be simply extended to the merge of more than two groups, say k > 2, groups by executing the two-group merge k − 1 times. First the two trees are ordered from the highest to lowest, denoted T1 and T2. If they are of the same height, they are ordered according to some other criteria. T2 joins to T1, and the insertion point is determined. If the two trees are of the same height, it joins simply T2 to the root node of T1. Otherwise it first tries to find the rightmost shallowest node where the join would not increase the overall tree height. If no such node exists, the insertion point is the root node. Assume that we have m trees to be merged. They can be ordered from the highest to the lowest: T1, · · · , Tm. To perform merge, each tree Ti has its rightmost shallowest leaf node as sponsor Msi . The process is illustrated as follows:
Merge Protocol. The key tree allows relatively simple merge of two groups. The merge protocol covers also the multiple join. The smaller group is merged onto the larger one, i.e. to place a smaller key tree directly on top of the larger one. If group sizes are equal, it can order them according to some other criteria. A new intermediate node N with two children is created. The root of the larger tree becomes the left child of N, while the lowest- numbered leaf of the smaller trees becomes the right child of N. The root of smaller tree becomes the root of the new tree. IN4 k4 IN2 k2, bk2 k3, bk3 s4, br4 LN4/M4 s3, br3 LN3/M3 IN2 IN3 k2, bk2 k3 s3, br3 LN3/M3(M4) IN1 s1/k1, br1/bk1 s2, br2 IN1 s1/k1, br1/bk1 s2, br2 Sponser LN1/M1 LN2/M2 LN1/M1(M2) LN2/M2(M3)
Merge Protocol. In this instant assume that m merging group needs to merge with c current group. The existing merging group director detects to achieve maximum signal strength what is measured as the closest member between itself and current group members. The current group director is the member what has maximum signal strength with merging group director. After the merging process, the leftest leaf of shorter tree becomes the right child of a new intermediate node. The root of the longer tree is left child of the new intermediate node. After the current group director received the MERGE_MESSAGE message, it refreshes session random key, computes keys and blinded keys, and sends the current group’s key tree containing the all blinded keys to merging group director. Later, the merging group director updates key tree by combining the merging group’s key tree and current group’s key tree at the new root node, the director chooses session random key, computes keys and blinded keys up to the root node, and broadcasts new key tree containing the all blinded keys to all members in new group. Finally, the group key is calculated independently by each member. Figure 3.8 shows the initial situation before current group merges with other group. After that Figure 3.9 shows the example of merge operation. The member that has maximum signal strength of merging group director, M5, is M1, and then M1 is current group director. The conclusion of merge protocol is shown as follows:
Merge Protocol. Like the TBG in previous protocol, this protocol assumes that m merging group needs to merge with c current group. The existing merging group director detects to achieve maximum signal strength what is measured as the closest member between itself and current group members. The current group director is the member that has maximum signal strength with merging group director. After the merging process, the smaller group is merged onto the larger one, i.e. to place a smaller key tree directly on top of the larger one. If group sizes are equal, it can order them according to some other criteria. A new intermediate node with two children is created. The root of the larger tree becomes the left child of new intermediate node, while the deepest leaf of the smaller tree the right child of new intermediate node. The root of smaller tree becomes the root of the new tree. After the current group director receives the MERGE_MESSAGE message, it refreshes session random key, computes keys and blinded keys, and sends the current group’s key tree containing the all authenticated blinded keys to merging group director. Later, the merging group director computes blinded key of current group’s key tree, updates key tree by combining the merging group’s key tree and current group’s key tree at the new root node, the director chooses session random key, computes keys and blinded keys up to the root node, and unicasts new key tree containing the all authenticated blinded keys to all members in new group. Finally, the group key is calculated independently by each member after computed blinded key. Figure 4.7 shows the initial situation before current group merges with other group. The member that has maximum signal strength of merging group director, M6, is M4, and then M4 is current group director. After that Figure 4.8 shows the authenticated key tree that merging director, M6, received from current group director, M4. Figure 4.9 shows the authenticated key tree that M3 received from merging group director, M6, after merging group director merges the key tree. Figure 4.10 shows the key tree after M2 computes keys and blinded keys. The conclusion of merge protocol is shown as follows:
