[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.26,Default,,0000,0000,0000,,Now that we've seen a few examples of\Nhistoric ciphers, all of which are badly
Dialogue: 0,0:00:04.26,0:00:07.13,Default,,0000,0000,0000,,broken, we're going to switch gears and\Ntalk about ciphers that are much better
Dialogue: 0,0:00:10.12,0:00:13.12,Default,,0000,0000,0000,,designed. But before we do that, I want to,\Nfirst of all, define more precisely what a
Dialogue: 0,0:00:13.12,0:00:17.43,Default,,0000,0000,0000,,cipher is. So first of all, a cipher is\Nactually, remember a cipher is made up of
Dialogue: 0,0:00:17.43,0:00:21.69,Default,,0000,0000,0000,,two algorithms. There's an encryption\Nalgorithm and a decryption algorithm. But
Dialogue: 0,0:00:21.69,0:00:26.01,Default,,0000,0000,0000,,in fact, a cipher is defined over a\Ntriple. So the set of all possible keys,
Dialogue: 0,0:00:26.01,0:00:31.29,Default,,0000,0000,0000,,which I'm going to denote by script K, and\Nsometimes I'll call this the key space,
Dialogue: 0,0:00:31.29,0:00:35.97,Default,,0000,0000,0000,,it's the set of all possible keys. There's\Nthis set of all possible messages and this
Dialogue: 0,0:00:35.97,0:00:40.36,Default,,0000,0000,0000,,set of all possible ciphertexts. Okay, so\Nthis triple in some sense defines the
Dialogue: 0,0:00:40.36,0:00:44.76,Default,,0000,0000,0000,,environment over which the cipher is\Ndefined. And then the cipher itself is a
Dialogue: 0,0:00:44.76,0:00:49.24,Default,,0000,0000,0000,,pair of efficient algorithms E and D. E is\Nthe encryption algorithm; D is the
Dialogue: 0,0:00:49.24,0:00:57.76,Default,,0000,0000,0000,,decryption algorithm. Of course, E takes\Nkeys and messages. And outputs ciphertexts.
Dialogue: 0,0:00:57.76,0:01:06.77,Default,,0000,0000,0000,,And the decryption algorithm takes\Nkeys and ciphertexts. Then outputs messages.
Dialogue: 0,0:01:06.77,0:01:12.28,Default,,0000,0000,0000,,And the only requirements is that these\Nalgorithms are consistent. They satisfy
Dialogue: 0,0:01:12.28,0:01:17.93,Default,,0000,0000,0000,,what's called the correctness property. So\Nfor every message in the message space.
Dialogue: 0,0:01:17.93,0:01:23.59,Default,,0000,0000,0000,,And every key. In the key space, it had\Nbetter be the case that if I encrypt the
Dialogue: 0,0:01:23.59,0:01:29.18,Default,,0000,0000,0000,,message with the key K and then I decrypt\Nusing the same key K I had better get back
Dialogue: 0,0:01:29.18,0:01:34.71,Default,,0000,0000,0000,,the original message that I started with.\NSo this equation here is what's called the
Dialogue: 0,0:01:34.71,0:01:39.97,Default,,0000,0000,0000,,consistency equation and every cipher has\Nto satisfy it in order to be a cipher
Dialogue: 0,0:01:39.97,0:01:44.97,Default,,0000,0000,0000,,otherwise it's not possible to decrypt.\NOne thing I wanted to point out is that I
Dialogue: 0,0:01:44.97,0:01:49.78,Default,,0000,0000,0000,,put the word efficient here in quotes. And\Nthe reason I do that is because efficient
Dialogue: 0,0:01:49.78,0:01:54.04,Default,,0000,0000,0000,,means different things to different\Npeople. If you're more inclined towards
Dialogue: 0,0:01:54.04,0:01:58.81,Default,,0000,0000,0000,,theory, efficient means runs in polynomial\Ntime. So algorithms E and D have to run in
Dialogue: 0,0:01:58.81,0:02:02.84,Default,,0000,0000,0000,,polynomial time in the size of their\Ninputs. If you're more practically
Dialogue: 0,0:02:02.84,0:02:07.04,Default,,0000,0000,0000,,inclined, efficient means runs within a\Ncertain time period. So for example,
Dialogue: 0,0:02:07.04,0:02:11.47,Default,,0000,0000,0000,,algorithm E might be required to take\Nunder a minute to encrypt a gigabyte of
Dialogue: 0,0:02:11.47,0:02:16.07,Default,,0000,0000,0000,,data. Now either way, the word efficient\Nkind of captures both notions and you can
Dialogue: 0,0:02:16.07,0:02:20.16,Default,,0000,0000,0000,,interpret it in your head whichever way\Nyou'd like. I'm just going to keep
Dialogue: 0,0:02:20.16,0:02:24.14,Default,,0000,0000,0000,,referring to it as efficient and put\Nquotes in it as I said if you're theory
Dialogue: 0,0:02:24.19,0:02:27.96,Default,,0000,0000,0000,,inclined think of it as polynomial time,\Notherwise think of it as
Dialogue: 0,0:02:27.96,0:02:32.10,Default,,0000,0000,0000,,concrete time constraints. Another comment\NI want to make is in fact algorithm E.
Dialogue: 0,0:02:32.10,0:02:36.46,Default,,0000,0000,0000,,It's often a randomized algorithm. What\Nthat means is that as your encrypting
Dialogue: 0,0:02:36.46,0:02:40.98,Default,,0000,0000,0000,,messages, algorithm E is gonna generate\Nrandom bits for itself, and it's going to
Dialogue: 0,0:02:40.98,0:02:45.68,Default,,0000,0000,0000,,use those random bits to actually encrypt\Nthe messages that are given to it. On the
Dialogue: 0,0:02:45.68,0:02:50.26,Default,,0000,0000,0000,,other hand the decrypting algorithm is\Nalways deterministic. In other words given
Dialogue: 0,0:02:50.26,0:02:54.56,Default,,0000,0000,0000,,the key and the ciphertext output is\Nalways the same. Doesn't depend on any
Dialogue: 0,0:02:54.56,0:02:58.97,Default,,0000,0000,0000,,randomness that's used by the algorithm.\NOkay, so now that we understand what a
Dialogue: 0,0:02:58.97,0:03:03.55,Default,,0000,0000,0000,,cipher is better, I want to kind of show\Nyou the first example of a secure cipher.
Dialogue: 0,0:03:03.55,0:03:08.36,Default,,0000,0000,0000,,It's called a one time pad It was designed\Nby Vernam back at the beginning of the
Dialogue: 0,0:03:08.36,0:03:12.72,Default,,0000,0000,0000,,twentieth century. Before I actually\Nexplain what the cipher is, let's just
Dialogue: 0,0:03:12.72,0:03:17.38,Default,,0000,0000,0000,,state it in the terminology that we've\Njust seen. So the message space for the
Dialogue: 0,0:03:17.38,0:03:22.22,Default,,0000,0000,0000,,Vernam cipher for the one-time pad is the\Nsame as the ciphertext space which is
Dialogue: 0,0:03:22.22,0:03:27.65,Default,,0000,0000,0000,,just the set of all ended binary strings.\NThis, this just means all sequences of
Dialogue: 0,0:03:27.65,0:03:33.85,Default,,0000,0000,0000,,bits, of zero one characters. The key\Nspace is basically the same as the message
Dialogue: 0,0:03:33.85,0:03:40.13,Default,,0000,0000,0000,,space which is again simply the embed of\Nall binary strings. So a key in the one
Dialogue: 0,0:03:40.13,0:03:46.29,Default,,0000,0000,0000,,time pad is simply a random big string,\Nit's a random sequence of bits. That's as
Dialogue: 0,0:03:46.29,0:03:51.51,Default,,0000,0000,0000,,long as the message to be encrypted, as\Nlong as the message. Okay, now that we've
Dialogue: 0,0:03:51.51,0:03:56.73,Default,,0000,0000,0000,,specified kind of what's the cipher's\Ndefined over we can actually specify how
Dialogue: 0,0:03:56.73,0:04:02.01,Default,,0000,0000,0000,,the cipher works and it's actually really\Nsimple. So essentially the ciphertexts.
Dialogue: 0,0:04:02.01,0:04:07.81,Default,,0000,0000,0000,,Which is the result of encrypting a\Nmessage with a particular key, is simply
Dialogue: 0,0:04:07.81,0:04:13.77,Default,,0000,0000,0000,,the XOR of the two. Simply K XOR M. [inaudible] see a quick example of
Dialogue: 0,0:04:13.77,0:04:20.03,Default,,0000,0000,0000,,this. Remember that XOR, this plus\Nwith a circle. XOR means addition
Dialogue: 0,0:04:20.03,0:04:26.82,Default,,0000,0000,0000,,modulo two. So if I take a particular\Nmessage, say, 0110111. And it take a
Dialogue: 0,0:04:26.82,0:04:33.87,Default,,0000,0000,0000,,particular key, say 1011001. When I\Ncompute the encryption of the message
Dialogue: 0,0:04:33.87,0:04:38.84,Default,,0000,0000,0000,,using this key, all I do is I\Ncompute the XOR of these two
Dialogue: 0,0:04:38.84,0:04:43.94,Default,,0000,0000,0000,,strings. In other words, I do addition\Nmodule or two bit by bit. So I get one,
Dialogue: 0,0:04:43.94,0:04:48.64,Default,,0000,0000,0000,,one, zero, one, one, one, zero. That's a\Nciphertext. And then how do I decrypt? I
Dialogue: 0,0:04:48.64,0:04:52.89,Default,,0000,0000,0000,,guess they could do kind of the same\Nthing. So they decrypt a cipher text using
Dialogue: 0,0:04:52.89,0:04:57.25,Default,,0000,0000,0000,,a particular key. What I do is I XOR the\Nkey and the ciphertext again. And so all
Dialogue: 0,0:04:57.25,0:05:01.82,Default,,0000,0000,0000,,we have to verify is that it satisfies the\Nconsistency requirements. And I'm going to
Dialogue: 0,0:05:01.82,0:05:06.44,Default,,0000,0000,0000,,do this slowly once and then from now on\NI'm going to assume this is all, simple to
Dialogue: 0,0:05:06.44,0:05:10.80,Default,,0000,0000,0000,,you. So we're gonna make, we're gonna have\Nto make sure that if I decrypt a cipher
Dialogue: 0,0:05:10.80,0:05:14.89,Default,,0000,0000,0000,,text, that was encrypted using a\Nparticular key, I had better get. Back the
Dialogue: 0,0:05:14.89,0:05:20.48,Default,,0000,0000,0000,,message M. So what happens here? Well,\Nlet's see. So if I look at the encryption
Dialogue: 0,0:05:20.48,0:05:25.100,Default,,0000,0000,0000,,of k and m, this is just k XOR m by\Ndefinition. What's the decryption of k XOR
Dialogue: 0,0:05:25.100,0:05:31.63,Default,,0000,0000,0000,,m using k? That's just k XOR (k XOR\Nm). And so since I said that XOR is
Dialogue: 0,0:05:31.63,0:05:36.95,Default,,0000,0000,0000,,addition modulo two, addition is\Nassociative, so this is the same as (k XOR k)
Dialogue: 0,0:05:36.95,0:05:43.01,Default,,0000,0000,0000,,XOR m, which is simply as you know k XOR k is a zero, and zero XOR anything
Dialogue: 0,0:05:43.01,0:05:49.07,Default,,0000,0000,0000,,is simply m. Okay, so this actually shows\Nthat the one-time pad is in fact a cipher,
Dialogue: 0,0:05:49.07,0:05:54.28,Default,,0000,0000,0000,,but it doesn't say anything about the\Nsecurity of the cipher. And we'll talk
Dialogue: 0,0:05:54.28,0:05:58.32,Default,,0000,0000,0000,,about security of the cipher in just a\Nminute. First of all, let me quickly ask
Dialogue: 0,0:05:58.32,0:06:02.20,Default,,0000,0000,0000,,you a question, just to make sure we're\Nall in sync. Suppose you are given a
Dialogue: 0,0:06:02.20,0:06:06.09,Default,,0000,0000,0000,,message m and the encryption of that\Nmessage using the one time pad. So all
Dialogue: 0,0:06:06.09,0:06:10.52,Default,,0000,0000,0000,,you're given is the message and the cipher\Ntext. My question to you is, given this
Dialogue: 0,0:06:10.52,0:06:15.47,Default,,0000,0000,0000,,pair m and c, can you actually figure out\Nthe one-time pad key that was used in the
Dialogue: 0,0:06:15.47,0:06:20.59,Default,,0000,0000,0000,,creation of c from m?
Dialogue: 0,0:06:20.59,0:06:23.03,Default,,0000,0000,0000,,So I hope all of you\Nrealize that in fact, given the message in
Dialogue: 0,0:06:23.03,0:06:25.47,Default,,0000,0000,0000,,the cipher text it's very easy to recover\Nwhat the key is. In particular the key is
Dialogue: 0,0:06:25.47,0:06:30.24,Default,,0000,0000,0000,,simply M XOR C. Then we'll see that if\Nit's not immediately obvious to you we'll
Dialogue: 0,0:06:30.24,0:06:35.24,Default,,0000,0000,0000,,see why that's, the case, a little later\Nin the talk, in the lecture. Okay alright
Dialogue: 0,0:06:35.24,0:06:40.20,Default,,0000,0000,0000,,so the 1-time pad is a really cool from a\Nperformance point of view all you're doing
Dialogue: 0,0:06:40.20,0:06:44.66,Default,,0000,0000,0000,,is you exo-ring the key in the message so\Nit's a super, super fast. Cypher for
Dialogue: 0,0:06:44.66,0:06:48.46,Default,,0000,0000,0000,,encrypting and decrypting very long\Nmessages. Unfortunately it's very
Dialogue: 0,0:06:48.46,0:06:52.77,Default,,0000,0000,0000,,difficult to use in practice. The reason\Nit's difficult to use is the keys are
Dialogue: 0,0:06:52.77,0:06:56.91,Default,,0000,0000,0000,,essentially as long as the message. So if\NAlice and Bob want to communicate
Dialogue: 0,0:06:56.91,0:07:01.32,Default,,0000,0000,0000,,securely, so you know Alice wants to send\Na message end to Bob, before she begins
Dialogue: 0,0:07:01.32,0:07:06.01,Default,,0000,0000,0000,,even sending the first bit of the message,\Nshe has to transmit a key to Bob that's as
Dialogue: 0,0:07:06.01,0:07:10.54,Default,,0000,0000,0000,,long as that message. Well, if she has a\Nway to transmit a secure key to Bob that's
Dialogue: 0,0:07:10.54,0:07:15.06,Default,,0000,0000,0000,,as long as the message, she might as well\Nuse that same mechanism to also transmit
Dialogue: 0,0:07:15.06,0:07:19.44,Default,,0000,0000,0000,,the message itself. So the fact that the\Nkey is as long as the message is quite
Dialogue: 0,0:07:19.44,0:07:23.49,Default,,0000,0000,0000,,problematic and makes the one-time pad\Nvery difficult to use in practice.
Dialogue: 0,0:07:23.49,0:07:28.04,Default,,0000,0000,0000,,Although we'll see that the idea behind\Nthe one-time pad is actually quite useful
Dialogue: 0,0:07:28.04,0:07:32.59,Default,,0000,0000,0000,,and we'll see that a little bit later. But\Nfor now I want to focus a little bit on
Dialogue: 0,0:07:32.59,0:07:36.92,Default,,0000,0000,0000,,security. So the obvious questions are,\Nyou know, why is the one-time pad secure?
Dialogue: 0,0:07:36.92,0:07:41.20,Default,,0000,0000,0000,,Why is it a good cypher? Then to answer\Nthat question, the first thing we have to
Dialogue: 0,0:07:41.20,0:07:45.19,Default,,0000,0000,0000,,answer is, what is a secure cipher to\Nbegin with? What is a, what makes cipher
Dialogue: 0,0:07:45.19,0:07:49.76,Default,,0000,0000,0000,,secure? Okay, so the study, security of\Nciphers, we have to talk a little bit
Dialogue: 0,0:07:49.76,0:07:54.96,Default,,0000,0000,0000,,about information theory. And in fact the\Nfirst person, to study security of ciphers
Dialogue: 0,0:07:55.15,0:08:00.08,Default,,0000,0000,0000,,rigorously. Is very famous, you know, the\Nfather of information theory, Claude
Dialogue: 0,0:08:00.08,0:08:05.04,Default,,0000,0000,0000,,Shannon, and he published a famous paper\Nback in 1949 where he analyzes the
Dialogue: 0,0:08:05.04,0:08:10.60,Default,,0000,0000,0000,,security of the one-time pad. So the idea\Nbehind Shannon's definition of security is
Dialogue: 0,0:08:10.60,0:08:15.18,Default,,0000,0000,0000,,the following. Basically, if all you get\Nto see is the cypher text, then you should
Dialogue: 0,0:08:15.18,0:08:19.38,Default,,0000,0000,0000,,learn absolutely nothing about the plain\Ntext. In other words, the cypher text
Dialogue: 0,0:08:19.38,0:08:23.41,Default,,0000,0000,0000,,should reveal no information about the\Nplain text. And you see why it took
Dialogue: 0,0:08:23.41,0:08:28.05,Default,,0000,0000,0000,,someone who invented information theory to\Ncome up with this notion because you have
Dialogue: 0,0:08:28.05,0:08:32.52,Default,,0000,0000,0000,,to formulize, formally explain what does\Ninformation about the plain text actually
Dialogue: 0,0:08:32.52,0:08:37.65,Default,,0000,0000,0000,,mean. Okay so that's what Shannon did and\Nso lemme show you Shannon's definition,
Dialogue: 0,0:08:37.65,0:08:42.84,Default,,0000,0000,0000,,I'll, I'll write it out slowly first. So\Nwhat Shannon said is you know suppose we
Dialogue: 0,0:08:42.84,0:08:48.03,Default,,0000,0000,0000,,have a cypher E D that's defined over\Ntriple K M and C just as before. So KM and
Dialogue: 0,0:08:48.03,0:08:53.41,Default,,0000,0000,0000,,C define the key space, the message space\Nand the cypher text space. And when we say
Dialogue: 0,0:08:53.41,0:08:58.40,Default,,0000,0000,0000,,that the cypher text sorry we say that the\Ncypher has perfect secrecy if the
Dialogue: 0,0:08:58.40,0:09:03.59,Default,,0000,0000,0000,,following condition holds. It so happens\Nfor every two messages M zero and M1 in
Dialogue: 0,0:09:03.59,0:09:08.68,Default,,0000,0000,0000,,the message space. For every two messages\Nthe only requirement I'm gonna put on
Dialogue: 0,0:09:08.68,0:09:13.83,Default,,0000,0000,0000,,these messages is they have the same\Nlength. Yeah so we're only, we'll see why
Dialogue: 0,0:09:13.83,0:09:19.11,Default,,0000,0000,0000,,this requirement is necessary in just a\Nminute. And for every cyphertext, in the
Dialogue: 0,0:09:19.11,0:09:25.22,Default,,0000,0000,0000,,cyphertext space. Okay? So for every pair\Nof method messages and for every cipher
Dialogue: 0,0:09:25.22,0:09:31.12,Default,,0000,0000,0000,,text, it had better be the case that, if I\Nask, what is the probability that,
Dialogue: 0,0:09:31.36,0:09:37.10,Default,,0000,0000,0000,,encrypting N zero with K, woops.\NEncrypting N zero with K gives C, okay? So
Dialogue: 0,0:09:37.10,0:09:43.55,Default,,0000,0000,0000,,how likely is it, if we pick a random key?\NHow likely is it that when we encrypt N
Dialogue: 0,0:09:43.55,0:09:49.82,Default,,0000,0000,0000,,zero, we get C. That probability should be\Nthe same as when we encrypt N1. Okay, so
Dialogue: 0,0:09:49.82,0:09:54.92,Default,,0000,0000,0000,,the probability of encrypting n one and\Ngetting c is exactly the same as the
Dialogue: 0,0:09:54.92,0:09:59.96,Default,,0000,0000,0000,,probability of encrypting n zero and\Ngetting c. And just as I said where the
Dialogue: 0,0:09:59.96,0:10:04.66,Default,,0000,0000,0000,,key, the distribution, is over the\Ndistribution on the key. So, the key is
Dialogue: 0,0:10:04.66,0:10:10.16,Default,,0000,0000,0000,,uniform in the key space. So k is uniform\Nin k. And I'm often going to write k arrow
Dialogue: 0,0:10:10.16,0:10:15.39,Default,,0000,0000,0000,,with a little r above it to denote the\Nfact that k is a random variable that's
Dialogue: 0,0:10:15.39,0:10:20.49,Default,,0000,0000,0000,,uniformly sampled in the key space k.\NOkay, this is the main part of Shannon's
Dialogue: 0,0:10:20.49,0:10:25.89,Default,,0000,0000,0000,,definition. And let's think a little bit\Nabout what this definition actually says.
Dialogue: 0,0:10:25.89,0:10:30.96,Default,,0000,0000,0000,,So what does it mean that these two\Nprobabilities are the same? Well, what it
Dialogue: 0,0:10:30.96,0:10:36.30,Default,,0000,0000,0000,,says is that if I'm an attacker and I\Nintercept a particular cypher text c, then
Dialogue: 0,0:10:36.30,0:10:41.58,Default,,0000,0000,0000,,in reality, the probability that the\Ncypher text is the encryption of n zero is
Dialogue: 0,0:10:41.58,0:10:46.80,Default,,0000,0000,0000,,exactly the same as the probability that\Nit's the incryption of n one. Because
Dialogue: 0,0:10:46.80,0:10:52.22,Default,,0000,0000,0000,,those probabilities are equal. So if I\Nhave, all I have the cypher text C that's
Dialogue: 0,0:10:52.22,0:10:57.64,Default,,0000,0000,0000,,all I have intercepted I have no idea\Nwhether the cypher text came from M zero
Dialogue: 0,0:10:57.64,0:11:03.20,Default,,0000,0000,0000,,or the cypher text came from M one because\Nagain the probability of getting C is
Dialogue: 0,0:11:03.20,0:11:08.65,Default,,0000,0000,0000,,equally likely whether M zero is being\Nencrypted or M one is being encrypted. So
Dialogue: 0,0:11:08.65,0:11:13.29,Default,,0000,0000,0000,,here, we have the definition stated again.\NAnd I just wanna write these properties
Dialogue: 0,0:11:13.29,0:11:17.75,Default,,0000,0000,0000,,again more precisely. So let's write this\Nagain. So what [inaudible] definition
Dialogue: 0,0:11:17.75,0:11:22.33,Default,,0000,0000,0000,,means is that if I am given a particular\Ncipher text, I can't tell where it came
Dialogue: 0,0:11:22.33,0:11:27.12,Default,,0000,0000,0000,,from. I can't tell if it's, if the message\Nthat was encrypted. Is either N zero or N
Dialogue: 0,0:11:27.12,0:11:32.09,Default,,0000,0000,0000,,one and in fact, this property is true for\Nall messages. For all these N zero, for
Dialogue: 0,0:11:32.09,0:11:37.12,Default,,0000,0000,0000,,all N zero and N ones. So not only can I\Nnot tell if'c' came from N zero or N one,
Dialogue: 0,0:11:37.12,0:11:42.14,Default,,0000,0000,0000,,I can't tell if it came from N two or N\Nthree or N four or N five because all of
Dialogue: 0,0:11:42.14,0:11:47.11,Default,,0000,0000,0000,,them are equally likely to produce the\Ncypher text'c'. So what this means really
Dialogue: 0,0:11:47.11,0:11:52.07,Default,,0000,0000,0000,,is that if you're encrypting messages with\Na one time pad then in fact the most
Dialogue: 0,0:11:52.07,0:11:56.73,Default,,0000,0000,0000,,powerful adversary, I don't really care\Nhow smart you are, the most powerful
Dialogue: 0,0:11:56.73,0:12:02.53,Default,,0000,0000,0000,,adversary. Can learn nothing about the\Nplain text, learns nothing about the plain
Dialogue: 0,0:12:02.53,0:12:09.62,Default,,0000,0000,0000,,text. From the cypher text. So to say it\Nin one more way, basically what this
Dialogue: 0,0:12:09.62,0:12:16.32,Default,,0000,0000,0000,,proves is that there's no, there's no\Ncypher text-only attack on a cypher that
Dialogue: 0,0:12:16.32,0:12:23.26,Default,,0000,0000,0000,,has perfect secrecy. Now, cypher attacks\Nactually aren't the only attacks possible.
Dialogue: 0,0:12:23.26,0:12:29.44,Default,,0000,0000,0000,,And in fact, other attacks may be\Npossible, other attacks may be possible.
Dialogue: 0,0:12:32.16,0:12:36.77,Default,,0000,0000,0000,,Okay. Now that we understand what perfect\Nsecrecy, means, the question is, can we
Dialogue: 0,0:12:36.77,0:12:41.33,Default,,0000,0000,0000,,build ciphers that actually have perfect\Nsecrecy? And it turns out that we don't
Dialogue: 0,0:12:41.33,0:12:45.52,Default,,0000,0000,0000,,have to look very far, the one time\Npattern fact has perfect secrecy. So I
Dialogue: 0,0:12:45.52,0:12:50.72,Default,,0000,0000,0000,,want to prove to you this is Shannon's first\Nresults and I wanna prove this fact to
Dialogue: 0,0:12:50.72,0:12:55.86,Default,,0000,0000,0000,,you, it's very simple proof so let's go\Nahead and look at it and just do it. So we
Dialogue: 0,0:12:55.86,0:13:01.06,Default,,0000,0000,0000,,need to kind of interpret what does that\Nmean, what is this probability that E K M
Dialogue: 0,0:13:01.06,0:13:06.20,Default,,0000,0000,0000,,Z is equal to C. So it's actually not that\Nhard to see that for every message and
Dialogue: 0,0:13:06.20,0:13:11.02,Default,,0000,0000,0000,,every cyphertext the probability that the\Nencryption of N under a key K the
Dialogue: 0,0:13:11.02,0:13:16.16,Default,,0000,0000,0000,,probability that, that's equal to C, the\Nprobability that our random choice of key
Dialogue: 0,0:13:16.16,0:13:23.72,Default,,0000,0000,0000,,by definition. All that is, is basically\Nthe number of keys. Kay, instruct Kay.
Dialogue: 0,0:13:24.76,0:13:31.53,Default,,0000,0000,0000,,Such that, well. If I encrypt. And with k\NI get c. So I literally count the number
Dialogue: 0,0:13:31.53,0:13:37.21,Default,,0000,0000,0000,,of keys and I divide by the total number\Nof keys. Right? That's what it means, that
Dialogue: 0,0:13:37.21,0:13:42.83,Default,,0000,0000,0000,,if I choose a random key, that key maps m\Nto c. Right. So it's basically the number
Dialogue: 0,0:13:42.83,0:13:47.71,Default,,0000,0000,0000,,of key that map n to c divided by the\Ntotal number of keys. This is its
Dialogue: 0,0:13:47.71,0:13:53.41,Default,,0000,0000,0000,,probability. So now suppose that we had a\Ncypher such that for all messages and all
Dialogue: 0,0:13:53.41,0:13:58.97,Default,,0000,0000,0000,,cypher texts, it so happens that if I look\Nat this number, the number of k, k, and k,
Dialogue: 0,0:13:58.97,0:14:04.39,Default,,0000,0000,0000,,such that e, k, m is equal to c. In other\Nwords, I'm looking at the number of keys
Dialogue: 0,0:14:04.39,0:14:09.26,Default,,0000,0000,0000,,that map m to c. Suppose this number\Nhappens to be a constant. So say it
Dialogue: 0,0:14:09.26,0:14:14.08,Default,,0000,0000,0000,,happens to be two, three, or ten or\Nfifteen. It just hap, happens to be an
Dialogue: 0,0:14:14.08,0:14:19.33,Default,,0000,0000,0000,,absolute constance. If that's the case,\Nthen by definition, for all n0 and n1 and
Dialogue: 0,0:14:19.33,0:14:24.75,Default,,0000,0000,0000,,for all c, this probability has to be the\Nsame because the denominator is the same,
Dialogue: 0,0:14:24.75,0:14:30.10,Default,,0000,0000,0000,,the numerator is the same, it's just as\Nconstant, and therefore the probability is
Dialogue: 0,0:14:30.10,0:14:35.64,Default,,0000,0000,0000,,always the same for all n and c. And so if\Nthis property is true, then the cypher has
Dialogue: 0,0:14:35.64,0:14:43.62,Default,,0000,0000,0000,,to have, the cypher has perfect secrecy.\NOkay, so lets see what can we say about
Dialogue: 0,0:14:43.62,0:14:48.80,Default,,0000,0000,0000,,this quantity for the one time pad. So the\Nsec-, so, the question to you is, if I
Dialogue: 0,0:14:48.80,0:14:54.77,Default,,0000,0000,0000,,have a message in a cipher-text, how many\None time pad keys are there [inaudible]
Dialogue: 0,0:14:54.77,0:15:00.38,Default,,0000,0000,0000,,map, this message ends, so the [inaudible]\NC? So, in other words, how many keys are
Dialogue: 0,0:15:00.38,0:15:06.10,Default,,0000,0000,0000,,there, such that M XOR K is equal to C?\NSo I hope you've all answered one. And
Dialogue: 0,0:15:06.10,0:15:12.68,Default,,0000,0000,0000,,let's see why that's the case. For the one\Ntime pad, if we have that, the encryption
Dialogue: 0,0:15:12.68,0:15:18.30,Default,,0000,0000,0000,,of K of M under K is equal to C. But\Nbasically, well, by definition, that
Dialogue: 0,0:15:18.30,0:15:24.88,Default,,0000,0000,0000,,implies that K XOR M is equal to C. But\Nthat also simply says that K has to equal
Dialogue: 0,0:15:24.88,0:15:31.77,Default,,0000,0000,0000,,to M XOR C. Yes, I just X over both\Nsides by M and I get that K must equal the
Dialogue: 0,0:15:31.77,0:15:37.56,Default,,0000,0000,0000,,M XOR C. Okay? So what that says is\Nthat, for the one time pad, in fact, the
Dialogue: 0,0:15:37.56,0:15:43.71,Default,,0000,0000,0000,,number of keys, in K, shows the EKM, is\Nequal to C. That simply is one, and this
Dialogue: 0,0:15:43.71,0:15:49.85,Default,,0000,0000,0000,,holds for all messages in cipher text. And\Nso, again, by what we said before, it just
Dialogue: 0,0:15:49.85,0:15:54.99,Default,,0000,0000,0000,,says that the one time pad has, perfect\Nsecrecy. Perfect secrecy and that
Dialogue: 0,0:15:54.99,0:15:59.09,Default,,0000,0000,0000,,completes the proof of this [inaudible]\Nvery, very simple. Very, very simple
Dialogue: 0,0:15:59.09,0:16:03.64,Default,,0000,0000,0000,,lemma. Now the funny thing is that\Neven though this lemma is so simple to
Dialogue: 0,0:16:03.64,0:16:08.19,Default,,0000,0000,0000,,prove in fact it proves a pretty powerful\Nstatement again. This basically says for
Dialogue: 0,0:16:08.19,0:16:12.33,Default,,0000,0000,0000,,the one time [inaudible] there is no\Ncypher text only attack. So, unlike the
Dialogue: 0,0:16:12.33,0:16:16.39,Default,,0000,0000,0000,,substitution cipher, or the vigenere\Ncipher, or the roller machines, all those
Dialogue: 0,0:16:16.39,0:16:20.78,Default,,0000,0000,0000,,could be broken by ciphertext-only attack.\NWe've just proved that for the one-time
Dialogue: 0,0:16:20.78,0:16:25.11,Default,,0000,0000,0000,,pad, that's simply impossible. Given the\Ncyphertext, you simply learn nothing about
Dialogue: 0,0:16:25.11,0:16:29.28,Default,,0000,0000,0000,,the plaintext. However, as we can see,\Nthis is simply not the end of the story. I
Dialogue: 0,0:16:29.28,0:16:33.13,Default,,0000,0000,0000,,mean, are we done? I mean, basically,\Nwe're done with the course now, cuz we
Dialogue: 0,0:16:33.13,0:16:37.36,Default,,0000,0000,0000,,have a way. To encrypt, so that an\Nattacker can't recover anything about our
Dialogue: 0,0:16:37.36,0:16:41.21,Default,,0000,0000,0000,,method. So maybe we're done with the\Ncourse. But in fact, as we'll see, there
Dialogue: 0,0:16:41.21,0:16:45.26,Default,,0000,0000,0000,,are other attacks. And, in fact, the one\Ntime pad is actually not such a
Dialogue: 0,0:16:45.26,0:16:49.32,Default,,0000,0000,0000,,secure cipher. And in fact, there are\Nother attacks that are possible, and we'll
Dialogue: 0,0:16:49.32,0:16:54.08,Default,,0000,0000,0000,,see that shortly. Okay? I emphasize again\Nthe fact that it has perfect secrecy does
Dialogue: 0,0:16:54.08,0:16:58.78,Default,,0000,0000,0000,,not mean that the one time pad is the\Nsecure cypher to use. Okay. But as we said
Dialogue: 0,0:16:58.78,0:17:03.73,Default,,0000,0000,0000,,the problem with the one time pad is that\Nthe secret key is really long. If you had
Dialogue: 0,0:17:03.73,0:17:08.07,Default,,0000,0000,0000,,a way of. Communicating the secret key\Nover to the other side. You might as well
Dialogue: 0,0:17:08.07,0:17:12.25,Default,,0000,0000,0000,,use that exact same method to also\Ncommunicate the message to the other side,
Dialogue: 0,0:17:12.25,0:17:16.65,Default,,0000,0000,0000,,in which case you wouldn't need a cypher\Nto begin with. Okay? So the problem again
Dialogue: 0,0:17:16.65,0:17:21.10,Default,,0000,0000,0000,,is the one time pad had really long keys\Nand so the obvious question is are there
Dialogue: 0,0:17:21.10,0:17:25.45,Default,,0000,0000,0000,,other cyphers that has perfect secrecy and\Npossibly have much, much shorter keys?
Dialogue: 0,0:17:25.45,0:17:30.14,Default,,0000,0000,0000,,Well, so the bad news is the Shannon,\Nafter proving that the one-time pad has
Dialogue: 0,0:17:30.14,0:17:34.94,Default,,0000,0000,0000,,perfect secrecy, proved another theorem\Nthat says that in fact if a cypher has
Dialogue: 0,0:17:34.94,0:17:39.88,Default,,0000,0000,0000,,perfect secrecy, the number of keys in the\Ncypher must be at least the number of
Dialogue: 0,0:17:39.88,0:17:44.94,Default,,0000,0000,0000,,messages that the cypher can handle. Okay,\Nso in particular, what this means is if I
Dialogue: 0,0:17:44.94,0:17:51.04,Default,,0000,0000,0000,,have perfect secrecy. Then necessarily the\Nnumber of keys, or rather the length of my
Dialogue: 0,0:17:51.04,0:17:56.31,Default,,0000,0000,0000,,key, must be greater than the length of\Nthe message. So, in fact, since the one
Dialogue: 0,0:17:56.31,0:18:00.83,Default,,0000,0000,0000,,time pad satisfies us with equality, the\None time pad is an optimal, cipher that
Dialogue: 0,0:18:00.83,0:18:04.86,Default,,0000,0000,0000,,has perfect secrecy, okay? So basically,\Nwhat this shows is that this is an
Dialogue: 0,0:18:04.86,0:18:09.06,Default,,0000,0000,0000,,interesting notion. The one time pad is an\Ninteresting cipher. But, in fact, in
Dialogue: 0,0:18:09.06,0:18:13.36,Default,,0000,0000,0000,,reality, it's actually quite hard to use.\NIt's hard to use in practice, again,
Dialogue: 0,0:18:13.36,0:18:17.79,Default,,0000,0000,0000,,because of these long keys. And so this\Nnotion of perfect secrecy, even though
Dialogue: 0,0:18:17.79,0:18:21.84,Default,,0000,0000,0000,,it's quite interesting, basically says\Nthat it doesn't really tell us the
Dialogue: 0,0:18:21.84,0:18:26.28,Default,,0000,0000,0000,,practical cyphers are going to be secure.\NAnd we're gonna see, but, as we said, the
Dialogue: 0,0:18:26.28,0:18:30.99,Default,,0000,0000,0000,,idea behind the one time pad is quite good.\NAnd we're gonna see, in the next lecture,
Dialogue: 0,0:18:30.99,0:18:33.55,Default,,0000,0000,0000,,how to make that into a practical\Nsystem.