0:00:00.000,0:00:03.583
Last week, we learned a number theory[br]that's needed for public key encryption.

0:00:03.583,0:00:07.166
This week we're gonna put this knowledge[br]to work, and we're gonna construct a

0:00:07.166,0:00:10.889
number of secure public key encryption[br]schemes. But first, we need to define what

0:00:10.889,0:00:14.565
is public key encryption, and what does it[br]mean for public key encryption to be

0:00:14.565,0:00:18.241
secure? So let me remind you that in a[br]public key encryption scheme, there is an

0:00:18.241,0:00:21.778
encryption algorithm which is usually[br]denoted by E, and there's a decryption

0:00:21.778,0:00:25.361
algorithm which we denote by D. However[br]here, the encryption algorithm takes a

0:00:25.361,0:00:29.477
public key, while the decryption algorithm[br]takes a secret key. This pair is called a

0:00:29.477,0:00:34.356
key pair. And the public key is used for[br]encrypting messages while the secret key

0:00:34.356,0:00:39.002
is used for decrypting messages. So in[br]this case a message m is encrypting using

0:00:39.002,0:00:43.880
the public key and what comes out of that[br]is the ciphertext c. And similarly the

0:00:43.880,0:00:48.643
ciphertext is fed into the decryption[br]algorithm and using the secret key, what

0:00:48.643,0:00:53.577
comes out of the decryption algorithm is[br]the original message m. Now public key

0:00:53.577,0:00:57.989
encryption has many applications. Last[br]week we saw the classic application which

0:00:57.989,0:01:02.455
is session setup, namely, key exchange and[br]for now we're just looking at key exchange

0:01:02.455,0:01:06.867
that is secure against eavesdropping only.[br]And if you remember the way the protocol

0:01:06.867,0:01:11.227
works, basically Alice, what she would do[br]is she would generate a public key secret

0:01:11.227,0:01:15.546
pair. She would send the public key to[br]Bob. Bob will generate a random X, which

0:01:15.546,0:01:20.136
is gonna serve as their shared secret, and[br]then he sends X encrypted to Alice,

0:01:20.136,0:01:24.904
encrypted under her public key. Alice can[br]decrypt, recover X and now both of them

0:01:24.904,0:01:29.554
have this shared secret X which they can[br]use to communicate securely with one

0:01:29.554,0:01:34.143
another. The attacker, of course, all he[br]gets to see is just the public key, the

0:01:34.143,0:01:38.972
encryption of X under the public key, from[br]which he should not be able to get any

0:01:38.972,0:01:43.800
information about X. And we are going to[br]define that more precisely to understand

0:01:43.800,0:01:48.507
what it means to not be able to learn[br]anything about X. Public key encryption

0:01:48.507,0:01:52.522
actually has many other applications. For[br]example, it's very useful in

0:01:52.522,0:01:57.235
non-interactive applications. So think of[br]an email system for example. So here, Bob

0:01:57.235,0:02:01.716
wants to send mail to Alice, and as Bob[br]sends the email, the email passes from

0:02:01.716,0:02:06.603
mail relay to mail relay until finally it[br]reaches Alice, at which point Alice should

0:02:06.603,0:02:10.502
decrypt. The way the email system is set[br]up, is designed for kind of

0:02:10.502,0:02:15.045
non-interactive settings where Bob sends[br]the email. And then Alice is supposed to

0:02:15.045,0:02:19.195
receive it. And Alice should not be to[br]communicate with Bob in order to decrypt

0:02:19.195,0:02:23.502
the email. So in this case, because of the[br]non-interactivity, there's no opportunity

0:02:23.502,0:02:27.705
for setting up a shared secret between[br]Alice and Bob. So in this case, what would

0:02:27.705,0:02:32.169
happen is, Bob basically would, would send[br]the email encrypted, using Alice's, public

0:02:32.169,0:02:36.571
key. So he sends the email. Anyone in the[br]world can send the email encrypted to

0:02:36.571,0:02:41.103
Alice, encrypted using her public key.[br]When Alice receives this email, she uses

0:02:41.103,0:02:45.748
her secret key to decrypt the ciphertext and recover the plain text message.

0:02:45.748,0:02:50.507
Of course the one caveat in a system like[br]this is that in fact Bob needs to somehow

0:02:50.507,0:02:54.804
obtain Alice's public key So for now we[br]are just going to assume Bob already has

0:02:54.804,0:02:58.297
Alice's public key, but later on,[br]actually, when we talk about digital

0:02:58.297,0:03:02.457
signatures we're gonna see how, this can[br]actually be done very efficiently using what's

