Postscript document

Complexity Analysis

 

This section compares the computation and communication of STRprotocol to other recent group key agreement methods, Cliques GDH.2 [STW00], Tree-Based Diffie-Hellman (TGDH) [KPT00], and Burmester/Desmedt (BD) [BD94]. These protocols provide contributory group key agreement based on different extensions of the two-party Diffie-Hellman key exchange. Moreover, they all support dynamic membership operations.

We consider the following costs:

$$ Number of rounds: this affects serial communication delay. Total number of messages: as the number of messages grows, the probability of message loss or corruption is increased, and so is the delay.

$$ Number of unicasts and broadcasts: a broadcast is much more expensive operation than a unicast, since it requires many acknowledgments within the group communication system.

$$ Number of serial exponentiation: this is the main factor in the computation overhead.

$$ Robustness: Lack of robustness requires additional measures to make the secure group communication system robust against cascaded (nested) faults and membership events.

Table 1 shows a comparison of the current approaches for group key management. The bold text refers to a parameter that severely slows down the protocol in a WAN deployment, for which STRis best suited.

In Cliques GDH.2 protocol, the number of new members $k$ is considered, since the merge cost depends on number of new members. The cost for TGDH is the average value when the key tree is fully balanced. The partition or leave cost for STRis computed on average, since it depends on the depth of the lowest-numbered leaving member node. For security reasons [STW00], BD always has to restart anew upon every membership event.

As seen from the table, STRis minimal in communication on every membership event. We showed in Section 5 that robustness in the STRprotocol is not only easier to implement than in other protocols, but it also achieves higher robustness to network partitions. Cliques GDH.2 is quite expensive protocol in wide area network, since: 1) it is hard or very expensive to provide robustness against cascaded events [AKNR$+$01] and 2) communication cost for merge increases linearly as the number of new members does. In TGDH, the partition protocol is expensive (relatively slow) which may cause more cascaded faults and long delays to agree on a key. The cost of BD is mostly acceptable but large number of simultaneous broadcast messages can be problematic over a wide area network.

 

 

Rounds Messages Ucast Bcast Exp. Robust

30.8cmCliques J 2 2 1 1 $2n$ 30.5cmHard

L/P 1 1 0 1 $n$

M $k+3$ $n+2k+1$ $n+2k-1$ 2 $n+2k$

30.8cmTGDH J/M 2 3 0 3 $2logn$ 30.5cmEasy

L 1 1 0 1 $logn$

P $O$(log n) $O$(log n) 0 $$O(log n) $O(logn)$

BD $2$ $2n$ 0 $2n$ $3$ Easy

30.8cmSTR J 1 2 1 1 2 30.5cmEasy

L/P 1 1 0 1 $\{3n2\}\; +\; 2$

M 2 3 2 1 $3k$ J: Join, L: Leave, P: Partition, M: Merge, Ucast: Unicast, Bcast: Broadcast, Exp: Exponentiation