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. 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. After M2 computes keys and blinded keys 90
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. As we discuss in section 3, network faults can partition a group into several subgroups. After the network faults heals, two or more subgroups may need to merge. In the first round of merge protocol, each sponsor broadcasts its tree information with all of its blinded keys to the other group. Upon receiving this message, all members can uniquely and independently determine the merge position of the two trees (for details see section 5.6). The rightmost member of the subtree rooted at the joining location becomes the sponsor of this operation. The sponsor computes every key on the key-path and the corresponding blinded keys. It, then, broadcasts the tree with the blinded keys to the other members. Figure 9 shows an example, where the sponsors M2 and M7 broadcast their trees (T2 and T7) containing all the blinded keys, along with BK and BK . Upon receiving these broadcast messages, every member checks
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)
