Page:Efficient and Secure Group Messaging.pdf/5

5Using Trees for Key Handshakes

Ratchet Trees are structures using public-key cryptography in order to improve the time complexity efficiency of securing a symmetric key for a group of ends that wants to communicate via an encrypted messaging channel. The ratcheting component in this tree allows new keys to be agreed upon in a group handshake that may occur efficiently on a recurring basis in order to provide break-in recovery (also known as post-compromise security).

Trees are acyclic undirected graphs with one root node that has no parents, numerous intermediate nodes that each have children, and leaves that have no children. In this section we will be discussing left-balanced binary trees, meaning that no more than two children exist per node, and the tree's levels are balanced (no especially deep paths) while maintaining remainder leaves of the tree as left as possible. For the sake of brevity, I will not go into detail on the structure and proofs of tree structure but focus instead on their use in this field of cryptography. I shall assume the reader is familiar with basic tree concepts.

There are numerous methods using trees to perform the operation of a group handshake. The simplest is the use of a Diffie-Hellman tree. Effectively, the standard Diffie-Hellman exchange algorithm is already itself using a tree, albeit one with only three vertices.

In this figure, we consider each node to store certain values. Namely, for some group G in which discrete log is difficult, in a field generated by the generator g, Alice picks the private key $\alpha \in G$ and publishes the public key $g^{\alpha }$, and Bob picks the private key $\beta \in G$ and publishes the public key $g^{\beta }$. The root's value is the computation available only to Alice and Bob of the shared key $g^{\alpha \beta }$ We can then expand the tree to involve multiple people as follows:

Like before, Alice and Bob both share the symmetric key $g^{\alpha \beta }$, meanwhile, Carol and Derek's private keys $\gamma$ and $\delta$ can be used to generate public keys $g^{\gamma }$ and $g^{\delta }$ and the shared key $g^{\gamma \delta }$ Finally, since both of these

5