Last week, we learned a number theory that's needed for public key encryption. This week we're gonna put this knowledge to work, and we're gonna construct a number of secure public key encryption schemes. But first, we need to define what is public key encryption, and what does it mean for public key encryption to be secure? So let me remind you that in a public key encryption scheme, there is an encryption algorithm which is usually denoted by E, and there's a decryption algorithm which we denote by D. However here, the encryption algorithm takes a public key, while the decryption algorithm takes a secret key. This pair is called a key pair. And the public key is used for encrypting messages while the secret key is used for decrypting messages. So in this case a message m is encrypting using the public key and what comes out of that is the ciphertext c. And similarly the ciphertext is fed into the decryption algorithm and using the secret key, what comes out of the decryption algorithm is the original message m. Now public key encryption has many applications. Last week we saw the classic application which is session setup, namely, key exchange and for now we're just looking at key exchange that is secure against eavesdropping only. And if you remember the way the protocol works, basically Alice, what she would do is she would generate a public key secret pair. She would send the public key to Bob. Bob will generate a random X, which is gonna serve as their shared secret, and then he sends X encrypted to Alice, encrypted under her public key. Alice can decrypt, recover X and now both of them have this shared secret X which they can use to communicate securely with one another. The attacker, of course, all he gets to see is just the public key, the encryption of X under the public key, from which he should not be able to get any information about X. And we are going to define that more precisely to understand what it means to not be able to learn anything about X. Public key encryption actually has many other applications. For example, it's very useful in non-interactive applications. So think of an email system for example. So here, Bob wants to send mail to Alice, and as Bob sends the email, the email passes from mail relay to mail relay until finally it reaches Alice, at which point Alice should decrypt. The way the email system is set up, is designed for kind of non-interactive settings where Bob sends the email. And then Alice is supposed to receive it. And Alice should not be to communicate with Bob in order to decrypt the email. So in this case, because of the non-interactivity, there's no opportunity for setting up a shared secret between Alice and Bob. So in this case, what would happen is, Bob basically would, would send the email encrypted, using Alice's, public key. So he sends the email. Anyone in the world can send the email encrypted to Alice, encrypted using her public key. When Alice receives this email, she uses her secret key to decrypt the ciphertext and recover the plain text message. Of course the one caveat in a system like this is that in fact Bob needs to somehow obtain Alice's public key So for now we are just going to assume Bob already has Alice's public key, but later on, actually, when we talk about digital signatures we're gonna see how, this can actually be done very efficiently using what's called public key management and as I said we'll actually get back to that at a later time. But the main thing I want you to remember, is that public key encryption is used for session setup. This is very common on the web, where public key encryption is used to set up a secure key between a web browser and, and web server. And public key encryption is also very useful for non-interactive applications, where anyone in the world, non-interactively, needs to send a message to Alice, they can encrypt the message using Alice's public key, and Alice can decrypt and recover the plain text. So let me remind you in a bit more detail what a public key encryption system is. Well, it's made up of three algorithms G, E, and D. G is called the key generation algorithm. Basically what it will do is it will generate this key pair, the public key and the secret key. As written here, G takes no arguments, but in real life, G actually does take an argument called the security parameter which specifies the size of the keys that are generated by this key generation algorithm. Then there are these encryption algorithms as usual that take a public key and a message and produce a ciphertext in a decryption algorithm that takes the corresponding secret key and a ciphertext and it produces a corresponding message. And as usual for consistency we say that if we encrypt a message under a given public key and then decrypt with a corresponding secret key we should get the original message back. Now what does it mean for a public key encryption to be secure? I'm going to start off by defining, security against eavesdropping. And then we're going to define security against active attacks. So the way to define security against eavesdropping is very similar to the symmetric case we've already this last week so we're gonna go through this quickly just as a review. Basically the attack game is defined as follows. We defined these two experiments, experiment zero and experiment one. At in either experiment the challenger is gonna generate a public and a secret key pair. He's gonna give the public key to the adversary. The adversary's gonna output two messages m0 and m1 of equal length and then what he gets back is either the encryption of m0 or the encryption of m1. In experiment zero he gets the encryption of m0. In experiment one he gets the encryption of m1. And then the adversary is supposed to say which one did he get. Did he get the encryption of m0 or did he get the encryption of m1? So in this game, the attacker only gets one ciphertext. This corresponds to an eavesdropping attack where he simply eavesdropped on that ciphertext C. And now his goal is to tell whether the ciphertext C i s the encryption of M0 or M1. No tampering on the ciphertext C is allowed just yet. And as usual we say that the public key encryption scheme is semantically secure if the attacker cannot distinguish experiment zero from experiment one. In other words he cannot tell whether he got the encryption of M0, or the encryption of M1. Before we move on to active attacks, I want to mention a quick relation between the definition we just saw, And the definition of, of eavesdropping security for symmetric ciphers. If you remember, when we talked about eavesdropping security for symmetric ciphers, we distinguished between the case where the key is used once, and the case where the key is used multiple times. And, in fact we saw that, there's a clear separation. For example, the onetime pad. Is secure if the key is used to encrypt a single message, but is completely insecure if the key is used to encrypt multiple messages. And in fact we had two different definitions if you remember we had a definition for one-time security, and then we had a separate definition, which was stronger, when the key was used multiple times. The definition that I showed you on the previous slide's very similar to the definition of one time security for symmetric ciphers. And in fact, it turns out that for public key encryption, if a system is secure under a onetime key, in a sense, it's also secure for a many time key. So in other words, we don't have to explicitly give the attacker the ability to, request encryptions of messages of his choice. Because he could just create those encryptions all by himself. He is given the public key, and therefore he can by himself encrypt any message he likes. As a result any public key secret pair in some sense inherently is used to encrypt multiple messages because the attacker could have just encrypted many, many messages of his choice using the given public key that we just gave him in the first step. And so, as a result in fact, the definition of one time security is enough to imply many time security and that's why we refer to the concept as indistinguishability under a chosen plain text attach. So this is just a minor point to explain why the settings of public encryption, we don't need a more complicated definition to capture eavesdropping security. Now that we understand eavesdropping security, let's look at more powerful adversaries that can actually mount active attacks. So, in particular, let's look at the email example. So here, we have our friend Bob who wants to send mail to his friend Caroline. And Caroline happens to have, an account at Gmail. And the way this works is basically, the email is sent to the Gmail server, encrypted. The Gmail server decrypts the email, looks at the, intended recipients. And then, if it's, the intended recipient is Caroline, it forwards the email to Caroline. If the intended recipient is the attacker, it forwards the email to the attacker. This is similar to how Gmail actually works because the sender would send the email encrypted over SSL to the Gmail server. The Gmail server would terminate the SSL and then forward the email to the appropriate recipients. Now suppose Bob encrypts the email using a system that allows the adversary to tamper with the ciphertext without being detected. For example, imagine this email is encrypted using Counter Mode, or something like that. Then when the attacker intercepts this email, he can change the recipient, so that now the recipient says attacker@gmail.com, and we know that for Counter Mode, for example, this is quite easy to do. The attacker knows that the email is intended for Caroline, he is just interested in the email body. So he can easily change the email recipient to attacker@gmail.com and now when the server receives the email, he will decrypt it, see that the recipient is supposed to be attacker, and forward the body to the attacker. And now the attacker was able to read the body of the email that was intended for Caroline. So this is a classic example of an active attack, and you notice what the attacker could do here, is it could decrypt any ciphertext where the intended recipient is to: attacker. So any ciphertext where the plain text begins with the words "to: attacker". So our goal is to design public key systems that are secure, even if the attacker can tamper with ciphertext and possibly decrypt certain cyphertexts. And again, I want to emphasize that here the attacker's goal was to get the message body. The attacker already knew that the email is intended for Caroline. And all he had to do was just change the, intended recipient. So this tampering attack motivates the definition of chosen ciphertext security. And in fact this is the standard notion of security for public key encryption. So let me explain how the attack [here procedes] and as I said our goal is to build systems that are secure under this very, very conservative notion of encryption. So we have an encryption scheme (G, E, D). And let's say that's defined over a message space and a ciphertext (M, C) and as usual we're gonna define two experiments, experiment zero, and experiment one. So 'b' here says whether the challenger is implementing experiment zero or experiment one. The challenger begins by generating a public key and a secret key, and then gives the public key to the adversary. Now the adversary can say, "Well, here are a bunch of ciphertexts, please decrypt them for me." So here the adversary submits ciphertext C1 and he gets the decryption of ciphertext C1, namely M1. And he gets to do this again and again, so he submits ciphertext C2, and he gets the decryption, which is M2, ciphertext C3, and he gets the decryption M3, and so on and so forth. Finally, the adversary says, "This squaring phase is over," and now he submits basically two equal length messages, M0 and M1 as normal, and he receives in response the challenge ciphertext C, Which is the encryption of M zero or the encryption of M one. Depending on whether we're in experiment zero or experiment one. Now, the adversary can continue to issue these ciphertext queries. So he can continue to issue, decryption requests. So he submits a ciphertext, and he gets a decryption of that ciphertext, but of course, now, there has to be a caveat. If the attacker could submit arbitrary ciphertext of his choice, of course, he could break the challenge. What he would do is he would submit the challenge ciphertext C as a decryption query. And then he would be told whether in the challenge phase he was given the encryption of M0 or the encryption of M1. As a result we put this limitation here, that says that he can in fact submit any ciphertext of his choice except. For the challenge ciphertext. So the attacker could ask for the decryption of any ciphertext of his choice other than the challenge ciphertext. And even though he was given all these decryptions, he still shouldn't be able to tell whether he was given the encryption of M0 or the encryption of M1. So you notice this is a very conservative definition. It gives the attacker more power than what we saw in the previous slide. On the previous slide, the attacker could only decrypt messages where the plain text began with the words "to: attacker". Here, we're saying the attacker can decrypt any ciphertext of his choice, as long as it's different from the challenge ciphertext C. Okay? And then his goal is to say whether the challenge ciphertext is the encryption of M0 or the encryption of M1. And as usual, if he can't do that, in other words, his behavior in experiment zero is basically the same as his behavior in experiment one, so he wasn't able to distinguish the encryption of M0 from the encryption of M1, even though he had all this power Then we say that the system is chosen ciphertext secure, CCA secure. And sometimes there is an acronym, the acronym for this is indistinguishability under a chosen ciphertext attack, but I'm just gonna say CCA secured. So let's see how this captures, the email example we saw before. So suppose the encryption system being used is such that just given the encryption of a message the attacker can change the intended recipient from to Alice say to, to Charlie. Then here's how we would win the CCA game. Well in the first step he's given the public key of course. And then what the attacker will do is he would issue two equal length messages, namely in the first message, the body is zero. In the second message the body is one. But both messages are intended for Alice. And in response, he would be given the challenge ciphertext C. Okay, so now here we have our challenge ciphertext C. Now what the attacker is gonna do is he's gonna use his, his ability here to modify the intended recipient. And he's gonna send back a ciphertext C', where C' is the encryption of the message to Charlie with body being the challenge body b. So if you remember is either zero or one. Now, because the plain text is different, we know that the ciphertext must also be different. So in particular, C prime must be different from the challenge ciphertext C, yeah? So the C prime here must be different from C. And as a result, the poor challenger now has to decrypt by definition of the CCA game. The challenger must decrypt any ciphertext that's not equal to a challenge ciphertext. So the challenger decrypts give the adversary M prime. Basically he gave the adversary B, and now the adversary can output the challenge B and he wins the game with advantage one. So he's advantage with this particular scheme is one. So, simply because the attacker was able to change the challenge ciphertext from one recipient to another that allows him to, to win the CCA game with advantage one. So as I said, chosen ciphertext security turns out actually is the correct notion of security for public key encryption systems. And it's a very, very interesting concept, right? Basically, somehow even though the attacker has this ability to decrypt anything he wants. Other than the challenge ciphertext, still he can't learn what the challenge ciphertext is. And so the goal for the remainder of this module and actually the next module as well, is to construct CCA secure systems. It's actually quite remarkable that this is achievable and I'm going to show you exactly how to do it. And in fact those CCA secure systems that we build are the ones that are used in the real world. And every time a system has tried to deploy a public key encryption mechanism that's not CCA secure someone has come up with an attack and was able to break it. And we're going to see some of these example attacks actually in the next few segments.
