Postscript document

Notation

 

We use the following notation:

$n,N$   number of protocol parties (group members)

$i,j$   group member indices:

$M$_i   $i$-th group member;

$r$_i   $M$_i's session random (secret key of leaf node $M$_i)

$br$_i   $M$_i's blinded session random, i.e. $r$_i p

$k$_j   secret key shared among $M$₁...$M$_j

$bk$_j   blinded $k$_j, i.e. $k$_j p

$p$   large prime number

$\alpha$   exponentiation base

$N$_j   Tree node $j$

$IN$_l   Internal tree node at level $l$

$LN$_i   Leaf node associated with member $M$_i

$T$_i   Tree of member $M$_i

$BT$_i   Tree of member $M$_i including all of its blinded keys

  
Figure 1: Notation for STR

Figure 1 shows an example of an STRkey tree. The tree has two types of nodes: leaf and internal. Each leaf node is associated with a specific group member. An internal node $IN$_i always has two children: another (lower) internal node $IN$_i-1 and a leaf node $LN$_i+1 . The exception is $IN$₁ which is also a leaf node corresponding to $M$₁. (Note that, consequently, $r$₁=k₁.)

Each leaf node $LN$_i has a session random $r$_i chosen and kept secret by $M$_i. The blinded version thereof is $br$_i = ⁴r_i p.

Every internal node $IN$_j has an associated secret key $k$_j and a public blinded key $bk$_j = ⁵k_j p. The secret key $k$_i (i > 1) is the result of a Diffie-Hellman key agreement between the node's two children. ($k$₁ is an exception and is equivalent to $r$_i.) $k$_i  (i > 1) is computed recursively as follows:

$k$_i = (bk_i-1)⁴r_i p = (br_i)⁴k_i-1 p = ⁴r_ik_i-1 p if $i\; >\; 1$.

The group key in Figure 1 is the key associated with the root node:

$k$₄ = ⁴r₄⁴r₃⁴r₂r₁

We note that the root (group) key is never used directly for the purposes of encryption, authentication or integrity. Instead, such sub-keys are derived from the root key, e.g., by applying a cryptographically secure hash function to the root key. All blinded keys $bk$_i are assumed to be public.

The basic key agreement protocol is as follows. We assume that all members know the structure of the key tree and their initial position within the tree. (It is simple to have an ordering that uniquely determines the location of each member in a key tree.) Furthermore, each member knows its session random and the blinded session randoms of all other members. The two members $M$₁ and $M$₂ can first compute the group key corresponding to $IN$₂ . $M$₁ computes:

$k$₂ = (br₂)⁴r₁ p = ⁴r₁r₂ p, bk₂ = k₂ p k₃ = (br₃)⁴k₂ p, bk₃ = k₃ p ... k_N = (br_N)⁴k_N-1 p

Next, $M$₁ broadcasts all blinded keys $bk$_i with $1\; \le i\; \le N-1$. Armed with this message, every member then computes $k$_N as follows. (As mentioned above, members $M$₁ and $M$₂ derive the group key without additional broadcasts.) Any $M$_i (with $i>2$) knows its session random $r$_i and $bk$_i-1 from the broadcast message. Hence, it can derive $k$_i = bk_i-1⁴r_i p. It can then compute all remaining keys recursively up to the group key from the public blinded session randoms: $k$_i = br_i+1⁴k_i p ($i\; \le N$).

Following every membership change, all members independently update the key tree. Since we assume that the underlying group communication system provides view synchrony (see Section 2.1), all members who correctly execute the protocol recompute an identical key tree after any membership event. The following fact describes the minimal requirement for a group member to compute the group key:
 

Proof. This follows directly from the recursive definition of the group key. In other words, both $M$₁ and $M$₂ (the member at the lowest leaf nodes) can obtain the group key by computing pairwise keys recursively and using blinded session randoms of other members.

 

Proof. This also follows from the definition of the group key. To compute the group key, member $M$_i needs 1) $r$_i, 2) $bk$_i-1, and 3) $br$_i+1,br_i+2,&ldots;,br_N.

The protocols described below benefit from a special role (called sponsor) assigned to a certain group member following each membership change. A sponsor reduces communication overhead by performing "housekeeping" tasks that vary depending on the type of membership change. The criteria for selecting a sponsor varies as described below.