Postscript document

Member Leave Protocol

 

We again have a group of $n$ members when a member $M$_d $(d\; \le n)$ leaves the group. If $d>1$, the sponsor$M$_s is the leaf node directly below the leaving member, i.e., $M$_d-1. Otherwise, the sponsor is $M$₂. Upon hearing about the leave event from the group communication system, each remaining member updates its key tree by deleting the nodes $LN$_d corresponding to $M$_d and its parent node $IN$_d . The nodes above the leaving node are also renumbered. The former sibling $IN$_d-1 of $M$_d is promoted to replace (former) $M$_d's parent. The sponsor$M$_s selects a new secret session random, computes all keys (and blinded keys) up to the root, and broadcasts $BT$_s to the group. This information allows all members to recompute the new group key.

In summary, the leave protocol takes one communication round and involves a single broadcast. The cryptographic cost varies depending on two factors: 1) the position of the departed member, and 2) the position of the remaining member who needs to compute the new key.

The total number of serial cryptographic operations in the leave protocol can be expressed as (assuming $n$ is the original group size):

$$$2(n-d)+1\; +\; (n-d)\; +\; 1\; =\; 3n-3d\; +\; 2$ when $d\; >\; 2$

$$$3n-7$ when $d\; =1,\; 2$

In the worst case, $M$₁ or $M$₂ leave the group. The cost for this leave operation is equal to the leave of member $M$₃, which is $3n-7$. The average leave cost is $3\; n/2+2$.

The leave protocol provides forward secrecy since a former member cannot compute the new key owing to the sponsor's changing the session random. The protocol also provides key independence since knowledge of the new key cannot be used to derive the previous keys; this is, again, due to the sponsor refreshing its session random.