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.