[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.91,Default,,0000,0000,0000,,My goal for the next few segments is to\Nshow you that if we use a secure PRG We'll
Dialogue: 0,0:00:03.91,0:00:07.89,Default,,0000,0000,0000,,get a secure stream safer. The first thing\Nwe have to do is define is, what does it
Dialogue: 0,0:00:07.89,0:00:11.68,Default,,0000,0000,0000,,mean for a stream safer to be secure? So\Nwhenever we define security we always
Dialogue: 0,0:00:11.68,0:00:15.17,Default,,0000,0000,0000,,define it in terms of what can the\Nattacker do? And what is the attacker
Dialogue: 0,0:00:15.17,0:00:18.67,Default,,0000,0000,0000,,trying to do? In the context of\Nstream ciphers remember these are only used
Dialogue: 0,0:00:18.67,0:00:22.74,Default,,0000,0000,0000,,with a onetime key, and as a result the\Nmost the attacker is ever going to see is
Dialogue: 0,0:00:22.74,0:00:26.75,Default,,0000,0000,0000,,just one cypher text encrypted using the\Nkey that we're using. And so we're gonna
Dialogue: 0,0:00:26.75,0:00:30.77,Default,,0000,0000,0000,,limit the attackers? ability to basically\Nobtain just one cypher text. And in
Dialogue: 0,0:00:30.77,0:00:34.64,Default,,0000,0000,0000,,fact later on we're going to allow the\Nattacker to do much, much, much more, but
Dialogue: 0,0:00:34.64,0:00:38.46,Default,,0000,0000,0000,,for now we're just gonna give him one\Ncypher text. And we wanted to find,
Dialogue: 0,0:00:38.46,0:00:42.56,Default,,0000,0000,0000,,what does it mean for the cypher to\Nbe secure? So the first definition that
Dialogue: 0,0:00:42.56,0:00:46.89,Default,,0000,0000,0000,,comes to mind is basically to say, well\Nmaybe we wanna require that the attacker
Dialogue: 0,0:00:46.89,0:00:50.72,Default,,0000,0000,0000,,can't actually recover the secret key.\NOkay so given ciphertext you
Dialogue: 0,0:00:50.72,0:00:54.61,Default,,0000,0000,0000,,shouldn't be able to recover the secret\Nkey. But that's a terrible definition
Dialogue: 0,0:00:54.61,0:00:58.72,Default,,0000,0000,0000,,because think about the falling brilliant\Ncipher but the way we encrypt the
Dialogue: 0,0:00:58.72,0:01:02.86,Default,,0000,0000,0000,,message using a key K is basically\Nwe just output the message. Okay this
Dialogue: 0,0:01:02.86,0:01:07.43,Default,,0000,0000,0000,,is a brilliant cipher yeah of course it\Ndoesn't do anything given a message just
Dialogue: 0,0:01:07.43,0:01:12.00,Default,,0000,0000,0000,,output a message as the cipher text.\NThis is not a particularly good encryption
Dialogue: 0,0:01:12.00,0:01:16.03,Default,,0000,0000,0000,,scheme; however, given the cipher text,\Nmainly the message the poor attacker
Dialogue: 0,0:01:16.03,0:01:20.49,Default,,0000,0000,0000,,cannot recover the key because he doesn't\Nknow what the key is. And so as a result
Dialogue: 0,0:01:20.49,0:01:24.63,Default,,0000,0000,0000,,this cipher which clearly is insecure,\Nwould be considered secure under this
Dialogue: 0,0:01:24.79,0:01:28.64,Default,,0000,0000,0000,,requirement for security. So this\Ndefinition will be no good. Okay so it's
Dialogue: 0,0:01:28.64,0:01:32.32,Default,,0000,0000,0000,,recovering the secret key is the wrong way\Nto define security. So the next thing we
Dialogue: 0,0:01:32.32,0:01:35.100,Default,,0000,0000,0000,,can kinda attempt is basically just say,\Nwell maybe the attacker doesn't care about
Dialogue: 0,0:01:35.100,0:01:39.68,Default,,0000,0000,0000,,the secret key, what he really cares about\Nare the plain text. So maybe it should be
Dialogue: 0,0:01:39.68,0:01:43.52,Default,,0000,0000,0000,,hard for the attacker to recover the\Nentire plain text. But even that doesn't
Dialogue: 0,0:01:43.52,0:01:48.22,Default,,0000,0000,0000,,work because let's think about the\Nfollowing encryption scheme. So suppose
Dialogue: 0,0:01:48.22,0:01:53.44,Default,,0000,0000,0000,,what this encryption scheme does is it\Ntakes two messages, so I'm gonna use two
Dialogue: 0,0:01:53.44,0:01:58.01,Default,,0000,0000,0000,,lines to denote concatenation of two\Nmessages M0 line, line M1 means
Dialogue: 0,0:01:58.01,0:02:03.10,Default,,0000,0000,0000,,concatenate M0 and M1. And imagine\Nwhat the scheme does is really it outputs
Dialogue: 0,0:02:03.10,0:02:08.06,Default,,0000,0000,0000,,M0 in the clear and concatenate to\Nthat the encryption of M1. Perhaps even
Dialogue: 0,0:02:08.06,0:02:13.34,Default,,0000,0000,0000,,using the One Time Pad okay? And\Nso here the attacker is gonna be given one
Dialogue: 0,0:02:13.34,0:02:17.48,Default,,0000,0000,0000,,cipher text. And his goal would be to\Nrecover the entire plain texts. But the
Dialogue: 0,0:02:17.48,0:02:21.70,Default,,0000,0000,0000,,poor attacker can't do that because here\Nmaybe we've encrypted M1 using the One
Dialogue: 0,0:02:21.70,0:02:25.87,Default,,0000,0000,0000,,Time Pad so the attacker can't\Nactually recover M1 because we know the
Dialogue: 0,0:02:25.87,0:02:30.04,Default,,0000,0000,0000,,One Time Pad is secure given just\None cipher text. So this construction
Dialogue: 0,0:02:30.04,0:02:34.06,Default,,0000,0000,0000,,would satisfy the definition but\Nunfortunately clearly this is not a secure
Dialogue: 0,0:02:34.06,0:02:37.96,Default,,0000,0000,0000,,encryption scheme because we just leaked\Nhalf of the plain text. M0 is
Dialogue: 0,0:02:37.96,0:02:42.18,Default,,0000,0000,0000,,completely available to the attacker so\Neven though he can't recover all of the
Dialogue: 0,0:02:42.18,0:02:46.46,Default,,0000,0000,0000,,plain text he might be able to recover\Nmost of the plain text, and that's clearly
Dialogue: 0,0:02:46.46,0:02:50.66,Default,,0000,0000,0000,,unsecured. So of course we already know\Nthe solution to this and we talked about
Dialogue: 0,0:02:50.66,0:02:54.75,Default,,0000,0000,0000,,Shanon definition of security perfect\Nsecrecy where Shannon's idea was that in
Dialogue: 0,0:02:54.75,0:02:58.84,Default,,0000,0000,0000,,fact when the attacker intercepts a cipher\Ntext he should learn absolutely no
Dialogue: 0,0:02:58.84,0:03:02.82,Default,,0000,0000,0000,,information about the plain texts. He\Nshouldn't even learn one bit about the
Dialogue: 0,0:03:02.82,0:03:07.22,Default,,0000,0000,0000,,plain text or even he shouldn't learn, he\Nshouldn't even be able to predict a little
Dialogue: 0,0:03:07.22,0:03:11.20,Default,,0000,0000,0000,,bit about a bid of the plain text.\NAbsolutely no information about the plain text.
Dialogue: 0,0:03:11.20,0:03:14.93,Default,,0000,0000,0000,,So let's recall very briefly\NShannon's concept of perfect secrecy
Dialogue: 0,0:03:14.93,0:03:19.44,Default,,0000,0000,0000,,basically we said that you know given a\Ncipher We said the cipher has perfect
Dialogue: 0,0:03:19.44,0:03:25.07,Default,,0000,0000,0000,,secrecy if given two messages of the same\Nlength it so happens that the distribution
Dialogue: 0,0:03:25.07,0:03:30.17,Default,,0000,0000,0000,,of cipher texts. Yet if we pick a random\Nkey and we look into distribution of
Dialogue: 0,0:03:30.17,0:03:34.84,Default,,0000,0000,0000,,cipher texts we encrypt M0 we get\Nexactly the same distribution as when we
Dialogue: 0,0:03:34.84,0:03:39.26,Default,,0000,0000,0000,,encrypt M1. The intuition here was that if\Nthe advisory observes the cipher texts
Dialogue: 0,0:03:39.26,0:03:43.84,Default,,0000,0000,0000,,then he doesn't know whether it came from\Nthe distribution the result of encrypting
Dialogue: 0,0:03:43.84,0:03:48.20,Default,,0000,0000,0000,,M0 or it came from the distribution as\Nthe result of encrypting M1. And as a
Dialogue: 0,0:03:48.20,0:03:52.51,Default,,0000,0000,0000,,result he can't tell whether we encrypted\NM0 or M1. And that's true for all
Dialogue: 0,0:03:52.51,0:03:56.88,Default,,0000,0000,0000,,messages of the same length and as a\Nresult a poor attacker doesn't really know
Dialogue: 0,0:03:56.88,0:04:01.21,Default,,0000,0000,0000,,what message was encrypted. Of course we\Nalready said that this definition is too
Dialogue: 0,0:04:01.21,0:04:05.40,Default,,0000,0000,0000,,strong in the sense that it requires\Nreally long keys if cipher has short
Dialogue: 0,0:04:05.40,0:04:09.54,Default,,0000,0000,0000,,keys can't possibly satisfy this\Ndefinition in a particular stream ciphers
Dialogue: 0,0:04:09.54,0:04:14.33,Default,,0000,0000,0000,,can satisfy this definition. Okay so let's\Ntry to weaken the definition a little bit
Dialogue: 0,0:04:14.33,0:04:19.11,Default,,0000,0000,0000,,and let's think to the previous segment,\Nand we can say that instead of requiring
Dialogue: 0,0:04:19.11,0:04:23.84,Default,,0000,0000,0000,,the two distributions to be absolutely\Nidentical what we can require is, is that
Dialogue: 0,0:04:23.84,0:04:28.69,Default,,0000,0000,0000,,two distributions just be computationally\Nindistinguishable. In other words a poor,
Dialogue: 0,0:04:28.86,0:04:33.35,Default,,0000,0000,0000,,efficient attacker cannot distinguish the\Ntwo distributions even though the
Dialogue: 0,0:04:33.35,0:04:37.82,Default,,0000,0000,0000,,distributions might be very, very, very\Ndifferent. That just given a sample for
Dialogue: 0,0:04:37.82,0:04:42.58,Default,,0000,0000,0000,,one distribution and a sample for another\Ndistribution the attacker can't tell which
Dialogue: 0,0:04:42.58,0:04:47.12,Default,,0000,0000,0000,,distribution he was given a sample from.\NIt turns out this definition is actually
Dialogue: 0,0:04:47.12,0:04:51.72,Default,,0000,0000,0000,,almost right, but it's still a little too\Nstrong, that still cannot be satisfied, so
Dialogue: 0,0:04:51.72,0:04:56.20,Default,,0000,0000,0000,,we have to add one more constraint, and\Nthat is that instead of saying that this
Dialogue: 0,0:04:56.20,0:05:00.80,Default,,0000,0000,0000,,definition should have hold for all M0 and M1. It is to hold for only pairs M0 M1
Dialogue: 0,0:05:00.80,0:05:05.21,Default,,0000,0000,0000,,that the attackers could\Nactually exhibit. Okay so this actually
Dialogue: 0,0:05:05.21,0:05:10.04,Default,,0000,0000,0000,,leads us to the definition of semantics\Nsecurity. And so, again this is semantics
Dialogue: 0,0:05:10.04,0:05:15.05,Default,,0000,0000,0000,,security for one time key in other words\Nwhen the attacker is only given one cipher
Dialogue: 0,0:05:15.05,0:05:19.82,Default,,0000,0000,0000,,text. And so the way we define semantic\Nsecurity is by defining two experiments,
Dialogue: 0,0:05:19.82,0:05:24.56,Default,,0000,0000,0000,,okay we'll define experiment 0 and\Nexperiment 1. And more generally we will
Dialogue: 0,0:05:24.56,0:05:29.23,Default,,0000,0000,0000,,think of these as experiments parentheses\NB, where B can be zero or one. Okay so the
Dialogue: 0,0:05:29.23,0:05:32.89,Default,,0000,0000,0000,,way the experiment is defined is as\Nfollows, we have an adversary that's
Dialogue: 0,0:05:32.89,0:05:37.16,Default,,0000,0000,0000,,trying to break the system. An adversary\NA, that's kinda the analog of statistical
Dialogue: 0,0:05:37.16,0:05:41.28,Default,,0000,0000,0000,,tests in the world of pseudo random\Ngenerators. And then the challenger does
Dialogue: 0,0:05:41.28,0:05:45.09,Default,,0000,0000,0000,,the following, so really we have two\Nchallengers, but the challengers are so
Dialogue: 0,0:05:45.09,0:05:49.41,Default,,0000,0000,0000,,similar that we can just describe them as\Na single challenger that in one case takes
Dialogue: 0,0:05:49.41,0:05:53.63,Default,,0000,0000,0000,,his inputs bits set to zero, and the other\Ncase takes his inputs bits set to
Dialogue: 0,0:05:53.63,0:05:57.19,Default,,0000,0000,0000,,one. And let me show you what these\Nchallengers do. The first thing the
Dialogue: 0,0:05:57.19,0:06:01.35,Default,,0000,0000,0000,,challenger is gonna do is it's gonna pick\Na random key and then the adversary
Dialogue: 0,0:06:01.35,0:06:06.08,Default,,0000,0000,0000,,basically is going to output two messages\NM0 and M1. Okay so this is an explicit
Dialogue: 0,0:06:06.08,0:06:11.04,Default,,0000,0000,0000,,pair of messages that the attacker wants\Nto be challenged on and as usual we're not
Dialogue: 0,0:06:11.04,0:06:15.77,Default,,0000,0000,0000,,trying to hide the length of the messages,\Nwe require that the messages be equal
Dialogue: 0,0:06:15.77,0:06:21.64,Default,,0000,0000,0000,,length. And then the challenger basically\Nwill output either the encryption of M0
Dialogue: 0,0:06:21.64,0:06:25.89,Default,,0000,0000,0000,,or the encryption of M1, okay so in\Nexperiment 0 the challenger will output
Dialogue: 0,0:06:25.89,0:06:30.30,Default,,0000,0000,0000,,the encryption of M0. In experiment 1 the challenger will output the encryption
Dialogue: 0,0:06:30.30,0:06:34.38,Default,,0000,0000,0000,,of M1. Okay so that the difference between\Nthe two experiments. And then the
Dialogue: 0,0:06:34.38,0:06:38.80,Default,,0000,0000,0000,,adversary is trying to guess basically\Nwhether he was given the encryption of M0
Dialogue: 0,0:06:38.80,0:06:44.05,Default,,0000,0000,0000,,or given the encryption of M1. Okay so\Nhere's a little bit of notation let's
Dialogue: 0,0:06:44.05,0:06:50.26,Default,,0000,0000,0000,,define the events Wb to be the events that\Nan experiment B the adversary output one.
Dialogue: 0,0:06:50.26,0:06:55.08,Default,,0000,0000,0000,,Okay so that is just an event that\Nbasically in experiment zero W0 means that
Dialogue: 0,0:06:55.08,0:07:00.34,Default,,0000,0000,0000,,the adversary output one and in experiment\None W1 means the adversary output one. And
Dialogue: 0,0:07:00.34,0:07:05.29,Default,,0000,0000,0000,,now we can define the advantage of this\Nadversary, basically to say that this is
Dialogue: 0,0:07:05.29,0:07:10.42,Default,,0000,0000,0000,,called the semantics security advantage of\Nthe adversary A against the scheme E,
Dialogue: 0,0:07:10.42,0:07:15.50,Default,,0000,0000,0000,,to be the difference of the probability of\Nthese two events. In other words we are
Dialogue: 0,0:07:15.50,0:07:20.14,Default,,0000,0000,0000,,looking at whether the adversary behaves\Ndifferently when he was given the
Dialogue: 0,0:07:20.14,0:07:24.82,Default,,0000,0000,0000,,encryption of M0 from when he was given\Nthe encryption of M1. And I wanna make
Dialogue: 0,0:07:24.82,0:07:29.20,Default,,0000,0000,0000,,sure this is clear so I'm gonna say it one\Nmore time. So in experiment zero he was
Dialogue: 0,0:07:29.20,0:07:33.53,Default,,0000,0000,0000,,given the encryption of M0 and in\Nexperiment one he was given the encryption
Dialogue: 0,0:07:33.53,0:07:37.70,Default,,0000,0000,0000,,of M1. Now we're just interested in\Nwhether the adversary output 1 or not.
Dialogue: 0,0:07:37.70,0:07:42.36,Default,,0000,0000,0000,,... In these experiments. If in both\Nexperiments the adversary output 1 with
Dialogue: 0,0:07:42.36,0:07:47.01,Default,,0000,0000,0000,,the same probability that means the\Nadversary wasn't able to distinguish the
Dialogue: 0,0:07:47.01,0:07:51.55,Default,,0000,0000,0000,,two experiments. Experiments zero\Nbasically looks to the adversary the same
Dialogue: 0,0:07:51.55,0:07:56.21,Default,,0000,0000,0000,,as experiment one because in both cases\Nupload one with the same probability.
Dialogue: 0,0:07:56.21,0:08:01.29,Default,,0000,0000,0000,,However if the adversary is able to output\N1 in one experiment with significantly
Dialogue: 0,0:08:01.29,0:08:05.76,Default,,0000,0000,0000,,different probability than in the other\Nexperiment, then the adversary was
Dialogue: 0,0:08:05.76,0:08:10.27,Default,,0000,0000,0000,,actually able to distinguish the two\Nexperiments. Okay so... To say this more
Dialogue: 0,0:08:10.27,0:08:14.46,Default,,0000,0000,0000,,formally, essentially the advantage again\Nbecause it's the difference of two
Dialogue: 0,0:08:14.46,0:08:18.92,Default,,0000,0000,0000,,probabilities the advantage is a number\Nbetween zero and one. If the advantage is
Dialogue: 0,0:08:18.92,0:08:22.89,Default,,0000,0000,0000,,close to zero that means that the\Nadversary was not able to distinguish
Dialogue: 0,0:08:22.89,0:08:27.13,Default,,0000,0000,0000,,experiment zero from experiment one.\NHowever if the advantage is close to one,
Dialogue: 0,0:08:27.13,0:08:31.54,Default,,0000,0000,0000,,that means the adversary was very well\Nable to distinguish experiment zero from
Dialogue: 0,0:08:31.54,0:08:36.11,Default,,0000,0000,0000,,experiment one and that really means that\Nhe was able to distinguish an encryption
Dialogue: 0,0:08:36.11,0:08:40.30,Default,,0000,0000,0000,,of M0 from an encryption of M1, okay?So that's out definition. Actually
Dialogue: 0,0:08:40.30,0:08:44.06,Default,,0000,0000,0000,,that is just the definition of the\Nadvantage and the definition is just what
Dialogue: 0,0:08:44.06,0:08:47.71,Default,,0000,0000,0000,,you would expect basically we'll say that\Na symmetric encryption scheme is
Dialogue: 0,0:08:47.71,0:08:52.35,Default,,0000,0000,0000,,semantically secure if for all efficient\Nadversaries here I'll put these in quotes
Dialogue: 0,0:08:52.35,0:08:56.93,Default,,0000,0000,0000,,again, "For all efficient adversaries the\Nadvantage is negligible." In other words,
Dialogue: 0,0:08:56.98,0:09:01.81,Default,,0000,0000,0000,,no efficient adversary can distinguish the\Nencryption of M0 from the encryption
Dialogue: 0,0:09:01.81,0:09:06.10,Default,,0000,0000,0000,,of M1 and basically this is what it\Nsays repeatedly that for these two
Dialogue: 0,0:09:06.10,0:09:10.76,Default,,0000,0000,0000,,messages that the adversary was able to\Nexhibit he wasn't able to distinguish
Dialogue: 0,0:09:10.76,0:09:15.06,Default,,0000,0000,0000,,these two distributions. Now I want to\Nshow you this, this is actually a very
Dialogue: 0,0:09:15.06,0:09:19.60,Default,,0000,0000,0000,,elegant definition. It might not seem so\Nright away, but I want to show you some
Dialogue: 0,0:09:19.60,0:09:24.41,Default,,0000,0000,0000,,implications of this definition and you'll\Nsee exactly why the definition is the way
Dialogue: 0,0:09:24.41,0:09:28.60,Default,,0000,0000,0000,,it is. Okay so let's look at some\Nexamples. So the first example is suppose
Dialogue: 0,0:09:28.60,0:09:33.19,Default,,0000,0000,0000,,we have a broken encryption scheme, in\Nother words suppose we have an adversary A
Dialogue: 0,0:09:33.19,0:09:38.28,Default,,0000,0000,0000,,that somehow given the cipher text he is\Nalways able to deduce the least
Dialogue: 0,0:09:38.28,0:09:44.15,Default,,0000,0000,0000,,significant bit of the plain text. Okay so\Ngiven the encryption of M0, this adversary
Dialogue: 0,0:09:44.15,0:09:48.80,Default,,0000,0000,0000,,is able to deduce the least significant\Nbit of M0. So that is a terrible
Dialogue: 0,0:09:48.80,0:09:52.91,Default,,0000,0000,0000,,encryption scheme because it basically\Nleaks the least significant bit of the
Dialogue: 0,0:09:52.91,0:09:57.13,Default,,0000,0000,0000,,plain text just given the cipher text. So\NI want to show you that this scheme is
Dialogue: 0,0:09:57.13,0:10:01.61,Default,,0000,0000,0000,,therefore semantically secure so that kind\Nof shows that if a system is semantically
Dialogue: 0,0:10:01.61,0:10:05.93,Default,,0000,0000,0000,,secure than there is no attacker of this\Ntype. Okay so let's see why is the system
Dialogue: 0,0:10:05.93,0:10:10.25,Default,,0000,0000,0000,,not semantically secure well so what we\Nare gonna do is we're gonna basically use
Dialogue: 0,0:10:10.25,0:10:14.37,Default,,0000,0000,0000,,our adversary who is able to learn our\Nmost insignificant bits, we're going to
Dialogue: 0,0:10:14.37,0:10:18.37,Default,,0000,0000,0000,,use him to break semantic security so\Nwe're going to use him to distinguish
Dialogue: 0,0:10:18.37,0:10:22.76,Default,,0000,0000,0000,,experiment zero from experiment one Okay\Nso here is what we are going to do. We are
Dialogue: 0,0:10:22.76,0:10:26.99,Default,,0000,0000,0000,,algorithm B, we are going to be algorithm\NB and this algorithm B is going to use
Dialogue: 0,0:10:26.99,0:10:31.16,Default,,0000,0000,0000,,algorithm A in its belly. Okay so the\Nfirst thing that is going to happen is of
Dialogue: 0,0:10:31.16,0:10:35.61,Default,,0000,0000,0000,,course the challenger is going to choose a\Nrandom key. The first thing that is going
Dialogue: 0,0:10:35.61,0:10:39.76,Default,,0000,0000,0000,,to happen is that we need to output two\Nmessages. The messages that we are going
Dialogue: 0,0:10:39.76,0:10:43.49,Default,,0000,0000,0000,,to output basically are going to have\Ndifferently significant bits. So one
Dialogue: 0,0:10:43.49,0:10:47.73,Default,,0000,0000,0000,,message is going to end with zero and one\Nmessage is going to end with one. Now what
Dialogue: 0,0:10:47.73,0:10:51.20,Default,,0000,0000,0000,,is the challenger going to do? The\Nchallenger is going to give us the
Dialogue: 0,0:10:51.20,0:10:55.24,Default,,0000,0000,0000,,encryption of either M0 or M1,\Ndepending on whether in experiment 0 or
Dialogue: 0,0:10:55.24,0:10:59.12,Default,,0000,0000,0000,,in experiment 1. And then we just\Nforward this cipher text to the adversary
Dialogue: 0,0:10:59.12,0:11:03.87,Default,,0000,0000,0000,,okay so the adversary A. Now what is the\Nproperty of adversary A? Given the cipher
Dialogue: 0,0:11:03.87,0:11:08.50,Default,,0000,0000,0000,,text, adversary A can tell us what the\Nleast significant bits of the plain text is.
Dialogue: 0,0:11:08.50,0:11:13.37,Default,,0000,0000,0000,,In other words the adversary is going\Nto output the least significant bits of M0 or M1
Dialogue: 0,0:11:13.37,0:11:17.89,Default,,0000,0000,0000,,but low and behold that's\Nbasically the bit B. And then we're just
Dialogue: 0,0:11:17.89,0:11:23.05,Default,,0000,0000,0000,,going to output that as our guest so let?s\Ncall this thing B prime Okay so now this
Dialogue: 0,0:11:23.05,0:11:28.38,Default,,0000,0000,0000,,describes the semantic security adversary.\NAnd now you tell me what is the semantic
Dialogue: 0,0:11:28.38,0:11:33.59,Default,,0000,0000,0000,,security advantage of this adversary? Well\Nso let's see. In experiment zero, what is
Dialogue: 0,0:11:33.59,0:11:38.78,Default,,0000,0000,0000,,the probability that adversary B outputs\None? Well in experiment zero it is always
Dialogue: 0,0:11:38.78,0:11:43.70,Default,,0000,0000,0000,,given the encryption of M zero and\Ntherefore adversary A is always output the
Dialogue: 0,0:11:43.70,0:11:48.63,Default,,0000,0000,0000,,least significant bit of M zero which\Nalways happens to be zero. In experiment
Dialogue: 0,0:11:48.63,0:11:53.12,Default,,0000,0000,0000,,zero, B always outputs zero. So the\Nprobability that outputs one is zero.
Dialogue: 0,0:11:53.12,0:11:57.83,Default,,0000,0000,0000,,However in experiment one, we're given the\Nencryption of M1. So how likely is
Dialogue: 0,0:11:57.83,0:12:02.78,Default,,0000,0000,0000,,adversary B to output one in experiment\None well it always outputs one, again by
Dialogue: 0,0:12:02.78,0:12:07.43,Default,,0000,0000,0000,,the properties of algorithm A and\Ntherefore the advantage basically is one.
Dialogue: 0,0:12:07.43,0:12:12.38,Default,,0000,0000,0000,,So this is a huge advantage, it's as big\Nas it's gonna get. Which means that this
Dialogue: 0,0:12:12.38,0:12:17.09,Default,,0000,0000,0000,,adversary completely broke the system.\NOkay so we consider, so under semantic
Dialogue: 0,0:12:17.09,0:12:22.30,Default,,0000,0000,0000,,security basically just deducing the least\Nsignificant bits is enough to completely
Dialogue: 0,0:12:22.30,0:12:27.19,Default,,0000,0000,0000,,break the system under a semantic security\Ndefinition. Okay, now the interesting
Dialogue: 0,0:12:27.19,0:12:32.39,Default,,0000,0000,0000,,thing here of course is that this is not\Njust about the least significant bit, in
Dialogue: 0,0:12:32.39,0:12:37.12,Default,,0000,0000,0000,,fact of the message for\Nexample the most significant bit, you know
Dialogue: 0,0:12:37.12,0:12:42.04,Default,,0000,0000,0000,,bit number seven Maybe the XOR of all the bits in the message and so on
Dialogue: 0,0:12:42.04,0:12:46.55,Default,,0000,0000,0000,,and so forth any kind of information, any\Nbit about the plain text they can be
Dialogue: 0,0:12:46.55,0:12:50.81,Default,,0000,0000,0000,,learned basically would mean that the\Nsystem is not semantically secure. So
Dialogue: 0,0:12:50.81,0:12:55.53,Default,,0000,0000,0000,,basically all the adversary would have to\Ndo would be to come up with two messages
Dialogue: 0,0:12:55.53,0:13:00.25,Default,,0000,0000,0000,,M0 and M1 such that under one thing that\Nthey learned it's the value zero and then
Dialogue: 0,0:13:00.25,0:13:04.63,Default,,0000,0000,0000,,the other thing, the value, is one. So for\Nexample if A was able to learn the XOR
Dialogue: 0,0:13:04.63,0:13:08.78,Default,,0000,0000,0000,,bits of the message then M0\Nand M1 would just have different
Dialogue: 0,0:13:08.78,0:13:13.26,Default,,0000,0000,0000,,XOR for all the bits of their\Nmessages and then this adversary A would
Dialogue: 0,0:13:13.26,0:13:18.17,Default,,0000,0000,0000,,also be sufficient to break semantic\Nsecurity. Okay so, basically for cipher
Dialogue: 0,0:13:18.17,0:13:23.20,Default,,0000,0000,0000,,is semantically secure then no\Nbit of information is revealed to an
Dialogue: 0,0:13:23.20,0:13:27.39,Default,,0000,0000,0000,,efficient adversary. Okay so this is\Nexactly a concept of perfect secrecy only
Dialogue: 0,0:13:27.39,0:13:31.32,Default,,0000,0000,0000,,applied just efficient adversaries\Nrather than all adversaries. So the next
Dialogue: 0,0:13:31.32,0:13:35.04,Default,,0000,0000,0000,,thing I wanna show you is that in fact the\None time pad in fact is
Dialogue: 0,0:13:35.04,0:13:38.82,Default,,0000,0000,0000,,semantically secure, they better be\Nsemantically secure because it's in fact,
Dialogue: 0,0:13:38.82,0:13:42.77,Default,,0000,0000,0000,,it's more than that it's perfectly secure.\NSo let's see why that's true. Well so
Dialogue: 0,0:13:42.77,0:13:47.01,Default,,0000,0000,0000,,again it's one of these experiments, so\Nsuppose we have an adversary that claims
Dialogue: 0,0:13:47.01,0:13:51.45,Default,,0000,0000,0000,,to break semantic security of the one time\Npad. The first the adversary is gonna do
Dialogue: 0,0:13:51.45,0:13:55.87,Default,,0000,0000,0000,,is he's gonna output two messages M0\Nand M1 of the same length.
Dialogue: 0,0:13:55.87,0:13:59.67,Default,,0000,0000,0000,,Now what does he get back as a challenge? As a\Nchallenge, he gets either the encryption
Dialogue: 0,0:13:59.67,0:14:03.99,Default,,0000,0000,0000,,of M0 or the encryption of M1 under\Nthe one time pad.
Dialogue: 0,0:14:03.99,0:14:07.89,Default,,0000,0000,0000,,And he's trying to distinguish between those two possible\Ncipher texts that he gets, right?
Dialogue: 0,0:14:07.89,0:14:12.26,Default,,0000,0000,0000,,In experiment zero, he gets the encryption of\NM0 and in experiment one, he gets the
Dialogue: 0,0:14:12.26,0:14:16.58,Default,,0000,0000,0000,,encryption of M1. Well so let me ask\Nyou, so what is the advantage of adversary
Dialogue: 0,0:14:16.58,0:14:21.30,Default,,0000,0000,0000,,A against the one time patent? So I\Nremember that the property of the ones I
Dialogue: 0,0:14:21.30,0:14:26.21,Default,,0000,0000,0000,,had is that, that K, XOR M0 is\Ndistributed identically to K, XOR M1.
Dialogue: 0,0:14:26.21,0:14:31.19,Default,,0000,0000,0000,,In other words, these distributions are\Nabsolutely identical distribution,
Dialogue: 0,0:14:31.19,0:14:36.03,Default,,0000,0000,0000,,distributions, identical. This is a\Nproperty of XOR. If we XOR the random pad
Dialogue: 0,0:14:36.03,0:14:40.67,Default,,0000,0000,0000,,K with anything, either M0 or M1,\Nwe get uniform distribution. So in both
Dialogue: 0,0:14:40.67,0:14:45.38,Default,,0000,0000,0000,,cases, algorithm A is given as in input\Nexactly the same distribution. Maybe the
Dialogue: 0,0:14:45.38,0:14:50.21,Default,,0000,0000,0000,,uniform distribution on cipher texts. And\Ntherefore it's gonna behave exactly the
Dialogue: 0,0:14:50.21,0:14:55.04,Default,,0000,0000,0000,,same in both cases because it was given\Nthe exact distribution as input. And as a
Dialogue: 0,0:14:55.04,0:14:59.70,Default,,0000,0000,0000,,result, its advantage is zero, which means\Nthat the onetime pad is semantically
Dialogue: 0,0:14:59.72,0:15:04.15,Default,,0000,0000,0000,,secure. Now the interesting thing here is\Nnot only is it semantically secure, it's
Dialogue: 0,0:15:04.15,0:15:08.24,Default,,0000,0000,0000,,semantically secure for all adversaries.\NWe don't even have to restrict the
Dialogue: 0,0:15:08.24,0:15:12.45,Default,,0000,0000,0000,,adversaries to be efficient. No adversary,\Ndoesn't matter how smart you are, no
Dialogue: 0,0:15:12.45,0:15:16.88,Default,,0000,0000,0000,,adversary will be able to distinguish K XOR M0 from K XOR M1 because the two
Dialogue: 0,0:15:16.88,0:15:21.30,Default,,0000,0000,0000,,distributions are identical. Okay, so the\None time pad is semantically secure. Okay,
Dialogue: 0,0:15:21.30,0:15:25.56,Default,,0000,0000,0000,,so that completes our definition of\Nsemantic security so the next thing we're
Dialogue: 0,0:15:25.56,0:15:30.09,Default,,0000,0000,0000,,going to do is prove to the secure PRG,\Nin fact implies that the stream cipher is
Dialogue: 0,0:15:30.09,0:15:31.19,Default,,0000,0000,0000,,semantically secure.