0:03:02.457,0:03:06.823
called public key management and as I said[br]we'll actually get back to that at a later

0:03:06.823,0:03:10.931
time. But the main thing I want you to[br]remember, is that public key encryption is

0:03:10.931,0:03:14.578
used for session setup. This is very[br]common on the web, where public key

0:03:14.578,0:03:18.840
encryption is used to set up a secure key[br]between a web browser and, and web server.

0:03:18.840,0:03:22.898
And public key encryption is also very[br]useful for non-interactive applications,

0:03:22.898,0:03:26.390
where anyone in the world,[br]non-interactively, needs to send a message

0:03:26.390,0:03:30.653
to Alice, they can encrypt the message using[br]Alice's public key, and Alice can decrypt

0:03:30.653,0:03:36.105
and recover the plain text. So let me[br]remind you in a bit more detail what a

0:03:36.105,0:03:40.347
public key encryption system is. Well,[br]it's made up of three algorithms G, E, and

0:03:40.347,0:03:44.431
D. G is called the key generation algorithm.[br]Basically what it will do is it will

0:03:44.431,0:03:48.672
generate this key pair, the public key and[br]the secret key. As written here, G takes

0:03:48.672,0:03:53.018
no arguments, but in real life, G actually[br]does take an argument called the security

0:03:53.018,0:03:57.260
parameter which specifies the size of the[br]keys that are generated by this key

0:03:57.260,0:04:01.731
generation algorithm. Then there are these[br]encryption algorithms as usual that take a

0:04:01.731,0:04:06.051
public key and a message and produce a[br]ciphertext in a decryption algorithm that

0:04:06.051,0:04:10.530
takes the corresponding secret key and a[br]ciphertext and it produces a corresponding

0:04:10.530,0:04:14.955
message. And as usual for consistency we[br]say that if we encrypt a message under a

0:04:14.955,0:04:19.380
given public key and then decrypt with a[br]corresponding secret key we should get the

0:04:19.380,0:04:23.852
original message back. Now what does it[br]mean for a public key encryption to be

0:04:23.852,0:04:27.913
secure? I'm going to start off by[br]defining, security against eavesdropping.

0:04:27.913,0:04:32.002
And then we're going to define security[br]against active attacks. So the way to

0:04:32.002,0:04:36.237
define security against eavesdropping is[br]very similar to the symmetric case we've

0:04:36.237,0:04:40.626
already this last week so we're gonna go[br]through this quickly just as a review.

0:04:40.626,0:04:44.808
Basically the attack game is defined as[br]follows. We defined these two experiments,

0:04:44.808,0:04:49.249
experiment zero and experiment one. At in[br]either experiment the challenger is gonna

0:04:49.249,0:04:52.965
generate a public and a secret key pair. He's gonna give the public

0:04:52.965,0:04:57.342
key to the adversary. The adversary's[br]gonna output two messages m0 and m1 of

0:04:57.342,0:05:01.663
equal length and then what he gets back is[br]either the encryption of m0 or the

0:05:01.663,0:05:06.039
encryption of m1. In experiment zero he[br]gets the encryption of m0. In experiment

0:05:06.039,0:05:10.748
one he gets the encryption of m1. And then[br]the adversary is supposed to say which one

0:05:10.748,0:05:15.240
did he get. Did he get the encryption of[br]m0 or did he get the encryption of m1? So

0:05:15.240,0:05:19.676
in this game, the attacker only gets one[br]ciphertext. This corresponds to an

0:05:19.676,0:05:24.226
eavesdropping attack where he simply[br]eavesdropped on that ciphertext C. And now

0:05:24.226,0:05:28.719
his goal is to tell whether the ciphertext[br]C i s the encryption of M0 or M1. No

0:05:28.719,0:05:34.221
tampering on the ciphertext C is allowed[br]just yet. And as usual we say that the

0:05:34.221,0:05:38.206
public key encryption scheme is[br]semantically secure if the attacker cannot

0:05:38.206,0:05:42.085
distinguish experiment zero from[br]experiment one. In other words he cannot

0:05:42.085,0:05:47.757
tell whether he got the encryption of M0,[br]or the encryption of M1. Before we move on

0:05:47.757,0:05:52.311
to active attacks, I want to mention a[br]quick relation between the definition we

0:05:52.311,0:05:56.105
just saw, And the definition of, of[br]eavesdropping security for symmetric

0:05:56.105,0:06:00.438
ciphers. If you remember, when we talked[br]about eavesdropping security for symmetric

0:06:00.438,0:06:04.771
ciphers, we distinguished between the case[br]where the key is used once, and the case

