0:00:00.000,0:00:04.669
In this segment we will look at how to use[br]block ciphers to encrypt multiple messages

0:00:04.669,0:00:08.959
using the same key. This comes up in[br]practice for example in file systems where

0:00:08.959,0:00:13.412
the same key's used to encrypt multiple[br]files. It comes up in networking protocols

0:00:13.412,0:00:17.647
where the same key is used to encrypt[br]multiple packets. So let's see how to do

0:00:17.647,0:00:21.883
it. The first thing we need to do is to[br]define what is mean for a cipher to be

0:00:21.883,0:00:26.185
secure when the same key is used to[br]encrypt multiple messages. When we use the

0:00:26.185,0:00:31.041
key more than once the result of that is[br]that the adversary gets to see many cyber

0:00:31.041,0:00:35.627
text encrypted using the same key. As a[br]result, when we define security, we're

0:00:35.627,0:00:40.512
gonna allow the adversary to mount what's[br]called a chosen plain text attack. In

0:00:40.512,0:00:45.522
other words, the adversary can obtain the[br]encryption of arbitrary messages of his

0:00:45.522,0:00:49.710
choice. So, for example, if the[br]adversary's interacting with Alice. The

0:00:49.710,0:00:53.924
adversary can ask Alice to encrypt[br]arbitrary messages of the adversary's

0:00:53.924,0:00:58.138
choosing. And Alice will go ahead and[br]encrypt those messages and give the

0:00:58.138,0:01:02.929
adversary the resulting cipher texts. You[br]might wonder why would Alice ever do this.

0:01:02.929,0:01:07.431
How could this possibly happen in real[br]life? But it turns out this is actually

0:01:07.431,0:01:11.760
very common in real life. And in fact,[br]this modeling is quite a conservative

0:01:11.760,0:01:16.320
modeling of real life. For example, the[br]adversary might send Alice an email. When

0:01:16.320,0:01:21.168
Alice receives the email, the writes it to[br]her encrypted disk, thereby encrypting the

0:01:21.168,0:01:26.140
adversary's email using her secret key. If[br]later the adversary steals this disc, then

0:01:26.140,0:01:31.280
he obtains the encryption of an email that[br]he sent Alice under Alice's secret key. So

0:01:31.280,0:01:36.298
that's an example of a chosen plain text[br]attack, where the adversary provided Alice

0:01:36.298,0:01:41.075
with a message and she encrypted that[br]message using her own key. And then later

0:01:41.075,0:01:45.429
the attacker was able to obtain the[br]resulting cipher text. So that's the

0:01:45.429,0:01:49.661
adversary's power. And then the[br]adversary's goal is basically to break

0:01:49.661,0:01:54.368
semantic security. So let's define this[br]more precisely. As usual, we're gonna

0:01:54.368,0:01:59.447
define semantic security under a chosen[br]plain text attack using two experiments,

0:01:59.447,0:02:04.717
experiment zero and experiment one, that[br]are modeled as a game between a challenger

0:02:04.717,0:02:09.669
and an adversary. When the game begins,[br]the challenger is gonna choose a random

0:02:09.669,0:02:14.006
key K. And now the adversary basically[br]gets to query the challenger. So the

0:02:14.006,0:02:18.198
adversary now begins by submitting a[br]semantic security query, namely, he

0:02:18.198,0:02:22.804
submits two messages, M zero and M one. I[br]added another index, but let me ignore

0:02:22.804,0:02:27.351
that extra index for a while. So the[br]adversary submits two messages, M zero and

0:02:27.351,0:02:31.780
M one, that happen to be of the same[br]length. And then the adversary receives

0:02:31.780,0:02:36.031
the encryption of one of those messages,[br]either of M zero or of M one. In

0:02:36.031,0:02:40.224
experiment zero, he receives the[br]encryption of M zero. In experiment one,

0:02:40.224,0:02:44.952
he receives the encryption of M one. So,[br]so far this would look familiar this looks

0:02:44.952,0:02:49.477
exactly like a standard semantic security[br][inaudible]. However, plain text attack

