[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.13,Default,,0000,0000,0000,,So now that we understand what a secure\NPRG is, and we understand what semantic
Dialogue: 0,0:00:04.13,0:00:08.42,Default,,0000,0000,0000,,security means, we can actually argue that\Na stream cipher with a secure PRG is, in
Dialogue: 0,0:00:08.42,0:00:12.56,Default,,0000,0000,0000,,fact, a semantically secure. So that's our\Ngoal for this, segment. It's a fairly
Dialogue: 0,0:00:12.56,0:00:16.75,Default,,0000,0000,0000,,straightforward proof, and we'll see how\Nit goes. So the theory we wanna prove is
Dialogue: 0,0:00:16.75,0:00:20.93,Default,,0000,0000,0000,,that, basically, given a generator G that\Nhappens to be a secured, psedo-random
Dialogue: 0,0:00:20.93,0:00:24.80,Default,,0000,0000,0000,,generator. In fact, the stream cipher\Nthat's derived from this generator is
Dialogue: 0,0:00:24.80,0:00:28.92,Default,,0000,0000,0000,,going to be semantically secure. Okay and\NI want to emphasize. That there was no
Dialogue: 0,0:00:28.92,0:00:33.08,Default,,0000,0000,0000,,hope of proving a theorem like this for\Nperfect secrecy. For Shannons concept of
Dialogue: 0,0:00:33.08,0:00:37.19,Default,,0000,0000,0000,,perfect secrecy. Because we know that a\Nstream cipher can not be perfectly
Dialogue: 0,0:00:37.19,0:00:41.26,Default,,0000,0000,0000,,secure because it has short keys. And\Nperfect secrecy requires the keys to be as
Dialogue: 0,0:00:41.26,0:00:45.32,Default,,0000,0000,0000,,long as the message. So this is really\Nkind of the first example the we see where
Dialogue: 0,0:00:45.32,0:00:49.23,Default,,0000,0000,0000,,we're able to prove that a cipher with\Nshort keys has security. The concept of
Dialogue: 0,0:00:49.23,0:00:53.24,Default,,0000,0000,0000,,security is semantic security. And this\Nactually validates that, really, this is a
Dialogue: 0,0:00:53.24,0:00:56.94,Default,,0000,0000,0000,,very useful concept. And in fact, you\Nknow, we'll be using semantic security
Dialogue: 0,0:00:56.94,0:01:00.75,Default,,0000,0000,0000,,many, many times throughout the course.\NOkay, so how do we prove a theory like
Dialogue: 0,0:01:00.75,0:01:04.26,Default,,0000,0000,0000,,this? What we're actually gonna be doing,\Nis we're gonna be proving the
Dialogue: 0,0:01:04.26,0:01:08.26,Default,,0000,0000,0000,,contrapositive. What we're gonna show is\Nthe following. So we're gonna prove this
Dialogue: 0,0:01:08.26,0:01:12.82,Default,,0000,0000,0000,,statement down here, but let me parse it\Nfor you. Suppose. You give me a semantic
Dialogue: 0,0:01:12.82,0:01:18.34,Default,,0000,0000,0000,,security adversary A. What we'll do is\Nwe'll build PRG adversary B to satisfy
Dialogue: 0,0:01:18.34,0:01:23.69,Default,,0000,0000,0000,,this inequality here. Now why is this\Ninequality useful? Basically what do we
Dialogue: 0,0:01:23.69,0:01:28.88,Default,,0000,0000,0000,,know? We know that if B is an efficient\Nadversary. Then we know that since G is a
Dialogue: 0,0:01:28.88,0:01:33.05,Default,,0000,0000,0000,,secure generator, we know that this\Nadvantage is negligible, right? A secure
Dialogue: 0,0:01:33.05,0:01:37.51,Default,,0000,0000,0000,,generator has a negligible advantage\Nagainst any efficient statistical test. So
Dialogue: 0,0:01:37.51,0:01:42.02,Default,,0000,0000,0000,,the right hand side, basically, is gonna\Nbe negligible. But because the right hand
Dialogue: 0,0:01:42.02,0:01:46.02,Default,,0000,0000,0000,,side is negligible, we can deduce that the\Nleft hand side is negligible.
Dialogue: 0,0:01:46.02,0:01:50.77,Default,,0000,0000,0000,,And therefore, the adversary that you looked\Nat actually has negligible advantage in
Dialogue: 0,0:01:50.77,0:01:54.54,Default,,0000,0000,0000,,attacking the stream cipher E. Okay. So\Nthis is how this, this will work.
Dialogue: 0,0:01:54.54,0:01:58.49,Default,,0000,0000,0000,,Basically all we have to do is given an\Nadversary A we're going to build an
Dialogue: 0,0:01:58.49,0:02:02.59,Default,,0000,0000,0000,,adversary B. We know that B has negligible\Nadvantage against generator but that
Dialogue: 0,0:02:02.59,0:02:06.04,Default,,0000,0000,0000,,implies that A has negligible advantage\Nagainst the stream cipher.
Dialogue: 0,0:02:06.08,0:02:10.99,Default,,0000,0000,0000,,So let's do that. So all we have to do again\Nis given A, we have to build B.
Dialogue: 0,0:02:10.99,0:02:15.18,Default,,0000,0000,0000,,So let A be a semantic security adversary against\Nthe stream cipher. So let me remind you
Dialogue: 0,0:02:15.18,0:02:19.32,Default,,0000,0000,0000,,what that means. Basically, there's a\Nchallenger. The challenger starts off by
Dialogue: 0,0:02:19.32,0:02:23.51,Default,,0000,0000,0000,,choosing the key K. And then the adversary\Nis gonna output two messages, two equal
Dialogue: 0,0:02:23.51,0:02:27.38,Default,,0000,0000,0000,,length messages. And he's gonna receive\Nthe encryption of M0 or M1
Dialogue: 0,0:02:27.38,0:02:31.23,Default,,0000,0000,0000,,and outputs B1. Okay, that's\Nwhat a semantic security adversary is
Dialogue: 0,0:02:31.23,0:02:34.93,Default,,0000,0000,0000,,going to do. So now we're going to start\Nplaying games with this adversary. And
Dialogue: 0,0:02:34.93,0:02:38.50,Default,,0000,0000,0000,,that's how we're going to prove our lemma. Alright, so the first thing
Dialogue: 0,0:02:38.50,0:02:42.54,Default,,0000,0000,0000,,we're going to do is we're going to make\Nthe challenger. Also choose a random R.
Dialogue: 0,0:02:42.54,0:02:47.50,Default,,0000,0000,0000,,Okay, a random string R. So, well you know\Nthe adversary doesn't really care what the
Dialogue: 0,0:02:47.50,0:02:52.40,Default,,0000,0000,0000,,challenger does internally. The challenger\Nnever uses R, so this doesn't affect the
Dialogue: 0,0:02:52.40,0:02:56.36,Default,,0000,0000,0000,,adversary's advantage at all. The\Nadversary just doesn't care that the
Dialogue: 0,0:02:56.36,0:03:00.71,Default,,0000,0000,0000,,challenger also picks R. But now comes the\Ntrick. What we're going to do is we're
Dialogue: 0,0:03:00.71,0:03:05.04,Default,,0000,0000,0000,,going to, instead of encrypting using GK.\NWe're going to encrypt using R. You can
Dialogue: 0,0:03:05.04,0:03:09.99,Default,,0000,0000,0000,,see basically what we're doing\Nhere. Essentially we're changing the
Dialogue: 0,0:03:09.99,0:03:14.22,Default,,0000,0000,0000,,challenger so now the challenge\Ncipher text is encrypted using a
Dialogue: 0,0:03:14.22,0:03:19.01,Default,,0000,0000,0000,,truly random pad. As opposed to just pseudo\Nrandom pad GK. Okay. Now, the property of
Dialogue: 0,0:03:19.01,0:03:23.64,Default,,0000,0000,0000,,the pseudo-random generator is that its\Noutput is indistinguishable from truly
Dialogue: 0,0:03:23.64,0:03:28.27,Default,,0000,0000,0000,,random. So, because the PRG is secure, the\Nadversary can't tell that we made this
Dialogue: 0,0:03:28.27,0:03:33.08,Default,,0000,0000,0000,,change. The adversary can't tell that we\Nswitched from a pseudo-random string to a
Dialogue: 0,0:03:33.08,0:03:37.42,Default,,0000,0000,0000,,truly random string. Again, because the generator is secure. Well, but now look at
Dialogue: 0,0:03:37.42,0:03:41.76,Default,,0000,0000,0000,,the game that we ended up with. So the\Nadversary's advantage couldn't have
Dialogue: 0,0:03:41.76,0:03:46.63,Default,,0000,0000,0000,,changed by much, because he can't tell the\Ndifference. But now look at the game that
Dialogue: 0,0:03:46.63,0:03:51.07,Default,,0000,0000,0000,,we ended up with. Now this game is truly a\None time pad game. This a semantic
Dialogue: 0,0:03:51.07,0:03:55.80,Default,,0000,0000,0000,,security game against the one time pad.\NBecause now the adversary is getting a one
Dialogue: 0,0:03:55.80,0:04:00.24,Default,,0000,0000,0000,,time pad encryption of M0 or M1 But in the\None time pad we know that the adversaries
Dialogue: 0,0:04:00.24,0:04:04.05,Default,,0000,0000,0000,,advantage is zero, because you can't beat\Nthe one time pad. The one time pad is
Dialogue: 0,0:04:04.05,0:04:08.16,Default,,0000,0000,0000,,secure Unconditionally secure. And as a\Nresult, because of this. Essentially
Dialogue: 0,0:04:08.16,0:04:12.67,Default,,0000,0000,0000,,because the adversary couldn't have told\Nthe difference when
Dialogue: 0,0:04:12.67,0:04:17.01,Default,,0000,0000,0000,,we moved from pseudo random to random. But he couldn't win the\Nrandom game. That also means that he
Dialogue: 0,0:04:17.01,0:04:21.41,Default,,0000,0000,0000,,couldn't win the sudo random game. And as\Na result, the stream cipher, the original
Dialogue: 0,0:04:21.41,0:04:25.63,Default,,0000,0000,0000,,stream cipher must be secure. So that's\Nthe intuition for how the proof is gonna go.
Dialogue: 0,0:04:25.63,0:04:29.59,Default,,0000,0000,0000,,But I wanna do it rigorously once.\NFrom now on, we're just gonna argue by
Dialogue: 0,0:04:29.59,0:04:33.98,Default,,0000,0000,0000,,playing games with our challenger. And, we\Nwon't be doing things as formal as I'm
Dialogue: 0,0:04:33.98,0:04:38.30,Default,,0000,0000,0000,,gonna do next. But I wanna do formally and\Nprecisely once, just so that you see how
Dialogue: 0,0:04:38.30,0:04:42.63,Default,,0000,0000,0000,,these proofs actually work. Okay, so I'm\Ngonna have to introduce some notation. And
Dialogue: 0,0:04:42.63,0:04:47.75,Default,,0000,0000,0000,,I'll do the usual notation, basically. If\Nthe original semantics are here at the
Dialogue: 0,0:04:47.75,0:04:52.94,Default,,0000,0000,0000,,beginning, when we're actually using a\Npseudo-random pad, I'm gonna use W0 and W1
Dialogue: 0,0:04:52.94,0:04:58.06,Default,,0000,0000,0000,,to denote the event that the adversary\Noutputs one, when it gets the encryption
Dialogue: 0,0:04:58.06,0:05:02.86,Default,,0000,0000,0000,,of M0, or gets the encryption of M1,\Nrespectively. Okay? So W0 corresponds to
Dialogue: 0,0:05:02.86,0:05:07.72,Default,,0000,0000,0000,,outputting 1 when receiving the\Nencryption of M0. And W1 corresponds
Dialogue: 0,0:05:07.72,0:05:13.14,Default,,0000,0000,0000,,to outputting 1 when receiving the encryption of M1. So that's the standard
Dialogue: 0,0:05:13.14,0:05:19.61,Default,,0000,0000,0000,,definition of semantic security. Now once\Nwe flip to the random pad. I'm gonna use
Dialogue: 0,0:05:19.61,0:05:24.50,Default,,0000,0000,0000,,R0 and R1 to denote the event that the\Nadversary outputs 1 when receiving the
Dialogue: 0,0:05:24.50,0:05:29.12,Default,,0000,0000,0000,,one-type pad encryption of M0 or the\None-time pad encryption of M1. So we have
Dialogue: 0,0:05:29.12,0:05:33.57,Default,,0000,0000,0000,,four events, W0, W1 from the original\Nsemmantics security game, and R0 and R1
Dialogue: 0,0:05:33.57,0:05:38.36,Default,,0000,0000,0000,,from the semmantics security game once we\Nswitch over to the one-time pad. So now
Dialogue: 0,0:05:38.36,0:05:42.98,Default,,0000,0000,0000,,let's look at relations between these\Nvariables. So first of all, R0 and R1 are
Dialogue: 0,0:05:42.98,0:05:47.43,Default,,0000,0000,0000,,basically events from a semmantics\Nsecurity game against a one-time pad. So
Dialogue: 0,0:05:47.43,0:05:51.93,Default,,0000,0000,0000,,the difference between these probabilities\Nis that, as we said, basically the
Dialogue: 0,0:05:51.93,0:05:56.90,Default,,0000,0000,0000,,advantage of algorithm A, of adversary A,\Nagainst the one-time pad. Which we know is
Dialogue: 0,0:05:56.90,0:06:01.23,Default,,0000,0000,0000,,zero. Okay, so that's great. So that\Nbasically means that probability of, of R0
Dialogue: 0,0:06:01.23,0:06:05.66,Default,,0000,0000,0000,,is equal to the probability of R1. So now,\Nlet's put these events on a line, on a
Dialogue: 0,0:06:05.66,0:06:10.26,Default,,0000,0000,0000,,line segment between zero and one. So here\Nare the events. W0 and W1 are the events
Dialogue: 0,0:06:10.26,0:06:14.50,Default,,0000,0000,0000,,we're interested in. We wanna show that\Nthese two are close. Okay. And the way
Dialogue: 0,0:06:14.50,0:06:18.49,Default,,0000,0000,0000,,we're going to do it is basically by\Nshowing, oh and I should say, here is
Dialogue: 0,0:06:18.49,0:06:22.75,Default,,0000,0000,0000,,probability R0 and R1, it says\Nthey're both same, I just put them in the
Dialogue: 0,0:06:22.75,0:06:27.24,Default,,0000,0000,0000,,same place. What we're gonna do is we're\Ngonna show that both W0 and W1 are
Dialogue: 0,0:06:27.24,0:06:31.72,Default,,0000,0000,0000,,actually close to the probability of RB\Nand as a result they must be close to one
Dialogue: 0,0:06:31.72,0:06:35.66,Default,,0000,0000,0000,,another. Okay, so the way we do that is\Nusing a second claim, so now we're
Dialogue: 0,0:06:35.66,0:06:39.86,Default,,0000,0000,0000,,interested in the distance between\Nprobability of Wb and the probability of
Dialogue: 0,0:06:39.86,0:06:44.73,Default,,0000,0000,0000,,Rb. Okay so we'll prove the claim in a\Nsecond. Let me just state the claim. The
Dialogue: 0,0:06:44.73,0:06:49.94,Default,,0000,0000,0000,,claim says that there exists in adversary\NB. Such that the difference of these two
Dialogue: 0,0:06:49.94,0:06:55.08,Default,,0000,0000,0000,,probabilities is basically the advantage\Nof B against the generator G and this is
Dialogue: 0,0:06:55.08,0:06:59.83,Default,,0000,0000,0000,,for both b's. Okay? So given these two\Nclaims, like the theorem is done because
Dialogue: 0,0:06:59.83,0:07:04.77,Default,,0000,0000,0000,,basically what do we know. We know this\Ndistance is less than the advantage of B
Dialogue: 0,0:07:04.77,0:07:09.52,Default,,0000,0000,0000,,against G. That's from claim two and\Nsimilarly, this distance actually is even
Dialogue: 0,0:07:09.52,0:07:14.40,Default,,0000,0000,0000,,equal to, I'm not gonna say\Nless but is equal to the advantage. Of B
Dialogue: 0,0:07:14.40,0:07:19.46,Default,,0000,0000,0000,,against G, and as a result you can see\Nthat the distance between W0 and W1
Dialogue: 0,0:07:19.46,0:07:24.45,Default,,0000,0000,0000,,is basically almost twice the\Nadvantage of B against G. That's basically
Dialogue: 0,0:07:24.45,0:07:29.38,Default,,0000,0000,0000,,the thing that we are trying to prove.\NOkay the only thing that remains is just
Dialogue: 0,0:07:29.38,0:07:34.30,Default,,0000,0000,0000,,proving this claim two and if you think\Nabout what claim two says, it basically
Dialogue: 0,0:07:34.30,0:07:39.17,Default,,0000,0000,0000,,captures the question of what happens in\Nexperiment zero what happens when we
Dialogue: 0,0:07:39.17,0:07:43.53,Default,,0000,0000,0000,,replace the pseudo random pad GK, by\Ntruly random pad R. Here in
Dialogue: 0,0:07:43.53,0:07:48.91,Default,,0000,0000,0000,,experiment zero say we're using the pseudo\Nrandom pad and here in experiment zero we
Dialogue: 0,0:07:48.91,0:07:53.59,Default,,0000,0000,0000,,are using a Truly random pad and we are\Nasking can the adversary tell the
Dialogue: 0,0:07:53.59,0:07:58.97,Default,,0000,0000,0000,,difference between these two and we wanna\Nargue that he cannot because the generator
Dialogue: 0,0:07:58.97,0:08:03.84,Default,,0000,0000,0000,,is secure. Okay so here's what we are\Ngonna do. So let's prove claim two. So we
Dialogue: 0,0:08:03.84,0:08:08.73,Default,,0000,0000,0000,,are gonna argue that in fact there is a\NPRG adversary B that has exactly the
Dialogue: 0,0:08:08.73,0:08:13.76,Default,,0000,0000,0000,,difference of the two probabilities as\Nit's advantage. Okay and since the point
Dialogue: 0,0:08:13.76,0:08:18.32,Default,,0000,0000,0000,,is since this is negligible this is\Nnegligible. And that's basically what we
Dialogue: 0,0:08:18.32,0:08:22.32,Default,,0000,0000,0000,,wanted to prove. Okay, so let's look at\Nthe statistical test b. So, what, our
Dialogue: 0,0:08:22.32,0:08:26.51,Default,,0000,0000,0000,,statistical test b is gonna use adversary\NA in his belly, so we get to build
Dialogue: 0,0:08:26.51,0:08:31.09,Default,,0000,0000,0000,,statistical test b however we want. As we\Nsaid, it's gonna use adversary A inside of
Dialogue: 0,0:08:31.09,0:08:35.56,Default,,0000,0000,0000,,it, for its operation, and it's a regular\Nstatistical test, so it takes an n-bit
Dialogue: 0,0:08:35.56,0:08:39.69,Default,,0000,0000,0000,,string as inputs, and it's supposed to\Noutput, you know, random or non-random,
Dialogue: 0,0:08:39.69,0:08:43.100,Default,,0000,0000,0000,,zero or one. Okay, so let's see. So it's,\Nfirst thing it's gonna do, is it's gonna
Dialogue: 0,0:08:43.100,0:08:48.41,Default,,0000,0000,0000,,run adversary A, and adversary A is gonna\Noutput two messages, M0 and M1. And then,
Dialogue: 0,0:08:48.41,0:08:54.05,Default,,0000,0000,0000,,what adversary b's gonna do, is basically\Ngonna respond. With M0 XOR or the string that
Dialogue: 0,0:08:54.05,0:08:59.94,Default,,0000,0000,0000,,it was given as inputs. Alright? That's\Nthe statistical lesson, then. Whenever A
Dialogue: 0,0:08:59.94,0:09:05.42,Default,,0000,0000,0000,,outputs, it's gonna output, its output.\NAnd now let's look at its advantage. So
Dialogue: 0,0:09:05.42,0:09:10.48,Default,,0000,0000,0000,,what can we say about the advantage of\Nthis statistical test against the
Dialogue: 0,0:09:10.48,0:09:15.61,Default,,0000,0000,0000,,generator? Well, so by definition, it's\Nthe probability that, if you choose a
Dialogue: 0,0:09:15.61,0:09:20.53,Default,,0000,0000,0000,,truly random string. So here are 01 to the N, so probability
Dialogue: 0,0:09:20.53,0:09:25.59,Default,,0000,0000,0000,,that R, that B outputs 1 minus the\Nprobability, is that when we choose a
Dialogue: 0,0:09:25.59,0:09:32.60,Default,,0000,0000,0000,,pseudo random string, B outputs 1, okay?\NOkay, but let's think about what this is.
Dialogue: 0,0:09:32.60,0:09:37.40,Default,,0000,0000,0000,,What can you tell me about the first\Nexpressions? What can you tell me about
Dialogue: 0,0:09:37.40,0:09:42.26,Default,,0000,0000,0000,,this expression over here? Well, by the\Ndefinition that's exactly if you think
Dialogue: 0,0:09:42.26,0:09:47.37,Default,,0000,0000,0000,,about what's going on here, that's this is\Nexactly the probability R0 right?
Dialogue: 0,0:09:47.37,0:09:52.73,Default,,0000,0000,0000,,Because this game that we are playing with\Nthe adversary here is basically he helped
Dialogue: 0,0:09:52.73,0:09:58.03,Default,,0000,0000,0000,,us M0 and M1 right here he helped add M0 and m1 and he got the encryption
Dialogue: 0,0:09:58.03,0:10:03.92,Default,,0000,0000,0000,,of M0 under truly one time pad. Okay,\Nso this is basically a [inaudible]. Here
Dialogue: 0,0:10:03.92,0:10:10.21,Default,,0000,0000,0000,,let me write this a little better. That's\Nthe basic level probability of R0.
Dialogue: 0,0:10:10.66,0:10:15.47,Default,,0000,0000,0000,,Now, what can we say about the next\Nexpression, well what can we say about
Dialogue: 0,0:10:15.47,0:10:19.10,Default,,0000,0000,0000,,when B is given a pseudo random\Nstring Y as input.
Dialogue: 0,0:10:19.10,0:10:23.49,Default,,0000,0000,0000,,Well in that case, this is exactly experiment zero and\Ntrue stream cipher game
Dialogue: 0,0:10:23.49,0:10:29.100,Default,,0000,0000,0000,,because now we're computing M XOR M0, XOR GK. This is\Nexactly W0.
Dialogue: 0,0:10:29.100,0:10:33.02,Default,,0000,0000,0000,,Okay, that's exactly what we have to prove. So it's kind of a trivial proof.
Dialogue: 0,0:10:33.02,0:10:39.56,Default,,0000,0000,0000,,Okay, so that completes the proof of claim two. And again, just to\Nmake sure this is all clear, once we have
Dialogue: 0,0:10:39.56,0:10:43.80,Default,,0000,0000,0000,,claim two, we know that W0 must be close\Nto W1, and that's the theorem.
Dialogue: 0,0:10:43.81,0:10:50.38,Default,,0000,0000,0000,,That's what we have to prove. Okay, so now we've\Nestablished that a stream cypher is in
Dialogue: 0,0:10:50.38,0:10:53.88,Default,,0000,0000,0000,,fact symmantically secure, assuming that\Nthe PRG is secure.