0:06:04.771,0:06:08.998
where the key is used multiple times. And,[br]in fact we saw that, there's a clear

0:06:08.998,0:06:13.357
separation. For example, the onetime pad.[br]Is secure if the key is used to encrypt a

0:06:13.357,0:06:17.382
single message, but is completely insecure[br]if the key is used to encrypt multiple

0:06:17.382,0:06:21.358
messages. And in fact we had two different[br]definitions if you remember we had a

0:06:21.358,0:06:25.383
definition for one-time security, and then[br]we had a separate definition, which was

0:06:25.383,0:06:29.700
stronger, when the key was used multiple[br]times. The definition that I showed you on

0:06:29.700,0:06:34.043
the previous slide's very similar to the[br]definition of one time security for

0:06:34.043,0:06:38.499
symmetric ciphers. And in fact, it turns[br]out that for public key encryption, if a

0:06:38.499,0:06:43.124
system is secure under a onetime key, in a[br]sense, it's also secure for a many time

0:06:43.124,0:06:47.929
key. So in other words, we don't have to[br]explicitly give the attacker the ability

0:06:47.929,0:06:53.171
to, request encryptions of messages of his[br]choice. Because he could just create those

0:06:53.171,0:06:57.870
encryptions all by himself. He is given[br]the public key, and therefore he can by

0:06:57.870,0:07:04.672
himself encrypt any message he likes. As a[br]result any public key secret pair in some

0:07:04.672,0:07:09.289
sense inherently is used to encrypt[br]multiple messages because the attacker

0:07:09.289,0:07:13.905
could have just encrypted many, many[br]messages of his choice using the given

0:07:13.905,0:07:18.891
public key that we just gave him in the[br]first step. And so, as a result in fact,

0:07:18.891,0:07:23.692
the definition of one time security is[br]enough to imply many time security and

0:07:23.692,0:07:28.801
that's why we refer to the concept as[br]indistinguishability under a chosen plain

0:07:28.801,0:07:34.012
text attach. So this is just a minor point[br]to explain why the settings of public

0:07:34.012,0:07:37.770
encryption, we don't need a more[br]complicated definition to capture

0:07:37.770,0:07:42.515
eavesdropping security. Now that we[br]understand eavesdropping security, let's

0:07:42.515,0:07:47.343
look at more powerful adversaries that can[br]actually mount active attacks. So, in

0:07:47.343,0:07:51.585
particular, let's look at the email[br]example. So here, we have our friend Bob

0:07:51.585,0:07:56.228
who wants to send mail to his friend[br]Caroline. And Caroline happens to have, an

0:07:56.228,0:08:00.699
account at Gmail. And the way this works[br]is basically, the email is sent to the

0:08:00.699,0:08:05.514
Gmail server, encrypted. The Gmail server[br]decrypts the email, looks at the, intended

0:08:05.514,0:08:09.297
recipients. And then, if it's, the[br]intended recipient is Caroline, it

0:08:09.297,0:08:13.653
forwards the email to Caroline. If the[br]intended recipient is the attacker, it

0:08:13.653,0:08:18.573
forwards the email to the attacker. This[br]is similar to how Gmail actually works

0:08:18.573,0:08:23.441
because the sender would send the email[br]encrypted over SSL to the Gmail server.

0:08:23.441,0:08:28.087
The Gmail server would terminate the SSL[br]and then forward the email to the

0:08:28.087,0:08:33.081
appropriate recipients. Now suppose Bob[br]encrypts the email using a system that

0:08:33.081,0:08:37.764
allows the adversary to tamper with the[br]ciphertext without being detected. For

0:08:37.764,0:08:42.387
example, imagine this email is encrypted[br]using Counter Mode, or something like

0:08:42.387,0:08:47.070
that. Then when the attacker intercepts[br]this email, he can change the recipient,

0:08:47.070,0:08:50.732
so that now the recipient says[br]attacker@gmail.com, and we know that for

0:08:50.732,0:08:55.415
Counter Mode, for example, this is quite[br]easy to do. The attacker knows that the

0:08:55.415,0:09:00.278
email is intended for Caroline, he is just[br]interested in the email body. So he can

0:09:00.278,0:09:04.226
easily change the email recipient to[br]attacker@gmail.com and now when the server

0:09:04.226,0:09:08.129
receives the email, he will decrypt it,[br]see that the recipient is supposed to be

0:09:08.129,0:09:12.033
attacker, and forward the body to the[br]attacker. And now the attacker was able to

0:09:12.033,0:09:16.022
read the body of the email that was[br]intended for Caroline. So this is a

0:09:16.022,0:09:21.198
classic example of an active attack, and[br]you notice what the attacker could do

