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.
