Page:Efficient and Secure Group Messaging.pdf/9

This update operation is how a tree starts in the first place: Each member contributes an initial value to begin with, and each time a member does an update operation it fills out its direct path to the tree. If all members performed this operation there would be a complete tree (though it is possible to get to a complete tree without all doing so).

This tree structure is incredibly powerful because we effectively have a symmetric group key derivable from each binary subtree in this graph. For instance, if $S'=\{Carol,Derek\}$ then it is easy enough to see that they can communicate already by using $x_{6}$. More importantly, thanks to the deterministic Key Encapsulation Method, the public key $\beta _{6}$ from the computation $(\alpha _{6},\beta _{6},c_{6})=KEM(x_{6})$ can be used by other nodes to encrypt values for this subgroup without being member to S'.

In this fashion, we can now complete the definition for an update operation such that the tree invariant continues holding for the whole tree:

Definition 5 TreeKEM Update Operation

1. The updating member computes a new secret value $X_{0}$ and propagates it up the direct path to the root, recursively computing $H(X_{i})=H(X_{i-1})$ for each subsequent value recursively.
2. For all members that can no longer hash up their direct path to the root, the updating member computes the least number of common ancestors whom if they had the new values would ensure that all group members can reach the root. The algorithm for this computation will be provided later. Once those nodes get the missing value as an encryption to their public KEM key, they can synchronize their view of the tree.
3. The updating member computes the KEM of its newly generated node values and posts publicly the public keys of these nodes to all members of the tree, to be used for future updates.

Members receiving information about updates should verify that the update is authenticated from a verified group member (using a signature scheme), compute similarly which is the common ancestor that they are part of (which S' do they belong to that received the new secret values), use their private key for that subtree to decrypt the value, and then propagate it up to the root using H along its direct path to compute the new key value for the group.

The problem of "which nodes need to receive encrypted values", or as I wrote earlier, computing "the least number of common ancestors whom if they had the new values would ensure that all group members can reach the root" is quite a simple one. Since each node's value is the hash of only one of two children, then the child that was not used to generate the parent is the one that no longer shares knowledge of the root key. It is these non-updated children that need to be given knowledge of the parent value via an encrypted ciphertext in order to complete the full tree path to the root node. Therefore, we can identify such nodes simply by looking at the one and only sibling at each level of the direct path. This of course assumes we already have a completed tree. Update operations for trees with blank intermediate nodes are less efficient.

9