In the last segment, we saw two active attacks that can completely destroy the

security of CPA secure encryption. In this segment, we're gonna define a new concept,

called authenticated encryption, that remains secure in the presence of an

active adversary. In later segments, we'll construct encryption schemes that satisfy

this new authenticated encryption concept. So what is authenticated encryption?

Authenticated encryption is a cipher where as usual the encryption algorithm takes a

key, a message and optionally a nonce and outputs a cipher text. The decryption algorithm as

usual outputs a message. However, here the decryption algorithm is allowed to output

a special symbol called bottom. When the decryption algorithm outputs the symbol

bottom, basically it says that the cipher text is invalid and should be ignored. The

only requirement is that this bottom is not in the message space so that in fact

it is a unique symbol that indicates that the cipher text should be rejected. Now

what does it mean for an authenticated encryption system to be secure? Well the

system has to satisfy two properties. The first property is that it has to be

semantically secure under a chosen plaintext attack just as before. But now

there's a second property which says that the system also has to satisfy what's

called cipher text integrity. What that means is that even though the attacker

gets to see a number of cipher texts, it should not be able to produce another

cipher text that decrypts properly. In other words, that decrypts to something

other than bottom. More precisely, let's look at the ciphertext integrity game.

So here, (E,D) is a cipher with message space M. As usual, the challenger begins

by choosing a random key K. And the adversary can submit messages of his

choice, and receive the encryptions of those messages. So here, C1 is the

encryption of M1, where M1 was chosen by the adversary. And the adversary can do

this repeatedly. In other words, he submits M2 and obtains the encryption of

M2, and so on and so forth. He submits many more messages up until Mq and obtains

the encryption of all those messages. So here the adversary obtained Q cipher texts

for messages of his choice. Then his goal is to produce some new cipher text that's

valid. So we'll say that the adversary wins the game if basically this new cipher

text that the adversary created decrypts correctly, in other words decrypts to

something other than bottom. And it's a new cipher text. In other words, it's not

one of the cipher texts that was given to the adversary as part of this chosen

plaintext attack. And then as usual we defined the adversary's advantage in the

cipher text integrity game as the probability that the challenger outputs

one at the end of the game and we'll say that the cipher has cipher text integrity

if in fact for all efficient adversaries the advantage in winning this game is

negligible. So now that we understand what cipher text integrity is we can

define authenticated encryption and basically we say that the cipher has

authenticated encryption if as we said it's semantically secure under a chosen

plaintext attack and it also has cipher text integrity. So just as a bad example,

let me mention that CBC with a random IV does not provide authenticated encryption

because it's very easy for the adversary to win the cipher text integrity game.

The adversary simply submits a random cipher text

and since the decryption algorithm for CBC encryption never outputs bottom,

it always outputs some message, the adversary just easily wins the game.

Any old random cipher text will decrypt to something other than bottom

and therefore the adversary directly wins the cipher-text integrity game. So this is just

a trivial example of a CPA secure cipher that does not provide authenticated encryption.

So I wanna mention two implications of authenticated encryption. The first I'll

call authenticity, which means that, basically, an attacker cannot fool the

recipient, Bob, into thinking that Alice sent a certain message that she didn't

actually send. So let's see what I mean by that. Well, here, the attacker basically

gets to interact with Alice, and get her to encrypt arbitrary messages of his

choice. So this is a chosen plain text attack. And then the attacker's goal is to

produce some cipher text that was not actually created by Alice. And because the

attacker can't win the cipher text integrity game, he can't do this. What

this means is, when Bob receives the cipher text that decrypts correctly under

the decryption algorithm, he knows that the message must have come from someone

who knows the secret key K. In particular, if Alice is the only one who knows K, then

he knows the cipher text really did come from Alice, and it's not some modification

that was sent by the attacker. Now the only caveat to that is that authenticated

encryption doesn't defend against replay attacks. In particular, the attacker

could've intercepted some cipher text from Alice to Bob. And could have replayed it

and both cipher text would look valid to Bob. So for example, Alice might send a

message to Bob saying transfer $100 to Charlie. Then Charlie could replay that

cipher text and as a result, Bob would transfer another $100 to Charlie. So in

fact, any encryption protocol has to defend against replay attacks and this is

not something that's directly prevented by authenticated encryption. And we'll come

back and talk about replay attacks in two segments. The second implication of

authenticated encryption is that it defends against a very powerful type of

adversary, namely an adversary that can mount what's called a chosen cipher text

attack. We're going to talk about that actually in the next segment.