0:02:49.477,0:02:54.007
the adversary can now repeat this query[br]again. So now you can issue a query with

0:02:54.007,0:02:58.485
two other plain texts, again of the same[br]length, and again you would receive the

0:02:58.485,0:03:03.189
encryption of one of them. In experiment[br]zero you would receive the encryption of M

0:03:03.189,0:03:07.837
zero. In experiment one you would receive[br]the encryption of M one. And the attacker

0:03:07.837,0:03:12.542
can continue issuing queries like this. In[br]fact we'll say that he can issue up to Q

0:03:12.542,0:03:17.020
queries of this type. And then, remember,[br]every time he issues a pair of messages.

0:03:17.020,0:03:21.416
That happen to be of the same length and[br]every time he either gets the encryption

0:03:21.416,0:03:25.867
of the left side or the right side again[br]in experiment zero he will always get the

0:03:25.867,0:03:29.727
encryption of the left message in[br]experiment one he will always get the

0:03:29.727,0:03:33.970
encryption of the left message. And, then[br]adversary's goal is, basically, to figure

0:03:33.970,0:03:38.289
out whether he's in experimental zero or[br]in experiment one. In other words, whether

0:03:38.289,0:03:42.713
he was constantly receiving the encryption[br]of the left message or the encryption of

0:03:42.713,0:03:47.032
the right message. So, in some sense, this[br]is a standard semantic security game just

0:03:47.032,0:03:51.193
iterated over many queries that the[br]attacker can issue to adaptively one after

0:03:51.193,0:03:56.014
the other. Now the chosen plain text[br]attack is captured by the fact that if the

0:03:56.014,0:04:00.646
attacker wants the encryption of a[br]particular message m. What he could do is,

0:04:00.646,0:04:05.234
for example, use query J for sum J, where[br]in this query J he'll set both the zero

0:04:05.234,0:04:09.593
message and the one message to be the[br]exactly same message M. In other words,

0:04:09.593,0:04:14.008
both the left message and the right[br]message are the same, and both are set to

0:04:14.008,0:04:18.653
the message M. In this case, what he will[br]receive, since both messages are the same,

0:04:18.653,0:04:23.126
he knows that he's gonna receive the[br]encryption of this message M that he was

0:04:23.126,0:04:27.600
interested in. So this is exactly what we[br]meant by a chosen [inaudible] attack.

0:04:27.600,0:04:32.598
Where the advisory can submit a message m[br]and receive the encryption of that

0:04:32.598,0:04:37.429
particular message m of his choice. So[br]some of his queries might be of this chose

0:04:37.429,0:04:42.157
plain text flavor where the message on the[br]left is equal to the message on the right,

0:04:42.157,0:04:46.775
but some of the queries might be standard[br]semantic security queries where the two

0:04:46.775,0:04:51.281
messages are distinct and that actually[br]gives him information on whether he's in

0:04:51.281,0:04:55.453
experiment zero or in experiment one. Now[br]by now you should be used to this

0:04:55.453,0:05:00.182
definition where we say that the system is[br]semantically secure under a chosen plain

0:05:00.182,0:05:04.141
text attack. If, for all efficient[br]adversaries, they cannot distinguish

0:05:04.141,0:05:08.703
experiment zero from experiment one. In[br]other words, the probability that, at the

0:05:08.703,0:05:13.091
end, the output, B Prime, which we're[br]gonna denote by the output of experiment

0:05:13.091,0:05:17.769
B. This output will be the same whether[br][inaudible] experiment zero or experiment

0:05:17.769,0:05:22.310
one. So the attacker couldn't distinguish[br]between always receiving encryptions of

0:05:22.310,0:05:26.900
the left messages, versus always receiving[br]encryptions of the right messages. So in

0:05:26.900,0:05:31.267
your mind, I'd like you to be thinking of[br]an adversary that is able to mount a

0:05:31.267,0:05:35.745
chosen plaintext attack, namely, be given[br]the encryption of arbitrary messages of

