Page:Efficient and Secure Group Messaging.pdf/10

Definition 6 Algorithm for listing and encrypting updated values

Let the updating member be vertex $v\in V$ contributing a new secret value x'. Then,

1. Let sib(v) be the sibling of $v\in V$
2. Let $\beta$ be the public key of the subtree with sib(v) as root, provided by the KEM
3. Compute the value $Enc(\beta ,H(x'))$ to be sent to all group members descendant from sib(v) (or sib(v) if it is a leaf)
4. Assign $v\leftarrow parent(v)$ or end if v has no parent (and is the root)
5. Assign $x'\leftarrow H(x')$
6. Go back to step 1

With these steps, it is clear that we have to encrypt only once per level of the tree (assuming that the tree is complete and not still being filled). If there are $n=|S|$ group members, or leaves in the tree, then the time-complexity for the number of encryption operations is logarithmic in relation, $O(log(n))$, which is our desired out come.

A remove operation also becomes equally simple, essentially being an update that's performed on behalf of a removed member, with a new contribution made on their behalf which they do not know, such that the removed member no longer has access to any current keys in the tree as the entire direct path from their node gets blanked and replaced.

Likewise, an add operation becomes simple to do, similarly equivalent to a new node performing an update, though, since they are not yet part of the group, it would likewise be required for another member to perform the add on their behalf. The member performing the add operation would choose a new random secret value for the new group member, add the new group member to the tree, maintaining a left-balanced tree as much as possible so as to work nicely with the algorithm of the update operation, and then perform an update operation on that node's behalf. The member performing the add operation would then provide the remaining group members with the new $log(n)$ cipher-texts needed for them to come in sync with the tree and would encrypt a similar larger state of the tree for the new node, encrypted for their official public key provided by a trusted authenticated party.

7Conclusions

Post-compromise security can now be efficiently achieved for the group, since it is feasible with such a small number of encryption operations to update the group key regularly. Not only is it faster to compute new keys, but the size of the handshake for doing so using this update operation is quite small, since there only needs to be a logarithmic number of encrypted cipher-texts provided to each group member upon an update.

If the secret group value x of the root is used to generate a root key of a symmetric ratchet chain, in which keys are hashed for the nth time when encrypting the nth message, and all previous copies of x are thrown out, then we can also achieve forward security.

This paper omits technical details of actually implementing the structure and is not meant to provide a guide for implementing an exact protocol. Rather it should serve as an easy introductory understanding to the concepts used in creating such a protocol. It explains the importance and benefit of a TreeKEM structure for encrypted group messaging and showcases the motivations behind many of the structural decisions made with new protocols implementing such structures, most notably the new Messaging Layer Security (MLS) protocol proposed by IETF's MLS work group. MLS is working to replace the double ratchet Signal protocol in order to be a more efficient new standard and provides technical details for a draft protocol using TreeKEM that is at the time of this writing still being written and peer-reviewed.

10