0:00

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.

Â