0:05:35.745,0:05:40.168
his choice, and his goal is to break[br]semantic security for some other challenge

0:05:40.168,0:05:44.330
cipher texts. And as I said in this[br][inaudible] model of the real world the

0:05:44.330,0:05:48.721
attacker is able to fool Alice into[br]encrypting for him messages of his choice

0:05:48.721,0:05:53.287
and then the attacker's goal is to somehow[br]break some challenge cypher text. So I

0:05:53.287,0:05:58.173
claim that all the ciphers that we've seen[br]up until now, namely deterministic counter

0:05:58.173,0:06:02.541
mode or the one time pad, are insecure[br]under a chosen plain text attack. More

0:06:02.541,0:06:07.312
generally, suppose we have an encryption[br]scheme that always outputs the same cipher

0:06:07.312,0:06:11.968
text for a particular message M. In other[br]words, if I ask the encryption scheme to

0:06:11.968,0:06:16.188
encrypt the message M once. And then I ask[br]the encryption scheme to encrypt the

0:06:16.188,0:06:21.183
message m again. If in both cases the[br]encryption scheme outputs the same cypher

0:06:21.183,0:06:26.550
text, then that system cannot possibly be[br]secure under a chosen plain text attack.

0:06:26.550,0:06:31.281
And both deterministic counter mode and[br]the one time pad were of that flavor. They

0:06:31.281,0:06:35.923
always output the same cipher text, given[br]the same message. And so let's see why

0:06:35.923,0:06:41.143
that cannot be chosen plain text secure.[br]And the attack is fairly simple, what the

0:06:41.143,0:06:46.300
attacker is gonna do, is he's gonna output[br]the same message twice. This just says.

0:06:46.300,0:06:51.233
That he really wants the encryption of M0.[br]So here the attacker is given C0 which is

0:06:51.233,0:06:55.872
the encryption of M0. So this was his[br]chosen plain text query where he actually

0:06:55.872,0:07:00.805
received the encryption of the message M0[br]of his choice. And now he's going to break

0:07:00.805,0:07:05.445
semantic security. So what he does is he[br]outputs two messages, M0 and M1 of the

0:07:05.445,0:07:10.084
same length, and he's going to be given[br]the encryption of MB. But low and behold,

0:07:10.084,0:07:15.850
we said that the encryption system. Always[br]outputs the same cipher text when its

0:07:15.850,0:07:21.539
encrypting the message, M0. Therefore, if[br]B is=to zero, we know that C, this

0:07:21.539,0:07:27.310
challenged cipher text, is simply=to CO,[br]because it's the encryption of M0.

0:07:27.310,0:07:32.409
However, if B is=to one. Then we know that[br]this challenge cypher text is the

0:07:32.409,0:07:38.048
encryption of M1 which is something other[br]than C zero so all the attacker does is he

0:07:38.048,0:07:43.441
just checks his C is = to C0 the output's[br]zero in other words he outputs one. So, in

0:07:43.441,0:07:47.722
this case, the attacker is able to[br]perfectly guess this bit B, so he knows

0:07:47.722,0:07:52.412
exactly [inaudible] given the encryption[br]of M0, or the encryption of M1. And as a

0:07:52.412,0:07:57.103
result, his advantage in winning this game[br]is one. Meaning that the system cannot

0:07:57.103,0:08:01.491
possibly be CPA secure. One is not a[br]negligible number. So this shows that the

0:08:01.491,0:08:05.582
deterministic encryption schemes cannot[br]possibly be CPA-secure, but you might

0:08:05.582,0:08:09.345
wonder well, what does this mean in[br]practice? Well in practice this means

0:08:09.345,0:08:13.111
again that every message is always[br]encrypted to the same cipher text. What

0:08:13.111,0:08:17.234
this means is if you're encrypting files[br]on disk, and you happen to be encrypting

0:08:17.234,0:08:21.407
two files that happen to be the same, they[br]will result in the same cipher text and

0:08:21.407,0:08:25.327
then the attacker by looking at the[br]encrypted disk, will learn that these two

