Page:Efficient and Secure Group Messaging.pdf/6

keys reduce to elements in G themselves, they can now be used as private keys in a meta-Diffie-Hellman computation of $g^{g^{\alpha \beta }g^{\gamma \delta }}$, the shared key of the entire tree.

With any such structure, and one that may soon be rotating keys using a ratchet step, we aim to fulfill the following

Definition 3 Tree invariant

Each node represents a secret that is only known to its children (and recursively to those children's children). In such a way, the root is by induction always supporting a key known to every group member. Even as node values change this property remains unchanging.

The number of needed operations to initialize this structure (despite the use of a tree) remains $O(n)$. Suppose that there are n group members and therefore n leaves, then just for the first level of computations we must perform ${\frac {n}{2}}=O(n)$ Diffie-Hellman computations. In fact, so long as the structure is based on each member contributing a secret, there will have to be that many operations to initialize; however, our aim is to allow the tree to be updated to provide break-in recovery without rebuilding the whole tree with linear time complexity.

Suppose that Alice changed her public/private key pair to $(\alpha ',g^{\alpha '})$, then rebuilding the tree with the updated value takes fewer operations as half of the tree (either the left of the root or the right root) would not need to be re-computed. However, such an update operation on a Diffie-Hellman tree still remains linear in time-complexity despite the reduced number of operations because half of the tree has to be re-computed and updated if a leaf is changed.

Next, I will review Key Encapsulation Method and its use with trees to achieve a structure in which updating a value can be done with only $O(\log n)$ operations.

6TreeKEM: Key Encapsulation Method

Key encapsulation refers to the encapsulation of a key inside of a public/private key structure. Let $k\in {\mathcal {K}}$ be a key in the symmetric key space ${\mathcal {K}}$ which Alice wants to post to other people in a secure way. Then, using public-key private key cryptography (and any algorithm of choice of a public key system), Alice can transmit this key securely to another member. However, in a group setting, Alice needs to encrypt the key separately for each member. If Alice then wants to use a new encryption key, she needs again to re-encrypt the key separately for each member.

Instead of this inefficient approach, we instead consider a similar approach to a tree with the invariant that each node represents values that are known to all of its children and those children's children.

Let S be a set of members wishing to communicate in a group, and let $S'\subset S$ be a subset of S that may represent a sub-tree in a tree structure as described above. In addition to each individual member having their public/private key pair that might be available in a public authenticated directory, the entire sub-group in this structure will have its own private/private key pair, $(s,g^{s})$ where the private key s would be a shared-key between all $|S'|$ members in the group. In this way, new symmetric keys can be encrypted and sent to the entire subgroup with one operation $c=Enc(g^{s},k)$

6