0:00:00.000,0:00:04.134
So now that we understand what a secure[br]PRG is, and we understand what semantic

0:00:04.134,0:00:08.425
security means, we can actually argue that[br]a stream cipher with a secure PRG is, in

0:00:08.425,0:00:12.559
fact, a semantically secure. So that's our[br]goal for this, segment. It's a fairly

0:00:12.559,0:00:16.746
straightforward proof, and we'll see how[br]it goes. So the theory we wanna prove is

0:00:16.746,0:00:20.932
that, basically, given a generator G that[br]happens to be a secured, psedo-random

0:00:20.932,0:00:24.805
generator. In fact, the stream cipher[br]that's derived from this generator is

0:00:24.805,0:00:28.924
going to be semantically secure. Okay and[br]I want to emphasize. That there was no

0:00:28.924,0:00:33.085
hope of proving a theorem like this for[br]perfect secrecy. For Shannons concept of

0:00:33.085,0:00:37.193
perfect secrecy. Because we know that a[br]stream cipher can not be perfectly

0:00:37.193,0:00:41.264
secure because it has short keys. And[br]perfect secrecy requires the keys to be as

0:00:41.264,0:00:45.321
long as the message. So this is really[br]kind of the first example the we see where

0:00:45.321,0:00:49.229
we're able to prove that a cipher with[br]short keys has security. The concept of

0:00:49.229,0:00:53.236
security is semantic security. And this[br]actually validates that, really, this is a

0:00:53.236,0:00:56.943
very useful concept. And in fact, you[br]know, we'll be using semantic security

0:00:56.943,0:01:00.750
many, many times throughout the course.[br]Okay, so how do we prove a theory like

0:01:00.750,0:01:04.257
this? What we're actually gonna be doing,[br]is we're gonna be proving the

0:01:04.257,0:01:08.264
contrapositive. What we're gonna show is[br]the following. So we're gonna prove this

0:01:08.264,0:01:12.815
statement down here, but let me parse it[br]for you. Suppose. You give me a semantic

0:01:12.815,0:01:18.345
security adversary A. What we'll do is[br]we'll build PRG adversary B to satisfy

0:01:18.345,0:01:23.686
this inequality here. Now why is this[br]inequality useful? Basically what do we

0:01:23.686,0:01:28.878
know? We know that if B is an efficient[br]adversary. Then we know that since G is a

0:01:28.878,0:01:33.053
secure generator, we know that this[br]advantage is negligible, right? A secure

0:01:33.053,0:01:37.510
generator has a negligible advantage[br]against any efficient statistical test. So

0:01:37.510,0:01:42.023
the right hand side, basically, is gonna[br]be negligible. But because the right hand

0:01:42.023,0:01:46.023
side is negligible, we can deduce that the[br]left hand side is negligible.

0:01:46.023,0:01:50.767
And therefore, the adversary that you looked[br]at actually has negligible advantage in

0:01:50.767,0:01:54.538
attacking the stream cipher E. Okay. So[br]this is how this, this will work.

0:01:54.538,0:01:58.486
Basically all we have to do is given an[br]adversary A we're going to build an

0:01:58.486,0:02:02.591
adversary B. We know that B has negligible[br]advantage against generator but that

0:02:02.591,0:02:06.036
implies that A has negligible advantage[br]against the stream cipher.

0:02:06.082,0:02:10.994
So let's do that. So all we have to do again[br]is given A, we have to build B.

0:02:10.994,0:02:15.183
So let A be a semantic security adversary against[br]the stream cipher. So let me remind you

0:02:15.183,0:02:19.320
what that means. Basically, there's a[br]challenger. The challenger starts off by

0:02:19.320,0:02:23.509
choosing the key K. And then the adversary[br]is gonna output two messages, two equal

0:02:23.509,0:02:27.383
length messages. And he's gonna receive[br]the encryption of M0 or M1

0:02:27.383,0:02:31.226
and outputs B1. Okay, that's[br]what a semantic security adversary is