0:09:21.198,0:09:26.174
here, is it could decrypt any ciphertext[br]where the intended recipient is to:

0:09:26.174,0:09:31.548
attacker. So any ciphertext where the plain[br]text begins with the words "to: attacker". So our goal is

0:09:31.548,0:09:36.657
to design public key systems that are[br]secure, even if the attacker can tamper

0:09:36.657,0:09:42.999
with ciphertext and possibly decrypt[br]certain cyphertexts. And again, I want to

0:09:42.999,0:09:47.612
emphasize that here the attacker's goal[br]was to get the message body. The attacker

0:09:47.612,0:09:52.055
already knew that the email is intended[br]for Caroline. And all he had to do was

0:09:52.055,0:09:56.863
just change the, intended recipient. So[br]this tampering attack motivates the

0:09:56.863,0:10:01.620
definition of chosen ciphertext security.[br]And in fact this is the standard notion of

0:10:01.620,0:10:07.462
security for public key encryption. So let[br]me explain how the attack [here procedes] and as I

0:10:07.462,0:10:11.899
said our goal is to build systems that are[br]secure under this very, very conservative

0:10:11.899,0:10:15.756
notion of encryption. So we have an[br]encryption scheme (G, E, D). And let's say

0:10:15.756,0:10:20.140
that's defined over a message space and[br]a ciphertext (M, C) and as usual we're

0:10:20.140,0:10:24.313
gonna define two experiments, experiment[br]zero, and experiment one. So 'b' here

0:10:24.313,0:10:28.222
says whether the challenger is[br]implementing experiment zero or experiment

0:10:28.222,0:10:32.659
one. The challenger begins by generating a[br]public key and a secret key, and then gives

0:10:32.659,0:10:37.254
the public key to the adversary. Now the[br]adversary can say, "Well, here are a bunch

0:10:37.254,0:10:41.611
of ciphertexts, please decrypt them for[br]me." So here the adversary submits

0:10:41.611,0:10:46.452
ciphertext C1 and he gets the decryption[br]of ciphertext C1, namely M1. And he gets

0:10:46.452,0:10:51.414
to do this again and again, so he submits[br]ciphertext C2, and he gets the decryption,

0:10:51.414,0:10:56.195
which is M2, ciphertext C3, and he gets[br]the decryption M3, and so on and so forth.

0:10:56.195,0:11:00.188
Finally, the adversary says, "This[br]squaring phase is over," and now he

0:11:00.188,0:11:04.485
submits basically two equal length[br]messages, M0 and M1 as normal, and he

0:11:04.485,0:11:08.820
receives in response the challenge[br]ciphertext C, Which is the encryption of M

0:11:08.820,0:11:13.052
zero or the encryption of M one. Depending[br]on whether we're in experiment zero or

0:11:13.052,0:11:17.003
experiment one. Now, the adversary can[br]continue to issue these ciphertext

0:11:17.003,0:11:21.063
queries. So he can continue to issue,[br]decryption requests. So he submits a

0:11:21.063,0:11:25.447
ciphertext, and he gets a decryption of[br]that ciphertext, but of course, now, there

0:11:25.447,0:11:29.994
has to be a caveat. If the attacker could[br]submit arbitrary ciphertext of his choice,

0:11:29.994,0:11:34.270
of course, he could break the challenge.[br]What he would do is he would submit the

0:11:34.270,0:11:38.506
challenge ciphertext C as a decryption[br]query. And then he would be told whether

0:11:38.506,0:11:42.665
in the challenge phase he was given the[br]encryption of M0 or the encryption of M1.

0:11:42.665,0:11:46.825
As a result we put this limitation here,[br]that says that he can in fact submit any

0:11:46.825,0:11:51.031
ciphertext of his choice except. For the[br]challenge ciphertext. So the attacker

0:11:51.031,0:11:55.034
could ask for the decryption of any[br]ciphertext of his choice other than the

0:11:55.034,0:11:59.297
challenge ciphertext. And even though he[br]was given all these decryptions, he still

0:11:59.297,0:12:03.196
shouldn't be able to tell whether he was[br]given the encryption of M0 or the

0:12:03.196,0:12:09.212
encryption of M1. So you notice this is a[br]very conservative definition. It gives the

0:12:09.212,0:12:14.113
attacker more power than what we saw in[br]the previous slide. On the previous slide,

0:12:14.113,0:12:18.710
the attacker could only decrypt messages[br]where the plain text began with the words

0:12:18.710,0:12:23.611
"to: attacker". Here, we're saying the attacker[br]can decrypt any ciphertext of his choice,