0:08:25.327,0:08:29.297
files actually contain the same content.[br]The attacker might not learn what the

0:08:29.297,0:08:33.419
content is, but he will learn that these[br]two encrypted files are an encryption of

0:08:33.419,0:08:37.524
the same content and he shouldn't be able[br]to learn that. Similarly, if you send two

0:08:37.524,0:08:41.287
encrypted packets on the network that[br]happen to be the same, the attacker will

0:08:41.287,0:08:45.146
not learn the content of those packets,[br]but he will learn that those two packets

0:08:45.146,0:08:49.301
actually contain the same information.[br]Think for example of an encrypted voice

0:08:49.301,0:08:53.769
conversation. Every time there's quiet on[br]the line, the system will be sending

0:08:53.769,0:08:58.072
encryptions of zero. But since encryption[br]of zero are always mapped to the same

0:08:58.072,0:09:02.334
cypher text. An attacker looking at the[br]network will be able to identify exactly

0:09:02.334,0:09:06.489
the points in the conversation where[br]there's quiet because he will always see

0:09:06.489,0:09:11.113
those exact same cypher text every time.[br]So these are examples where deterministic

0:09:11.113,0:09:15.492
encryption cannot possibly be secure. And[br]as I say formerly we say that the

0:09:15.492,0:09:19.800
terministic encryption can not be[br]semantically secure under a chosen plain

0:09:19.800,0:09:24.743
text attack. So what do we do, well the[br]lesson here is if the secret keys gonna be

0:09:24.743,0:09:29.674
used to encrypt multiple messages, it had[br]better be the case that given the same

0:09:29.674,0:09:33.572
plain text to encrypt twice. The[br]encryption algorithm must produce

0:09:33.572,0:09:38.147
different cipher texts. And so there are[br]two ways to do that. The first method is

0:09:38.147,0:09:42.836
what's called randomized encryption. Here,[br]the encryption algorithm itself is going

0:09:42.836,0:09:47.296
to choose some random string during the[br]encryption process and it is going to

0:09:47.296,0:09:51.642
encrypt the message M using that random[br]string. So what this means is that a

0:09:51.642,0:09:56.389
particular message, M0 for example, isn't[br]just going to be mapped to one cipher text

0:09:56.389,0:10:00.894
but it's going to be mapped to a whole[br]ball of cipher texts. Whereon every

0:10:00.894,0:10:06.692
encryption, basically, we output one point[br]in this ball. So every time we encrypt, the

0:10:06.692,0:10:11.292
encryption algorithm chooses a random[br]string, and that random string leads to

0:10:11.292,0:10:15.832
one point in this ball. Of course, the[br]decryption algorithm, when it takes any

0:10:15.832,0:10:20.610
point in this ball, will always map the[br]result to M zero. Similarly cipher text M

0:10:20.610,0:10:25.449
one will be mapped to a ball, and every[br]time we encrypt M one, we basically output

0:10:25.449,0:10:29.690
one point in this ball. And these balls[br]have to be disjoint, so that the

0:10:29.690,0:10:34.469
encryption algorithm, when it obtains a[br]point in the ball corresponding to M one,

0:10:34.469,0:10:38.964
will always output the message M one. In[br]this way, since the encryption algorithm

0:10:38.964,0:10:43.266
uses randomness, if we encrypt the same[br]message twice, with high probability we'll

0:10:43.266,0:10:47.144
get different cipher texts. Unfortunately[br]this means that the cipher text

0:10:47.144,0:10:51.393
necessarily has to be longer than the[br]plain text because somehow the randomness

0:10:51.393,0:10:55.855
that was used to generate the cipher text[br]is now encoded somehow in the cipher text.

0:10:55.855,0:11:00.158
So the cipher text takes more space. And[br]roughly speaking, the cipher text size is

0:11:00.158,0:11:04.620
going to be larger than the plain text. By[br]basically the number of random bits that

0:11:04.620,0:11:08.748
were used during encryption. So if the[br]plain texts are very big, if the plain

0:11:08.748,0:11:13.203
texts are gigabytes long, the number of[br]random bits is going to be on the order of