0:02:31.226,0:02:34.933
going to do. So now we're going to start[br]playing games with this adversary. And

0:02:34.933,0:02:38.498
that's how we're going to prove our lemma. Alright, so the first thing

0:02:38.498,0:02:42.535
we're going to do is we're going to make[br]the challenger. Also choose a random R.

0:02:42.535,0:02:47.500
Okay, a random string R. So, well you know[br]the adversary doesn't really care what the

0:02:47.500,0:02:52.405
challenger does internally. The challenger[br]never uses R, so this doesn't affect the

0:02:52.405,0:02:56.365
adversary's advantage at all. The[br]adversary just doesn't care that the

0:02:56.365,0:03:00.706
challenger also picks R. But now comes the[br]trick. What we're going to do is we're

0:03:00.706,0:03:05.042
going to, instead of encrypting using GK.[br]We're going to encrypt using R. You can

0:03:05.042,0:03:09.993
see basically what we're doing[br]here. Essentially we're changing the

0:03:09.993,0:03:14.219
challenger so now the challenge[br]cipher text is encrypted using a

0:03:14.219,0:03:19.006
truly random pad. As opposed to just pseudo[br]random pad GK. Okay. Now, the property of

0:03:19.006,0:03:23.639
the pseudo-random generator is that its[br]output is indistinguishable from truly

0:03:23.639,0:03:28.273
random. So, because the PRG is secure, the[br]adversary can't tell that we made this

0:03:28.273,0:03:33.082
change. The adversary can't tell that we[br]switched from a pseudo-random string to a

0:03:33.082,0:03:37.422
truly random string. Again, because the generator is secure. Well, but now look at

0:03:37.422,0:03:41.762
the game that we ended up with. So the[br]adversary's advantage couldn't have

0:03:41.762,0:03:46.630
changed by much, because he can't tell the[br]difference. But now look at the game that

0:03:46.630,0:03:51.073
we ended up with. Now this game is truly a[br]one time pad game. This a semantic

0:03:51.073,0:03:55.803
security game against the one time pad.[br]Because now the adversary is getting a one

0:03:55.803,0:04:00.238
time pad encryption of M0 or M1 But in the[br]one time pad we know that the adversaries

0:04:00.238,0:04:04.048
advantage is zero, because you can't beat[br]the one time pad. The one time pad is

0:04:04.048,0:04:08.165
secure Unconditionally secure. And as a[br]result, because of this. Essentially

0:04:08.165,0:04:12.674
because the adversary couldn't have told[br]the difference when

0:04:12.674,0:04:17.013
we moved from pseudo random to random. But he couldn't win the[br]random game. That also means that he

0:04:17.013,0:04:21.411
couldn't win the sudo random game. And as[br]a result, the stream cipher, the original

0:04:21.411,0:04:25.634
stream cipher must be secure. So that's[br]the intuition for how the proof is gonna go.

0:04:25.634,0:04:29.594
But I wanna do it rigorously once.[br]From now on, we're just gonna argue by

0:04:29.594,0:04:33.975
playing games with our challenger. And, we[br]won't be doing things as formal as I'm

0:04:33.975,0:04:38.304
gonna do next. But I wanna do formally and[br]precisely once, just so that you see how

0:04:38.304,0:04:42.629
these proofs actually work. Okay, so I'm[br]gonna have to introduce some notation. And

0:04:42.629,0:04:47.751
I'll do the usual notation, basically. If[br]the original semantics are here at the

0:04:47.751,0:04:52.937
beginning, when we're actually using a[br]pseudo-random pad, I'm gonna use W0 and W1

0:04:52.937,0:04:58.059
to denote the event that the adversary[br]outputs one, when it gets the encryption

0:04:58.059,0:05:02.856
of M0, or gets the encryption of M1,[br]respectively. Okay? So W0 corresponds to

0:05:02.856,0:05:07.719
outputting 1 when receiving the[br]encryption of M0. And W1 corresponds

