So, what did we do last week? We looked at Ratchet and Key Exchange. We were working

on the definition for Ratchet and Key Exchange for two weeks already and our aim was to understand

how the definition really works. And we focused on unidirectional Ratchet and Key Exchange,

which is the notion in which the sender will always send and the receiver will always receive

and the primary thing that we did last week was identifying the trivial winning conditions,

the trivial attack and the concept of how to prevent these attacks. The second step

that we did last week is to come up or was to come up with a construction. And the third

step was to at least intuitively think about how we could prove security for this. And

so we had somewhat a high level security argument. What we are going to do today is that we will

extend this security argument and come up with a formal proof. And then, and this was

part of the exercise for this week already that we discussed in the exercise session

just before, is that randomness or weak randomness is indeed a realistic threat. And we will look

at how to prevent or how to strengthen constructions against that threat. So weak

randomness is the threat and we will then look at how we can build a building block,

a primitive that we call key-updatable key encapsulation mechanisms. And with this building

block key-updatable key encapsulation mechanism, we will be able to protect a ratchety key exchange

construction against weak randomness. Okay, without losing any further time, we will quickly look

again at what type of construction of ratchety key exchange we are looking at right now and what

our arguments were that this construction is indeed secure. So our construction consists of

three algorithms and these three algorithms are an initialization, a send algorithm and a receive

algorithm. And the two main building blocks that we use that we can instantiate are a key

encapsulation mechanism and during initialization we generate an initial key encapsulation mechanism

key pair, public key and secret key, encapsulation key and decapsulation key. And we also generate a

signing key pair, signing key and verification key. And so the basic idea is that we give the

encapsulation key to the sender, the decapsulation key to the receiver, the signing key to the sender

and the verification key to the receiver. Because basically what the sender will always do is try

to encapsulate a symmetric key to the receiver and so the sender needs the encapsulation key,

receiver needs the decapsulation key. And in order to protect against active adversaries,

the sender will use the signing mechanism to sign the ciphertext and so the sender needs the signing

key and the receiver will need the verification key. The basic process for sending something is

that the sender will first encapsulate something to the receiver, just as I said, then protect the

ciphertext with a signature. And the interesting part here is that we want to update the key pair

for two reasons. First of all, we have the security guarantee forward secrecy that we want to achieve.

And then secondly, we have that guarantee that once something malicious happens on the wire between

sender and receiver, we want that the sender and receiver are out of sync, that they diverge,

that their key material becomes independent. And so for that reason we have basically an update

mechanism that takes the current public key, takes some secret information and comes up with a new public key.

And this update mechanism is based on the random oracle model, or on the random oracle. In the

random oracle model we basically idealize hash functions. So we talked about the random oracle

model last week. The basic idea is that we idealize a hash function and the guarantees that we hope to

obtain from a hash function is that every output of the hash function looks random and we obtain no

information about the output of a hash function until we invoke the hash function, until we take

the hash function, put the inputs into the hash function and see what the output is.

As long as we did not do that, we have no information about how the output of the hash function looks like.

And that in particular means that the description of a hash function will not help us to gain any information about

the hash function unless we use that description to invoke the hash function.

So on the receiver side of course what the receiver first does is verifying the signature, then

encapsulating the ciphertext, obtaining the key and then also updating the decapsulation key,

the secret key with the hash function. This is on a very very high level.

The actual construction looks a little bit more difficult so we will look at