0:11:13.203,0:11:17.494
128. So maybe this extra space doesn't[br]really matter. But if the plain texts are

0:11:17.494,0:11:21.786
very short, maybe they themselves are 128[br]bits, then adding an extra 128 bits to

0:11:21.786,0:11:26.240
every cipher text is going to double the[br]total cipher text size. And that could be

0:11:26.240,0:11:31.117
quite expensive. So as I say randomized[br]encryption is a fine solution but in some

0:11:31.117,0:11:35.862
cases it actually introduces quite a bit[br]of costs. So let's look at a simple example.

0:11:35.862,0:11:41.107
So imagine we have a pseudorandom[br]function that takes inputs in a certain

0:11:41.107,0:11:46.223
space r which is gonna be called a nonce[br]space. And outputs, outputs in the message

0:11:46.223,0:11:50.636
space. And, now, let's define the[br]following randomize encryption scheme

0:11:50.636,0:11:55.880
where we want to encrypt the message m[br]with the encryption of whatever it's gonna

0:11:55.880,0:12:01.149
do is first it's gonna generate a random r[br]in this nonce space R. And then it's going

0:12:01.149,0:12:06.232
to open a cypher text that consist of two[br]components, the first component is going

0:12:06.232,0:12:10.943
to be this value R and the second[br]component is going to be an evaluation of

0:12:10.943,0:12:16.180
the pseudo-random function at the point R[br]XOR with the message M. And my question to

0:12:16.180,0:12:21.397
you is, is this encryption system[br]semantically secure under a chosen plain

0:12:21.397,0:12:26.290
text attack. So the correct answer is yes.[br]But only if the nonce space R is large

0:12:26.290,0:12:31.249
enough so that little R never repeats with[br]very, very high probability. And let's

0:12:31.249,0:12:36.332
quickly argue why that's true. So first of[br]all, because F is a secure pseudo-random

0:12:36.332,0:12:41.352
function, we might as well replace it with[br]a truly random function. In other words,

0:12:41.352,0:12:46.373
this is indistinguishable from the case[br]where we encrypt the message M, using the

0:12:46.373,0:12:51.252
truly random function little F, evaluated[br]to point R, and then XOR with M.

0:12:51.252,0:12:57.320
But since this little r never repeats every[br]cypher text uses a different little r what

0:12:57.320,0:13:03.095
this means is that the values of F(r)[br]are random uniform independent strings

0:13:03.095,0:13:08.818
every time. So every time we encrypt a[br]message, we encrypt it essentially using a

0:13:08.818,0:13:14.369
new uniform random one time pad. And since[br]XORing a uniform string with any string

0:13:14.369,0:13:19.666
simply generates a new uniform string, the[br]resulting cipher text is distributed as

0:13:19.666,0:13:24.767
simply two random uniform strings. I'll[br]call them r and r prime. And so both in

0:13:24.767,0:13:30.325
experiment zero and in experiment one, all[br]the attacker gets to see are truly uniform

0:13:30.325,0:13:35.622
random strings r, r', and since in both[br]experiments the attacker is seeing the same

0:13:35.622,0:13:40.666
distribution, he cannot distinguish the[br]two distributions. And so since security

0:13:40.666,0:13:45.695
holds completely when we're using a truly[br]random function it's also gonna hold when

0:13:45.695,0:13:50.559
we're using a pseudorandom function. Okay,[br]so this is a nice example of how we use

0:13:50.559,0:13:55.435
the fact that the pseudo random function[br]behaves like a random function to argue

0:13:55.435,0:13:59.829
security of this particular encryption[br]scheme. Okay, so now we have a nice

0:13:59.829,0:14:04.465
example of randomized encryption. The[br]other approach to building chosen plain

0:14:04.465,0:14:09.344
text secure encryption schemes is what's[br]called a nonce based encryption. Now, in

0:14:09.344,0:14:14.012
a non-spaced encryption system, the[br]encryption algorithm actually takes three

0:14:14.012,0:14:19.044
inputs rather than two. As usual it takes[br]the key and the message. But it also takes

