Page:Efficient and Secure Group Messaging.pdf/3

values and chain of keys have the ability to generate the new symmetric key and decrypt messages.

Due to the use of two separate ratchet steps performed at every message, this protocol is known as The Double Ratchet Algorithm. To read the full protocol go to The Double Ratchet Algorithm, available at https://signal.org/docs/specifications/doubleratchet/. This method of message encryption is currently one of the most popular methods for message encryption in the world, with more than 2 billion users' messages being encrypted using this scheme on WhatsApp's messaging platform, which uses the Signal protocol.

3Security Features

Below I will define more formally our desired features of forward secrecy and break-in recovery. In general, the best practice for defining security in cryptography is by describing an attack game where a challenger encrypts data and provides it to an adversary ${\mathcal {A}}$ who wishes to gleam information from the encrypted data. If the adversary ${\mathcal {A}}$ cannot statistically distinguish encrypted data (and therefore perceives it to be entirely random) then the information is considered to be semantically secure. I will forego providing the definition for standard semantic security described but will provide to the reader here my own definition for forward secrecy and for break-in recovery using the model of an attack game and using the same definition for semantic security within those definitions.

For both games, we will let ${\mathcal {E}}=(E,D)$ define an encryption scheme providing such features, where E is the encryption algorithm and D is the decryption algorithm.

$$E:{\mathcal {M}}\times {\mathcal {K}}\times {\mathcal {X}}\to {\mathcal {C}}\times {\mathcal {X}}$$

E is an encryption function mapping from the message space ${\mathcal {M}}$, the key space ${\mathcal {X}}$, and the state space ${\mathcal {X}}$. The state space is an addition on a standard encryption scheme and will allow these features to exist. As described in regards to Signal's Double Ratchet step, this state can include information about the chain of derived keys or the new Diffie-Hellman key information. In the case of a tree structure, the state might represent the current values and nodes of the tree structure. The state could at its simplest be a simple counter of natural numbers $\mathbb {N}$ counting the number of total messages sent between Alice and Bob. In fact, such a counter is usually desired even as part of simple ElGammal encryption in order to prevent replay attacks where an adversary can send the same cipher text again and convince Alice or Bob that the message was sent from the other due to the valid signature; a signed counter would confirm for Alice or Bob that this is in fact an old message.

Certain parts of the state may be sent publicly, such as public keys, while other parts of the state are kept in sync privately by each party, such as the secret values in a tree structure. The algorithm D decrypts from the $({\mathcal {C}},{\mathcal {K}},{\mathcal {X}})$ space.

$$D:{\mathcal {C}}\times {\mathcal {K}}\times {\mathcal {X}}\to {\mathcal {M}}\times {\mathcal {X}}$$

With this encryption scheme, we can now formally define forward secrecy and break-in recovery.

Definition 1 Forward secrecy:

For a given encryption scheme $L=(E,D)$, defined over $({\mathcal {M}},{\mathcal {K}},{\mathcal {C}},{\mathcal {X}})$, and a given adversary ${\mathcal {A}}$, we define an attack game that runs as follows to define a scheme that is forward secure.

• The challenger picks a random message $m_{1}\in {\mathcal {M}}$, and an initial key $k\in {\mathcal {K}}$. The challenger initializes the state $x_{1}\in {\mathcal {X}}$ and then computes the cipher $c_{1}\in {\mathcal {C}}$ and sends $c_{1}$ to the adversary ${\mathcal {A}}$ As part of the encryption output the challenger is also left with a new state $x_{2}\in {\mathcal {X}}$. The challenger may perform this step as many time as the adversary would like with different messages before proceeding to the second step, since this is how the situation would be in real life.
• Next, the challenger picks a new random message $m_{2}$, and encrypts it using $c_{2}=E(m,k,x_{2})$ using the new state generated from step 1. The challenger sends the cipher $c_{2}$ to the adversary.

3