Page:Efficient and Secure Group Messaging.pdf/8

For example, many Elliptic Curve cryptography schemes including Curve25519 and P-256, have a private key space of $\{0,1\}^{256}$, meaning that a standard hash function like SHA256 is enough to generate a private key. So an example of a deterministic KEM may be

$$KEM(x)=(SHA256(x),g^{SHA256(x)},Enc(SHA256(x),x))$$

The encapsulated value x need not be used directly as an encryption key for this to be considered a key encapsulation method. x can represent a random key that is then subsequently used to generate multiple random keys out of it using symmetric key-derivation methods. Indeed, in practice it is most secure to do so, providing x as input key material to produce multiple non-invertible image keys, such that x never needs to be unnecessarily used more than once to encrypt the same thing.

The main advantage of this deterministic property is that we may now build our tree based just on singular random elements in ${\mathcal {X}}$. Instead of storing Diffie-Hellman values in each node, consider storing random secret values from ${\mathcal {X}}$ in each node. Consider the following tree for our prior example:

In this tree example, $x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$ are generated and known by Alice, Bob, Carol, and Derek respectively.

In order to achieve a similar security tree invariant to the one we had in the DH tree, we need the root (and each subroot) value to be computable by its children. For this example, to ensure that the tree invariant holds, it should be possible to generate $x_{5}$, $x_{6}$, $x_{7}$ out of the $x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$ values, such that all group members know the group secret $x_{7}$.

We can achieve this by defining the following parent child relationship. Let H be a pseudo-random hash or key derivation function. Then, for a non-leaf node $v\in V$ in this tree with vertices and edges $(V,E)$, we define the relationship:

$$val(v\in V)=H(left(v)){\text{ or }}H(right(v))$$

Where left(v) is the left child of v such that $(v,left(v))\in E$ and right(v) is the equivalent right child of v. In the initializing case of leaf nodes $v\in V$, val(v) is randomly generated by the group member associated with that leaf node.

Whether the left or right vertex child will be used depends on the order of operations done in the group. An update operation involves a member changing their base key $x_{i}$ and propagating the change up the direct path of the root, hashing on each level. Suppose for example that Alice wants to update her secret contribution of this tree to $x'_{1}$. Then the updated tree would look as follows:

8