0:14:19.044,0:14:23.773
an additional input called a nonce. And[br]similarly, the decryption algorithm also

0:14:23.773,0:14:28.683
takes the nonce as input, and then produces[br]the resulting decrypted plain text. And

0:14:28.683,0:14:33.529
what is this nonce value n. This nonce is[br]a public value. It does not need to be

0:14:33.529,0:14:38.402
hidden from the adversary but the only[br]requirement is that the pair (k,n)

0:14:38.402,0:14:43.213
is only used to encrypt a single[br]message. In other words, this pair (k,n)

0:14:43.213,0:14:48.148
must change from message to message. And[br]there are two ways to change it. One way

0:14:48.148,0:14:53.144
to change it is by choosing a new random[br]key for every message. And the other way

0:14:53.144,0:14:58.276
is to keep using the same key all the time[br]but then we must choose a new nonce for

0:14:58.276,0:15:02.721
every message. And, and as I said, I wanna[br]emphasize again, this nonce need not

0:15:02.721,0:15:06.823
be secret, and it need not be random. The[br]only requirement is the nonce is unique.

0:15:06.823,0:15:11.029
And in fact, we're gonna use this[br]term throughout the course. A nonce

0:15:11.029,0:15:15.247
for us, means a unique value that doesn't[br]repeat. It does not have to be random. So

0:15:15.247,0:15:19.891
let's look at some examples of choosing an[br]nonce, well the simplest option is

0:15:19.891,0:15:24.255
simply to make the nonce of the[br]accounter so for example the networking

0:15:24.255,0:15:28.898
protocol you can imagine the nonce[br]being a packet counter that's incremented

0:15:28.898,0:15:33.598
every time a packet is sent by a sender or[br]received by the receiver this means that

0:15:33.598,0:15:37.962
the encrypter has to keep state from[br]message to message mainly that he has to

0:15:37.962,0:15:42.270
keep this counter around and increment it[br]after every message is transmitted.

0:15:42.270,0:15:47.487
Interestingly, if the decrypter actually[br]has the same state then there is no need

0:15:47.487,0:15:52.705
to include the nuance in the cipher text[br]since the nuance is implicit. Let's look

0:15:52.705,0:15:57.987
at an example. The https protocol is run[br]over a reliable transport mechanism which

0:15:57.987,0:16:03.075
means that packets sent by the sender are[br]assumed to be received in order at a

0:16:03.075,0:16:07.645
recipient. So if the sender sends packet #5 and then packet #6, the recipient

0:16:07.645,0:16:12.068
will receive packet #5 and then[br]packet #6 in that order. This

0:16:12.068,0:16:16.215
means that if the sender maintains a[br]packet counter, the recipient can also

0:16:16.215,0:16:20.860
maintain a packet counter and two counters[br]basically increment in sync. In this case

0:16:20.860,0:16:24.896
there is no reason to include the[br]nonce in the packets because the

0:16:24.896,0:16:29.476
nonce is implicit between the two[br]sides. However, in other protocols, for

0:16:29.476,0:16:34.600
example, in IPsec, IPsec has a protocol[br]designed to encrypt the IP layer. The IP

0:16:34.600,0:16:39.330
layer does not guarantee in order[br]delivery. And so the sender might send

0:16:39.330,0:16:44.520
packet #5 and then packet #6, but[br]those will be received in reverse order at

0:16:44.520,0:16:49.164
the recipient. In this case it's still[br]fine to use a packet counter as a nonce

0:16:49.164,0:16:53.748
but now the nonce has to be included in[br]the packet so that the recipient knows

0:16:53.748,0:16:58.102
which nonce to use to decrypt the[br]received packet. So as I say, nonce based

0:16:58.102,0:17:02.686
encryption is a very efficient way to[br]achieve CPA security. In particular if the

0:17:02.686,0:17:07.098
nonce is implicit, it doesn't even[br]increase the cipher text length. Of course

0:17:07.098,0:17:11.796
another method to generate a unique nonce[br]is simply to pick the nonce at random

