Page:Efficient and Secure Group Messaging.pdf/7

We will consider shortly how such a tree structure can be instantiated in the first place. However, as an example, in the above tree each node would have its own public/private key pair encapsulating a secret symmetric key, where all children and children's children of each node know the private key.

For instance, node A would have its own public/private key pair, where the private key pair is known only to nodes Alice and Bob, while node B would have its own public/private key pair where the private key is known only to Carol and to Derek.

Likewise, the root of the tree would have a public/private key pair known to all nodes of the tree. This key pair would be encapsulating a secret value used for the entire group to communicate.

It should be noted that this description above was vastly simplified in order to provide an introductory understanding to the subject. Not any Key Encapsulation Method can be used. While the traditional approach for Key encapsulation is to pick a public/private key pair first and then use that to encrypt a random value or key, it is important for the purposes of this structure (for reasons that will be soon clear) that anybody who has access to the encapsulated key should also be able to decrypt information encrypted for the public key. The simplest way to achieve this property is for the private key to be deterministically generated from the secret value itself.

Definition 4 Deterministic Key Encapsulation

Let G be a group with generator g used for public-key cryptography. Let $KEM(x)$ be a key encapsulation method which takes a value $x\in {\mathcal {X}}$ in some space ${\mathcal {X}}$ and outputs a private-public key pair of elements in the group G. Then,

$$KEM(x)=(\alpha ,\beta ,c)$$

Where $\alpha \in G$ is a private key, $\beta \in G$ is a public key, and $c\in {\mathcal {Y}}$ is optional ciphertext in the ciphertext space ${\mathcal {Y}}$ containing securely encrypted information about x. Any output of the KEM for a value x in a deterministic KEM would have the same deterministic output value for the private key $\alpha$ every time, such that any holder of x may compute $\alpha$, and thereby be able to decrypt any information encrypted for $\beta$. The ciphertext c need not be used or deterministic, however it makes sense for its value to be an encrypted version of x, say $Enc(\beta ,x)$, which would not be deterministic under most secure schemes due to uses of random nonce and salt values.

Key encapsulation methods can achieve this deterministic property by creating a one-way pseudorandom map from the space ${\mathcal {X}}$ to private-key elements in the group G.

$$H:{\mathcal {X}}\to G$$

7