[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.00,0:00:04.39,Default,,0000,0000,0000,,In this segment we ask whether we can\Nbuild block ciphers from simpler Dialogue: 0,0:00:04.39,0:00:09.46,Default,,0000,0000,0000,,primitives like pseudo random generators.\NThe answer is yes. So to begin with, let's Dialogue: 0,0:00:09.46,0:00:14.22,Default,,0000,0000,0000,,ask whether we can build pseudo random\Nfunctions as opposed to pseudo random Dialogue: 0,0:00:14.22,0:00:18.79,Default,,0000,0000,0000,,permutations from a pseudo random\Ngenerator. Can we build a PRF from a PRG? Dialogue: 0,0:00:18.79,0:00:23.87,Default,,0000,0000,0000,,Our ultimate goal though is to build a\Nblock cipher which is a PRP. And we'll get Dialogue: 0,0:00:23.87,0:00:29.13,Default,,0000,0000,0000,,to that at the end. Okay, for now we build\Na PRF. So let's start with a PRG that Dialogue: 0,0:00:29.13,0:00:34.59,Default,,0000,0000,0000,,doubles its inputs so the seeds for the\NPRG is an element in K and the output is Dialogue: 0,0:00:34.59,0:00:39.42,Default,,0000,0000,0000,,actually two elements in K. So here we\Nhave a schematic of the generator, that Dialogue: 0,0:00:39.42,0:00:44.30,Default,,0000,0000,0000,,basically takes his input of C and K, and\Noutputs two elements, in K as its output. Dialogue: 0,0:00:44.30,0:00:48.99,Default,,0000,0000,0000,,And now what does it mean for this purity\Nto be secure, recall this means that Dialogue: 0,0:00:48.99,0:00:52.96,Default,,0000,0000,0000,,essentially the output is\Nindistinguishable from a random element Dialogue: 0,0:00:52.96,0:00:58.36,Default,,0000,0000,0000,,inside of K squared Now it turns out that\Nit's very easy to define basically what's Dialogue: 0,0:00:58.36,0:01:03.46,Default,,0000,0000,0000,,called a one bit PRF from this PRG. So\Nwhat's a one bit PRF is basically a PRF Dialogue: 0,0:01:03.46,0:01:08.36,Default,,0000,0000,0000,,who's domain is only one bit. Okay, so\Nit's a PRF that just takes one bit as Dialogue: 0,0:01:08.36,0:01:13.46,Default,,0000,0000,0000,,input. Okay, and the way we'll do it is\Nwe'll say is if the input bit X is zero Dialogue: 0,0:01:13.46,0:01:18.63,Default,,0000,0000,0000,,I'll put the left output and if the input\Nbit X is one then I'll put the right Dialogue: 0,0:01:18.63,0:01:23.68,Default,,0000,0000,0000,,output of the PRF. Okay, in symbols we\Nbasically have what we wrote here. Now it Dialogue: 0,0:01:23.68,0:01:28.52,Default,,0000,0000,0000,,is straightforward to show, that in fact G\Nis a secure PRG, then this one bit PRF is Dialogue: 0,0:01:28.52,0:01:32.90,Default,,0000,0000,0000,,in fact a secure PRF. If you think about\Nit for a second, this really is not Dialogue: 0,0:01:32.90,0:01:37.57,Default,,0000,0000,0000,,[inaudible]. Its really just stating the\Nsame thing twice. So i will leave it for Dialogue: 0,0:01:37.57,0:01:42.24,Default,,0000,0000,0000,,you to think about this briefly and see\Nand convince yourself that in fact this Dialogue: 0,0:01:42.24,0:01:46.85,Default,,0000,0000,0000,,theorem is true. The real questions is\Nwhether we can build a PRF, that actually Dialogue: 0,0:01:46.85,0:01:51.76,Default,,0000,0000,0000,,has a domain that is bigger than one bit.\NIdeally we would like the domain to be 128 Dialogue: 0,0:01:51.76,0:01:56.42,Default,,0000,0000,0000,,bits, just say as a [inaudible] has. So\Nthe question is can we build 128 bit PRS Dialogue: 0,0:01:56.42,0:02:01.20,Default,,0000,0000,0000,,from a pseudo random generator. Well so\Nlet's see if we can make progress. So the Dialogue: 0,0:02:01.20,0:02:05.97,Default,,0000,0000,0000,,first thing we're gonna do is we're gonna\Nsay, well again, let's start with a PRG Dialogue: 0,0:02:05.97,0:02:10.86,Default,,0000,0000,0000,,that doubles its input let's see if we can\Nbuild a PRG that quadruples its inputs. Dialogue: 0,0:02:10.86,0:02:15.80,Default,,0000,0000,0000,,Okay? So it goes from K to K to the fourth\Ninstead of K to K squared. Okay, so let's Dialogue: 0,0:02:15.80,0:02:20.81,Default,,0000,0000,0000,,see how to do this. So here we start with\Nour original PRG that just doubles its Dialogue: 0,0:02:20.81,0:02:25.88,Default,,0000,0000,0000,,inputs, now remember that the fact that\Nhis is a PRG means that the output of the Dialogue: 0,0:02:25.88,0:02:30.77,Default,,0000,0000,0000,,PRG is indistinguishable from two random\Nvalues in K. Well, if the output looks Dialogue: 0,0:02:30.77,0:02:35.85,Default,,0000,0000,0000,,like two random values in K, we can simply\Napply the generator again to those two Dialogue: 0,0:02:35.85,0:02:40.36,Default,,0000,0000,0000,,outputs. So let's say we apply the\Ngenerator once to the left output, and Dialogue: 0,0:02:40.36,0:02:45.34,Default,,0000,0000,0000,,once to the rights outputs. And we are\Ngoing to call the output of that, this Dialogue: 0,0:02:45.34,0:02:50.45,Default,,0000,0000,0000,,quadruple of elements, we are, are going\Nto call that G1K. And i wrote down in Dialogue: 0,0:02:50.45,0:02:55.55,Default,,0000,0000,0000,,symbols what this generator does, but you\Ncan see basically from this figure, Dialogue: 0,0:02:55.55,0:03:00.86,Default,,0000,0000,0000,,exactly how the generator works. So now\Nthat we have a generator from K to K to Dialogue: 0,0:03:00.86,0:03:06.17,Default,,0000,0000,0000,,the fourth, We actually get a two bit PRF.\NNamely, what we will do is, we will say, Dialogue: 0,0:03:06.17,0:03:11.41,Default,,0000,0000,0000,,given two bits, 000110 or eleven, wills\Nimply output the appropriate block that Dialogue: 0,0:03:11.41,0:03:16.07,Default,,0000,0000,0000,,the output of G1K. Okay, so now we can\Nbasically have a PRF that takes four Dialogue: 0,0:03:16.07,0:03:21.06,Default,,0000,0000,0000,,possible inputs as opposed to just two\Npossible inputs as before. So the question Dialogue: 0,0:03:21.06,0:03:26.11,Default,,0000,0000,0000,,you should be asking me is why is this G1\Ncase secure? Why is it a secure PRG? That Dialogue: 0,0:03:26.11,0:03:30.61,Default,,0000,0000,0000,,is why is this quadruple of outputs\Nindistinguishable from random. And so Dialogue: 0,0:03:30.61,0:03:35.66,Default,,0000,0000,0000,,let's do a quick proof of this, we'll just\Ndo a simple proof by pictures. So here's Dialogue: 0,0:03:35.66,0:03:40.41,Default,,0000,0000,0000,,our generator that we want to prove is\Nsecure. And what that means is that we Dialogue: 0,0:03:40.41,0:03:45.40,Default,,0000,0000,0000,,want to argue that this distribution is\Nindistinguishable from a random fordable Dialogue: 0,0:03:45.40,0:03:49.29,Default,,0000,0000,0000,,in K to the fourth. Okay so our goal is to\Nprove that these two are Dialogue: 0,0:03:49.29,0:03:53.89,Default,,0000,0000,0000,,indistinguishable. Well let's do it one\Nstep at a time. We know that the generator Dialogue: 0,0:03:53.89,0:03:58.03,Default,,0000,0000,0000,,is a secure generator, therefore in fact\Nthe output of the first level is Dialogue: 0,0:03:58.03,0:04:02.45,Default,,0000,0000,0000,,indistinguishable from random. In other\Nwords, if we replace the first level by Dialogue: 0,0:04:02.45,0:04:06.99,Default,,0000,0000,0000,,truly random strings these two are truly\Nrandom picked in the key space, then no Dialogue: 0,0:04:10.27,0:04:11.36,Default,,0000,0000,0000,,efficient adversary should be able to\Ndistinguish these two distributions. In Dialogue: 0,0:04:11.36,0:04:15.95,Default,,0000,0000,0000,,fact, if you could distinguish these two\Ndistributions, it's easy to show that you Dialogue: 0,0:04:15.95,0:04:20.77,Default,,0000,0000,0000,,would break the original PRG. Okay, but\Nessentially you see that the reason we can Dialogue: 0,0:04:20.77,0:04:25.58,Default,,0000,0000,0000,,do this replacement, we can replace the\Noutput of G, with truly random values, is Dialogue: 0,0:04:25.58,0:04:30.58,Default,,0000,0000,0000,,exactly because of the definition of the\NPRG, which says the out put of the PRG is Dialogue: 0,0:04:30.58,0:04:35.39,Default,,0000,0000,0000,,indistinguishable from random, so we might\Nas well just put random there, and no Dialogue: 0,0:04:35.39,0:04:40.26,Default,,0000,0000,0000,,efficient adversary can distinguish the\Nresulting two distributions. Okay, so far Dialogue: 0,0:04:40.26,0:04:45.02,Default,,0000,0000,0000,,so good, but now we can do the same thing\Nagain to the left hand side. In other Dialogue: 0,0:04:45.02,0:04:49.71,Default,,0000,0000,0000,,words, we can replace these two pseudo\Nrandom outputs, by truly random outputs. Dialogue: 0,0:04:49.71,0:04:53.92,Default,,0000,0000,0000,,And again because the generator G is\Nsecure, no efficient adversary can tell Dialogue: 0,0:04:54.09,0:04:57.81,Default,,0000,0000,0000,,the difference between these two\Ndistributions. But differently, if an Dialogue: 0,0:04:57.81,0:05:02.08,Default,,0000,0000,0000,,adversary can distinguish these two\Ndistributions, then we would also give an Dialogue: 0,0:05:02.08,0:05:06.71,Default,,0000,0000,0000,,attack on the generator G. And now finally\Nwe're gonna do this one last time. We're Dialogue: 0,0:05:06.71,0:05:11.28,Default,,0000,0000,0000,,gonna replace this pseudo random pair By a\Ntruly random pair, and low and behold we Dialogue: 0,0:05:11.28,0:05:15.67,Default,,0000,0000,0000,,get the actual distribution that we were\Nshooting for, we would get a distribution Dialogue: 0,0:05:15.67,0:05:19.85,Default,,0000,0000,0000,,that is really made of four independent\Nblocks. And so now we have proved this Dialogue: 0,0:05:19.85,0:05:23.28,Default,,0000,0000,0000,,transition basically that these two\Nindistinguishable, these two Dialogue: 0,0:05:23.28,0:05:27.24,Default,,0000,0000,0000,,indistinguishable, and these two\Nindistinguishable, and therefore these two Dialogue: 0,0:05:27.24,0:05:31.48,Default,,0000,0000,0000,,are indistinguishable, which is what we\Nwanted to prove. Okay so this is kind of Dialogue: 0,0:05:31.48,0:05:35.76,Default,,0000,0000,0000,,the high level idea for the proof, it is\Nnot too difficult to make this rigorous, Dialogue: 0,0:05:35.76,0:05:39.79,Default,,0000,0000,0000,,but i just wanted to show you kinda\Nintuition for how the proof works. Well, Dialogue: 0,0:05:39.79,0:05:44.36,Default,,0000,0000,0000,,if we were able to extend the generators\Noutputs once, there's nothing preventing Dialogue: 0,0:05:44.36,0:05:48.82,Default,,0000,0000,0000,,us from doing it again so here is a\Ngenerator G1 that outputs four elements in Dialogue: 0,0:05:48.82,0:05:53.34,Default,,0000,0000,0000,,the key space. And remember the output\Nhere is indistinguishable from our random Dialogue: 0,0:05:53.34,0:05:57.91,Default,,0000,0000,0000,,four couple, that's what we just proved.\NAnd so there's nothing preventing us from Dialogue: 0,0:05:57.91,0:06:02.48,Default,,0000,0000,0000,,applying the generator again. So we'll\Ntake the generator apply it to this random Dialogue: 0,0:06:02.48,0:06:07.22,Default,,0000,0000,0000,,looking thing and we should be able to get\Nthis random looking thing. This pair over Dialogue: 0,0:06:07.22,0:06:11.51,Default,,0000,0000,0000,,here that's random looking. And we can do\Nthe same thing again, and again, and Dialogue: 0,0:06:11.51,0:06:16.40,Default,,0000,0000,0000,,again. And now basically we've built a new\Ngenerator that outputs elements in K to Dialogue: 0,0:06:16.40,0:06:21.26,Default,,0000,0000,0000,,the eighth, as opposed to K to the fourth.\NAnd again the proof of security is very Dialogue: 0,0:06:21.26,0:06:26.06,Default,,0000,0000,0000,,much the same as the one I just showed you\Nessentially you gradually change the Dialogue: 0,0:06:26.06,0:06:30.61,Default,,0000,0000,0000,,outputs into truly random outputs. So we\Nwould change this to a truly random Dialogue: 0,0:06:30.61,0:06:35.17,Default,,0000,0000,0000,,output, then this, then that, then this,\Nthen that and so on and so forth. Until Dialogue: 0,0:06:35.17,0:06:39.72,Default,,0000,0000,0000,,finally we get something that's truly\Nrandom and therefore the original two Dialogue: 0,0:06:39.72,0:06:44.40,Default,,0000,0000,0000,,distributions we started with G2K and\Ntruly random are indistinguishable. Okay, Dialogue: 0,0:06:44.40,0:06:49.32,Default,,0000,0000,0000,,so far so good. So now we have a generator\Nthat outputs elements in K to the eighth. Dialogue: 0,0:06:49.32,0:06:54.02,Default,,0000,0000,0000,,Now if we do that basically we get a three\Nbit PRF. In other words, at zero, zero, Dialogue: 0,0:06:54.02,0:06:58.88,Default,,0000,0000,0000,,zero this PRF would output this block, and\Nso on and so forth until one, one, one it Dialogue: 0,0:06:58.88,0:07:03.16,Default,,0000,0000,0000,,would output this block. Now the\Ninteresting thing is that in fact this PRF Dialogue: 0,0:07:03.16,0:07:07.70,Default,,0000,0000,0000,,is easy to compute. For example, suppose\Nwe wanted to compute the PRF at the point Dialogue: 0,0:07:07.70,0:07:11.95,Default,,0000,0000,0000,,one zero one. Okay, it's a three bit PRF.\NOkay so one zero one. How would we do Dialogue: 0,0:07:11.95,0:07:16.54,Default,,0000,0000,0000,,that? Well basically we would start from\Nthe original key K. And now we would apply Dialogue: 0,0:07:16.54,0:07:20.62,Default,,0000,0000,0000,,the generator G but we would only pay\Nattention to the right output of G, Dialogue: 0,0:07:20.62,0:07:25.04,Default,,0000,0000,0000,,because the first bit is one. And then we\Nwill apply the generator again, but we Dialogue: 0,0:07:25.04,0:07:29.52,Default,,0000,0000,0000,,would only pay attention to the left of\Nthe output of the generator because the Dialogue: 0,0:07:29.52,0:07:33.86,Default,,0000,0000,0000,,second bit is zero. And then we would\Napply the generator again and only pay Dialogue: 0,0:07:33.86,0:07:38.59,Default,,0000,0000,0000,,attention to the right outputs because the\Nthird bit is one and that would be the Dialogue: 0,0:07:38.59,0:07:43.14,Default,,0000,0000,0000,,final output. Right, so you can see that,\Nthat lead us to 101, and in fact because Dialogue: 0,0:07:43.14,0:07:47.46,Default,,0000,0000,0000,,the [inaudible] generator is pseudo\Nrandom, we know that, in particular that, Dialogue: 0,0:07:47.46,0:07:52.80,Default,,0000,0000,0000,,this output here is pseudo random. Okay,\Nso this gives us a three bit PRF. Well, if Dialogue: 0,0:07:52.80,0:07:58.63,Default,,0000,0000,0000,,it worked three times, there's no reason\Nwhy it can't work N times. And so if we Dialogue: 0,0:07:58.63,0:08:03.50,Default,,0000,0000,0000,,apply this transformation again and again,\Nwe arrive at what's called a GGMPRF. Ggm Dialogue: 0,0:08:03.50,0:08:07.96,Default,,0000,0000,0000,,stands for Goldreich, Goldwasser and\NMicali these are the inventors of Dialogue: 0,0:08:07.96,0:08:12.53,Default,,0000,0000,0000,,this PRF and the way it works is as\Nfollows. So we start off with a generator Dialogue: 0,0:08:12.53,0:08:17.28,Default,,0000,0000,0000,,just doubles its outputs, and now we're\Nable to build a PRF that acts on a large Dialogue: 0,0:08:17.28,0:08:22.24,Default,,0000,0000,0000,,domain mainly a domain of size zero one to\Nthe N. Or N could be as big as 128 or even Dialogue: 0,0:08:22.24,0:08:26.90,Default,,0000,0000,0000,,more. So let's see, suppose we're given an\Ninput in 01 to the N, let me show you how Dialogue: 0,0:08:26.90,0:08:31.27,Default,,0000,0000,0000,,to evaluate the PRF. Well by now you\Nshould actually have a good idea for how Dialogue: 0,0:08:31.27,0:08:35.48,Default,,0000,0000,0000,,to do it. Essentially we start from the\Noriginal key and then we apply the Dialogue: 0,0:08:35.48,0:08:40.26,Default,,0000,0000,0000,,generator and we take either the left or\Nthe right side depending on the bit X0 and Dialogue: 0,0:08:40.26,0:08:44.75,Default,,0000,0000,0000,,then we arrive at the next key, K1. And\Nthen we apply the generator again and we Dialogue: 0,0:08:44.75,0:08:49.44,Default,,0000,0000,0000,,take the left or the right side depending\Non X1 and we arrive at the next key. And Dialogue: 0,0:08:49.44,0:08:54.73,Default,,0000,0000,0000,,then we do this again and again, until\Nfinally we are arrive at the output. So we Dialogue: 0,0:08:54.73,0:08:59.82,Default,,0000,0000,0000,,have processed all end bits, and we arrive\Nat the output of this function. And Dialogue: 0,0:08:59.82,0:09:05.17,Default,,0000,0000,0000,,basically we can prove security again\Npretty much along the same lines as we did Dialogue: 0,0:09:05.17,0:09:10.32,Default,,0000,0000,0000,,before, and we can show that if G is a\Nsecure PRG, then in fact we get a secure Dialogue: 0,0:09:10.32,0:09:14.92,Default,,0000,0000,0000,,PRF, on 01 to the N, on a very large\Ndomain. So that's fantastic. Now we have Dialogue: 0,0:09:14.92,0:09:19.06,Default,,0000,0000,0000,,we have essential, we have a PRF that's\Nprovably secure, assuming that the Dialogue: 0,0:09:19.06,0:09:23.50,Default,,0000,0000,0000,,underlying generator is secure, and the\Ngenerator is supposedly much easier to Dialogue: 0,0:09:23.50,0:09:28.15,Default,,0000,0000,0000,,build than an actual PRF. And in fact it\Nworks on blocks that can be very large, in Dialogue: 0,0:09:28.15,0:09:33.30,Default,,0000,0000,0000,,particular, 01 to the 128th, which is what\Nwe needed. So you might ask well why isn't Dialogue: 0,0:09:33.30,0:09:39.12,Default,,0000,0000,0000,,this thing being used in practice? And the\Nreason is, that it's actually fairly slow. Dialogue: 0,0:09:39.12,0:09:44.60,Default,,0000,0000,0000,,So imagine we plug in as a generator we\Nplug in the salsa generator. So now to Dialogue: 0,0:09:44.60,0:09:50.14,Default,,0000,0000,0000,,evaluate this PRF at a 128 bit inputs, we\Nwould basically have to run the salsa Dialogue: 0,0:09:50.14,0:09:55.62,Default,,0000,0000,0000,,generator 128 times. One time per bit of\Nthe input. But then we would get a PRF Dialogue: 0,0:09:55.62,0:10:01.51,Default,,0000,0000,0000,,that's 128 times slower than the original\Nsalsa. And that's much, much, much slower Dialogue: 0,0:10:01.51,0:10:06.23,Default,,0000,0000,0000,,than AES. Aes is a heuristic PRF. But\Nnevertheless it's much faster then what we Dialogue: 0,0:10:06.23,0:10:10.58,Default,,0000,0000,0000,,just got here. And so even though this is\Na very elegant construction, it's not used Dialogue: 0,0:10:10.58,0:10:14.52,Default,,0000,0000,0000,,in practice to build pseudo random\Nfunctions although in a week we will be Dialogue: 0,0:10:14.52,0:10:18.92,Default,,0000,0000,0000,,using this type of construction to build a\Nmessage integrity mechanism. So the last Dialogue: 0,0:10:18.92,0:10:23.18,Default,,0000,0000,0000,,step, is basically now that we've built a\NPRF, the questions is whether we can Dialogue: 0,0:10:23.18,0:10:27.73,Default,,0000,0000,0000,,actually build the block cypher. In other\Nwords, can we actually build a secure PRP Dialogue: 0,0:10:27.73,0:10:32.05,Default,,0000,0000,0000,,from a secure PRG. Everything we've done\Nso far is not reversible. Again if you Dialogue: 0,0:10:32.05,0:10:36.60,Default,,0000,0000,0000,,look at this construction here, we can't\Ndecrypt basically given the final outputs. Dialogue: 0,0:10:36.60,0:10:40.54,Default,,0000,0000,0000,,It is not possible to go back or at least\Nwe don't know how to go back the, the Dialogue: 0,0:10:40.54,0:10:44.52,Default,,0000,0000,0000,,original inputs. So now the question of\Ninterest is so can we actually solve the Dialogue: 0,0:10:44.52,0:10:48.65,Default,,0000,0000,0000,,problem we wanted solve initially? Mainly,\Ncan we actually build a block cipher from Dialogue: 0,0:10:48.65,0:10:53.54,Default,,0000,0000,0000,,a secure PRG? So ill let you think about\Nthis for a second, and mark the answer. So Dialogue: 0,0:10:53.54,0:10:57.72,Default,,0000,0000,0000,,of course I hope everyone said the answer\Nis yes and you already have all the Dialogue: 0,0:10:57.72,0:11:01.90,Default,,0000,0000,0000,,ingredients to do it. In particular, you\Nalready know how to build a PRF from a Dialogue: 0,0:11:01.90,0:11:06.40,Default,,0000,0000,0000,,pseudo random generator. And we said that\Nonce we have a PRF we can plug it into the Dialogue: 0,0:11:06.40,0:11:10.57,Default,,0000,0000,0000,,Luby-Rackoff construction, which if you\Nremember, is just a three-round feistel. Dialogue: 0,0:11:10.57,0:11:14.75,Default,,0000,0000,0000,,So we said that if you plug a secure PRF\Ninto a three-round feistel, you get a Dialogue: 0,0:11:14.75,0:11:19.04,Default,,0000,0000,0000,,secure PRP. So combining these two\Ntogether, basically gives us a secure PRP Dialogue: 0,0:11:19.04,0:11:23.33,Default,,0000,0000,0000,,from a pseudo random generator. And this\Nis provably secure as long as the Dialogue: 0,0:11:23.33,0:11:28.08,Default,,0000,0000,0000,,underlying generator is secure. So it's a\Nbeautiful result but unfortunately again Dialogue: 0,0:11:28.08,0:11:32.48,Default,,0000,0000,0000,,it's not used in practice because it's\Nconsiderably slower than heuristics Dialogue: 0,0:11:32.48,0:11:36.72,Default,,0000,0000,0000,,constructions like AES. Okay so\Nthis completes our module on constructing Dialogue: 0,0:11:36.72,0:11:40.46,Default,,0000,0000,0000,,pseudo random permutations, and pseudo\Nrandom functions. And then in the next Dialogue: 0,0:11:40.46,0:11:44.29,Default,,0000,0000,0000,,module we're gonna talk about how to use\Nthese things to do proper encryption.