0:17:11.796,0:17:16.495
assuming the nonce space is sufficiently[br]large so that with high probability the

0:17:16.495,0:17:21.579
nonce will never repeat for the life of[br]the key. Now in this case, nonce

0:17:21.579,0:17:26.098
based encryption simply reduces to[br]randomized encryption. However, the

0:17:26.098,0:17:31.600
benefit here is that the sender does not[br]need to maintain any state from message to

0:17:31.600,0:17:36.382
message. So this is very useful for[br]example if encryption happens to take

0:17:36.382,0:17:41.425
place on multiple devices. For example, I[br]might have both a laptop and a smart

0:17:41.425,0:17:46.096
phone. They might both use the same key.[br]But in this case if I require state full

0:17:46.097,0:17:49.961
encryption, then my laptop and the[br]smartphone would have to coordinate to

0:17:49.961,0:17:54.302
make sure that they never reuse the same[br]nonces. Whereas if both of them simply take

0:17:54.302,0:17:58.114
nonces at random, they don't need to[br]coordinate because it was very high

0:17:58.114,0:18:02.243
probability they'll simply never choose[br]the same nonce. Again assuming the nonce

0:18:02.243,0:18:06.478
space is big enough. So there are some[br]cases where stateless encryption is quite

0:18:06.478,0:18:10.562
important, in particular where the same[br]key is used by multiple machines. So I

0:18:10.562,0:18:14.492
wanted to find, more precisely, what[br]security means for nonce based

0:18:14.492,0:18:18.694
encryption. And in particular, I want to[br]emphasize that the system must remain

0:18:18.694,0:18:23.122
secure when the nonce are chosen by[br]the adversary. The reason it's important

0:18:23.122,0:18:27.027
to allow the adversary to choose the[br]nonces is because the adversary can

0:18:27.027,0:18:31.090
choose which cipher text it wants to[br]attack. So imagine the nonce happens to

0:18:31.090,0:18:35.364
be a counter and it so happens that when[br]the couter hits the value fifteen, maybe

0:18:35.364,0:18:39.428
at that point it's easy for the adversary[br]to break semantic security. So the

0:18:39.428,0:18:43.702
adversary will wait until the fifteenth[br]packet is sent and only then he will ask

0:18:43.702,0:18:48.076
to break semantic security. So when we[br]talk about nonce based encryption, we

0:18:48.076,0:18:52.806
generally allow the adversary to choose[br]the nonce and the system should remain

0:18:52.806,0:18:57.772
secure even under those settings. So let's[br]define the CPA game in this case and it's

0:18:57.772,0:19:02.442
actually very similar to the game before.[br]Basically the attacker gets to submit

0:19:02.442,0:19:06.935
pairs of messages MI, MI0, and MI1.[br]Obviously they both have to be of the same

0:19:06.935,0:19:11.576
length. And he gets to supply the nonce.[br]And in response, the adversary is given

0:19:11.576,0:19:16.304
the encryption of either MI0, or MI1. But[br]using the nonce that the adversary

0:19:16.304,0:19:20.740
chose. And of course, as usual, the[br]adversary's goal is to tell whether he was

0:19:20.740,0:19:25.096
given the encryption of the left plain[br]text or the right plain text. And as

0:19:25.096,0:19:29.464
before the adversary gets to iterate these[br]queries and he can issue as, as many

0:19:29.464,0:19:33.610
queries as he wants, we usually let q[br]denote the number of queries that the

0:19:33.610,0:19:37.956
adversary issues. Now the only restriction[br]of course, which is crucial, is that

0:19:37.956,0:19:42.329
although the adversary gets to choose the[br]nonces, he's restricted to choosing

0:19:42.329,0:19:46.758
distinct nonces. The reason we force him[br]to choose distinct nonces is because

0:19:46.758,0:19:50.959
that's the requirement in practice. Even[br]if the adversary fools Alice into

0:19:50.959,0:19:55.161
encrypting multiple messages for him,[br]Alice will never use the same nonce

