- We will assume that a symmetric encryption algorithm is being used as part of the forward secure
scheme. Suppose that the challenger was using
*AES-GCM*256 (without loss of generality this can be any semantically secure symmetric algorithm) as his symmetric encryption scheme, such that for some , the challenger shall now provide this key to the adversary.

At the end of this game, the adversary should easily be able to compute by possession of the AES 256-bit key , however, if the scheme is forward secure then the adversary will not be able to distinguish from any random piece of data, and if now given a random message alongside the real message , the adversary should be statistically unable to distinguish which message was encrypted to generate the ciphertext . The probability that the adversary guesses correctly minus the probability the adversary guesses wrong, which is the adversary advantage, should be (negligibly) zero. Let be the event that the adversary guesses correctly and be the event that the adversary guesses wrongly.

**Definition 2** *Break-in recovery:*

Break-in recovery is defined by a near equivalent game. The challenger picks a random message , and an initial key . The challenger initializes the state and then computes the cipher and sends to the adversary . As part of the encryption output the challenger is also left with a new state .

Next, the challenger picks a new random message , and encrypts it using using the new state generated from step 1. The challenger sends the cipher to the adversary.

This time, the challenger reveals to the adversary the initial key and the initial state . However, without , which includes information on a ratchet step performed from the initial step, the adversary cannot decrypt , and given a random message alongside should not be able to guess which one was used to generate .

**4A Simple Symmetric Ratchet**

Suppose that we are using symmetric encryption (so a shared key has already been securely established by the parties), then we make it into a symmetric ratchet by changing the key in a one-way fashion each time we take a ratchet step (perhaps every message or every hour). Below I provide a simple way of achieving this using just symmetric keys and no public-key cryptography, simply by using a random collision-resistant hash function.

Let *key[0]* be in the initial agreed symmetric key. Then we recursively define

For the *ith* message key used for authenticated encryption (say with AES-GCM). Each encryption operation
would also include a random nonce for added security.

Does this achieve forward secrecy? Only if the parties can securely delete *consumed* keys - keys which
have already been used for their decryption/encryption operations.

In the forward secrecy Attack Game the key *k'* given to adversary is equivalently the second key generated
in the chain: , if the adversary does not have access to *key[0]* then he cannot distinguish
between the messages without breaking semantic security: In other words, if the adversary had some way
of distinguishing between two messages encrypted with *key[0]* without *key[0]* then that would break the
semantic security of AES, and therefore by proof of contradiction this approach is forward secure. We
assume that *key[1]* does not provide any information about *key[0]*, viewing the hash function under the
assumption that it acts like a purely random oracle (even though in reality it is in practice going to be
collision resistant and certainly not perfect given that the pre-image space is larger than the range).

4