0:05:07.719,0:05:13.141
to outputting 1 when receiving the encryption of M1. So that's the standard

0:05:13.141,0:05:19.606
definition of semantic security. Now once[br]we flip to the random pad. I'm gonna use

0:05:19.606,0:05:24.505
R0 and R1 to denote the event that the[br]adversary outputs 1 when receiving the

0:05:24.505,0:05:29.125
one-type pad encryption of M0 or the[br]one-time pad encryption of M1. So we have

0:05:29.125,0:05:33.567
four events, W0, W1 from the original[br]semmantics security game, and R0 and R1

0:05:33.567,0:05:38.365
from the semmantics security game once we[br]switch over to the one-time pad. So now

0:05:38.365,0:05:42.985
let's look at relations between these[br]variables. So first of all, R0 and R1 are

0:05:42.985,0:05:47.427
basically events from a semmantics[br]security game against a one-time pad. So

0:05:47.427,0:05:51.929
the difference between these probabilities[br]is that, as we said, basically the

0:05:51.929,0:05:56.902
advantage of algorithm A, of adversary A,[br]against the one-time pad. Which we know is

0:05:56.902,0:06:01.231
zero. Okay, so that's great. So that[br]basically means that probability of, of R0

0:06:01.231,0:06:05.662
is equal to the probability of R1. So now,[br]let's put these events on a line, on a

0:06:05.662,0:06:10.261
line segment between zero and one. So here[br]are the events. W0 and W1 are the events

0:06:10.261,0:06:14.499
we're interested in. We wanna show that[br]these two are close. Okay. And the way

0:06:14.499,0:06:18.490
we're going to do it is basically by[br]showing, oh and I should say, here is

0:06:18.490,0:06:22.754
probability R0 and R1, it says[br]they're both same, I just put them in the

0:06:22.754,0:06:27.237
same place. What we're gonna do is we're[br]gonna show that both W0 and W1 are

0:06:27.237,0:06:31.720
actually close to the probability of RB[br]and as a result they must be close to one

0:06:31.720,0:06:35.656
another. Okay, so the way we do that is[br]using a second claim, so now we're

0:06:35.656,0:06:39.865
interested in the distance between[br]probability of Wb and the probability of

0:06:39.865,0:06:44.730
Rb. Okay so we'll prove the claim in a[br]second. Let me just state the claim. The

0:06:44.730,0:06:49.938
claim says that there exists in adversary[br]B. Such that the difference of these two

0:06:49.938,0:06:55.081
probabilities is basically the advantage[br]of B against the generator G and this is

0:06:55.081,0:06:59.833
for both b's. Okay? So given these two[br]claims, like the theorem is done because

0:06:59.833,0:07:04.771
basically what do we know. We know this[br]distance is less than the advantage of B

0:07:04.771,0:07:09.523
against G. That's from claim two and[br]similarly, this distance actually is even

0:07:09.523,0:07:14.401
equal to, I'm not gonna say[br]less but is equal to the advantage. Of B

0:07:14.401,0:07:19.455
against G, and as a result you can see[br]that the distance between W0 and W1

0:07:19.455,0:07:24.446
is basically almost twice the[br]advantage of B against G. That's basically

0:07:24.446,0:07:29.375
the thing that we are trying to prove.[br]Okay the only thing that remains is just

0:07:29.375,0:07:34.304
proving this claim two and if you think[br]about what claim two says, it basically

0:07:34.304,0:07:39.170
captures the question of what happens in[br]experiment zero what happens when we

0:07:39.170,0:07:43.530
replace the pseudo random pad GK, by[br]truly random pad R. Here in

0:07:43.530,0:07:48.910
experiment zero say we're using the pseudo[br]random pad and here in experiment zero we

0:07:48.910,0:07:53.593
are using a Truly random pad and we are[br]asking can the adversary tell the

0:07:53.593,0:07:58.972
difference between these two and we wanna[br]argue that he cannot because the generator