0:19:55.161,0:19:59.477
again. As a result, the adversary will[br]never see messages encrypted using the

0:19:59.477,0:20:03.678
same nonce and therefore, even in the[br]game, we require that all nonce be

0:20:03.678,0:20:08.305
distinct. And then as usual we say that[br]the system is a nonce based encryption

0:20:08.305,0:20:13.412
system that's, semantically secure under a[br]chosen plain text attack if the adversary

0:20:13.421,0:20:17.890
cannot distinguish experiment zero where[br]he's given encryptions of the left

0:20:17.890,0:20:22.593
messages from experiment one where he's[br]given encryptions of the right messages.

0:20:22.593,0:20:27.121
So let's look at an example of a nonce[br]based encryption system. As before, we

0:20:27.121,0:20:32.119
have a secure PRF that takes inputs in the[br]nonce space R and outputs strings in the

0:20:32.119,0:20:36.823
message space M. Now when a new key is[br]chosen, we're going to reset our counter R

0:20:36.823,0:20:41.006
to be zero. And now we encrypt the[br]particular message M, what we will do is

0:20:41.006,0:20:45.103
we will increment our counter R, and then[br]encrypt the message M using the

0:20:45.103,0:20:49.481
pseudorandom function applied to this[br]value R. And as before, the cipher text is

0:20:49.481,0:20:53.859
going to contain two components, our[br]current value of the counter and then the

0:20:53.859,0:20:58.518
one time pad encryption of the message M.[br]And so my question to you is whether this

0:20:58.518,0:21:03.312
is a secure, non-spaced encryption system.[br]So the answer as before is yes, but only

0:21:03.312,0:21:08.485
if the nuance space is large enough. So as[br]we increment the counter R, it will never

0:21:08.485,0:21:13.284
cycle back to zero so that the nuances[br]will always, always be unique. We argue

0:21:13.284,0:21:18.020
security the same way as before. Because[br]the PRF is secure, we know that this

0:21:18.020,0:21:22.819
encryption system is indistinguishable[br]from using a truly random function. In

0:21:22.819,0:21:27.493
other words, if we apply a truly random[br]function to the counter and XOR the

0:21:27.493,0:21:32.602
results with, the plain text M. But now[br]since the nuance R never repeats, every

0:21:32.602,0:21:37.447
time we compute this F of R, we get a[br]truly random uniform and independent

0:21:37.447,0:21:42.843
string so that we're actually encrypting[br]every message using the one time pad. And

0:21:42.843,0:21:48.306
as a result, all the adversary gets to see[br]in both experiments are basically just a

0:21:48.306,0:21:52.751
pair of random strings. So both the[br]experiment zero and experiment one the

0:21:52.751,0:21:57.408
adversary get's to see exactly the same[br]distribution, namely, the responses to all

0:21:57.408,0:22:02.064
this chosen plain text queries are just[br]pairs of strings that are just uniformly

0:22:02.064,0:22:06.950
distributed and this is basically the same[br]in experiment zero and experiment one and,

0:22:06.950,0:22:11.664
therefore, the attacker cannot distinguish[br]the two experiments. And since he cannot

0:22:11.664,0:22:16.206
win the semantic security game with a[br]truly random function he, also, cannot win

0:22:16.206,0:22:20.517
the semantics security game with the[br]secure PRF, and, therefore, the scheme is

0:22:20.517,0:22:25.222
secure. So now we understand what it means[br]for a symmetric system to be secure when

0:22:25.222,0:22:30.091
the keys used to encrypt multiple messages[br]the requirement is that it be secure under

0:22:30.091,0:22:34.777
a chosen plan of attack. And we said that[br]basically, the only way to be secure under

0:22:34.777,0:22:39.289
a chosen plain text attack is either to[br]use randomized encryption, or to use, use

0:22:39.289,0:22:43.462
nonce spaced encryption where the[br]nonce never repeats. And then in the

0:22:43.462,0:22:48.143
next two segments, we're gonna build two[br]classic encryption systems that are secure

0:22:48.143,0:22:50.174
when the key is used multiple times.