0:12:23.611,0:12:29.717
as long as it's different from the[br]challenge ciphertext C. Okay? And then his

0:12:29.717,0:12:34.094
goal is to say whether the challenge[br]ciphertext is the encryption of M0 or the

0:12:34.094,0:12:37.918
encryption of M1. And as usual, if he[br]can't do that, in other words, his

0:12:37.918,0:12:42.351
behavior in experiment zero is basically[br]the same as his behavior in experiment

0:12:42.351,0:12:46.839
one, so he wasn't able to distinguish the[br]encryption of M0 from the encryption of

0:12:46.839,0:12:51.219
M1, even though he had all this power Then[br]we say that the system is chosen

0:12:51.219,0:12:55.877
ciphertext secure, CCA secure. And[br]sometimes there is an acronym, the acronym

0:12:55.877,0:13:00.596
for this is indistinguishability under a[br]chosen ciphertext attack, but I'm just

0:13:00.596,0:13:05.745
gonna say CCA secured. So let's see how[br]this captures, the email example we saw

0:13:05.745,0:13:10.587
before. So suppose the encryption system[br]being used is such that just given the

0:13:10.587,0:13:15.429
encryption of a message the attacker can[br]change the intended recipient from to

0:13:15.429,0:13:20.129
Alice say to, to Charlie. Then here's how[br]we would win the CCA game. Well in the

0:13:20.129,0:13:25.033
first step he's given the public key of[br]course. And then what the attacker will do

0:13:25.033,0:13:29.578
is he would issue two equal length[br]messages, namely in the first message, the

0:13:29.578,0:13:33.943
body is zero. In the second message the[br]body is one. But both messages are

0:13:33.943,0:13:39.890
intended for Alice. And in response, he[br]would be given the challenge ciphertext C.

0:13:39.890,0:13:45.130
Okay, so now here we have our challenge[br]ciphertext C. Now what the attacker is

0:13:45.130,0:13:49.961
gonna do is he's gonna use his, his[br]ability here to modify the intended

0:13:49.961,0:13:55.269
recipient. And he's gonna send back a[br]ciphertext C', where C' is the encryption

0:13:55.269,0:14:01.760
of the message to Charlie with body being[br]the challenge body b. So if you remember is

0:14:01.760,0:14:07.822
either zero or one. Now, because the plain[br]text is different, we know that the

0:14:07.822,0:14:12.486
ciphertext must also be different. So in[br]particular, C prime must be different from

0:14:12.486,0:14:17.206
the challenge ciphertext C, yeah? So the[br]C prime here must be different from C. And

0:14:17.206,0:14:21.758
as a result, the poor challenger now has[br]to decrypt by definition of the CCA game.

0:14:21.758,0:14:26.141
The challenger must decrypt any ciphertext[br]that's not equal to a challenge

0:14:26.141,0:14:30.648
ciphertext. So the challenger decrypts[br]give the adversary M prime. Basically he

0:14:30.648,0:14:35.256
gave the adversary B, and now the[br]adversary can output the challenge B and

0:14:35.256,0:14:40.293
he wins the game with advantage one. So[br]he's advantage with this particular scheme

0:14:40.293,0:14:45.143
is one. So, simply because the attacker[br]was able to change the challenge ciphertext

0:14:45.146,0:14:49.999
from one recipient to another that[br]allows him to, to win the CCA game with

0:14:49.999,0:14:55.003
advantage one. So as I said, chosen[br]ciphertext security turns out actually is

0:14:55.003,0:14:59.327
the correct notion of security for public[br]key encryption systems. And it's a very,

0:14:59.327,0:15:03.651
very interesting concept, right? Basically, somehow[br]even though the attacker has this ability

0:15:03.651,0:15:07.839
to decrypt anything he wants. Other than[br]the challenge ciphertext, still he can't

0:15:07.839,0:15:12.028
learn what the challenge ciphertext is.[br]And so the goal for the remainder of this module

0:15:12.028,0:15:16.275
and actually the next module as well, is[br]to construct CCA secure systems. It's

0:15:16.275,0:15:20.093
actually quite remarkable that this is[br]achievable and I'm going to show you

0:15:20.093,0:15:24.310
exactly how to do it. And in fact those[br]CCA secure systems that we build are the

0:15:24.310,0:15:28.579
ones that are used in the real world. And[br]every time a system has tried to deploy

0:15:28.737,0:15:33.007
a public key encryption mechanism that's not[br]CCA secure someone has come up with an

0:15:33.007,0:15:37.487
attack and was able to break it. And we're[br]going to see some of these example attacks

0:15:37.487,0:15:39.280
actually in the next few segments.