0:07:58.972,0:08:03.845
is secure. Okay so here's what we are[br]gonna do. So let's prove claim two. So we

0:08:03.845,0:08:08.728
are gonna argue that in fact there is a[br]PRG adversary B that has exactly the

0:08:08.728,0:08:13.764
difference of the two probabilities as[br]it's advantage. Okay and since the point

0:08:13.764,0:08:18.319
is since this is negligible this is[br]negligible. And that's basically what we

0:08:18.319,0:08:22.323
wanted to prove. Okay, so let's look at[br]the statistical test b. So, what, our

0:08:22.323,0:08:26.514
statistical test b is gonna use adversary[br]A in his belly, so we get to build

0:08:26.514,0:08:31.091
statistical test b however we want. As we[br]said, it's gonna use adversary A inside of

0:08:31.091,0:08:35.558
it, for its operation, and it's a regular[br]statistical test, so it takes an n-bit

0:08:35.558,0:08:39.694
string as inputs, and it's supposed to[br]output, you know, random or non-random,

0:08:39.694,0:08:43.995
zero or one. Okay, so let's see. So it's,[br]first thing it's gonna do, is it's gonna

0:08:43.995,0:08:48.407
run adversary A, and adversary A is gonna[br]output two messages, M0 and M1. And then,

0:08:48.407,0:08:54.053
what adversary b's gonna do, is basically[br]gonna respond. With M0 XOR or the string that

0:08:54.053,0:08:59.942
it was given as inputs. Alright? That's[br]the statistical lesson, then. Whenever A

0:08:59.942,0:09:05.418
outputs, it's gonna output, its output.[br]And now let's look at its advantage. So

0:09:05.418,0:09:10.477
what can we say about the advantage of[br]this statistical test against the

0:09:10.477,0:09:15.606
generator? Well, so by definition, it's[br]the probability that, if you choose a

0:09:15.606,0:09:20.527
truly random string. So here are 01 to the N, so probability

0:09:20.527,0:09:25.587
that R, that B outputs 1 minus the[br]probability, is that when we choose a

0:09:25.587,0:09:32.603
pseudo random string, B outputs 1, okay?[br]Okay, but let's think about what this is.

0:09:32.603,0:09:37.398
What can you tell me about the first[br]expressions? What can you tell me about

0:09:37.398,0:09:42.256
this expression over here? Well, by the[br]definition that's exactly if you think

0:09:42.256,0:09:47.366
about what's going on here, that's this is[br]exactly the probability R0 right?

0:09:47.366,0:09:52.729
Because this game that we are playing with[br]the adversary here is basically he helped

0:09:52.729,0:09:58.028
us M0 and M1 right here he helped add M0 and m1 and he got the encryption

0:09:58.028,0:10:03.919
of M0 under truly one time pad. Okay,[br]so this is basically a [inaudible]. Here

0:10:03.919,0:10:10.214
let me write this a little better. That's[br]the basic level probability of R0.

0:10:10.660,0:10:15.467
Now, what can we say about the next[br]expression, well what can we say about

0:10:15.467,0:10:19.100
when B is given a pseudo random[br]string Y as input.

0:10:19.100,0:10:23.493
Well in that case, this is exactly experiment zero and[br]true stream cipher game

0:10:23.493,0:10:29.999
because now we're computing M XOR M0, XOR GK. This is[br]exactly W0.

0:10:29.999,0:10:33.015
Okay, that's exactly what we have to prove. So it's kind of a trivial proof.

0:10:33.015,0:10:39.563
Okay, so that completes the proof of claim two. And again, just to[br]make sure this is all clear, once we have

0:10:39.563,0:10:43.799
claim two, we know that W0 must be close[br]to W1, and that's the theorem.

0:10:43.814,0:10:50.383
That's what we have to prove. Okay, so now we've[br]established that a stream cypher is in

0:10:50.383,0:10:53.880
fact symmantically secure, assuming that[br]the PRG is secure.