In this segment we ask whether we can build block ciphers from simpler primitives like pseudo random generators. The answer is yes. So to begin with, let's ask whether we can build pseudo random functions as opposed to pseudo random permutations from a pseudo random generator. Can we build a PRF from a PRG? Our ultimate goal though is to build a block cipher which is a PRP. And we'll get to that at the end. Okay, for now we build a PRF. So let's start with a PRG that doubles its inputs so the seeds for the PRG is an element in K and the output is actually two elements in K. So here we have a schematic of the generator, that basically takes his input of C and K, and outputs two elements, in K as its output. And now what does it mean for this purity to be secure, recall this means that essentially the output is indistinguishable from a random element inside of K squared Now it turns out that it's very easy to define basically what's called a one bit PRF from this PRG. So what's a one bit PRF is basically a PRF who's domain is only one bit. Okay, so it's a PRF that just takes one bit as input. Okay, and the way we'll do it is we'll say is if the input bit X is zero I'll put the left output and if the input bit X is one then I'll put the right output of the PRF. Okay, in symbols we basically have what we wrote here. Now it is straightforward to show, that in fact G is a secure PRG, then this one bit PRF is in fact a secure PRF. If you think about it for a second, this really is not [inaudible]. Its really just stating the same thing twice. So i will leave it for you to think about this briefly and see and convince yourself that in fact this theorem is true. The real questions is whether we can build a PRF, that actually has a domain that is bigger than one bit. Ideally we would like the domain to be 128 bits, just say as a [inaudible] has. So the question is can we build 128 bit PRS from a pseudo random generator. Well so let's see if we can make progress. So the first thing we're gonna do is we're gonna say, well again, let's start with a PRG that doubles its input let's see if we can build a PRG that quadruples its inputs. Okay? So it goes from K to K to the fourth instead of K to K squared. Okay, so let's see how to do this. So here we start with our original PRG that just doubles its inputs, now remember that the fact that his is a PRG means that the output of the PRG is indistinguishable from two random values in K. Well, if the output looks like two random values in K, we can simply apply the generator again to those two outputs. So let's say we apply the generator once to the left output, and once to the rights outputs. And we are going to call the output of that, this quadruple of elements, we are, are going to call that G1K. And i wrote down in symbols what this generator does, but you can see basically from this figure, exactly how the generator works. So now that we have a generator from K to K to the fourth, We actually get a two bit PRF. Namely, what we will do is, we will say, given two bits, 000110 or eleven, wills imply output the appropriate block that the output of G1K. Okay, so now we can basically have a PRF that takes four possible inputs as opposed to just two possible inputs as before. So the question you should be asking me is why is this G1 case secure? Why is it a secure PRG? That is why is this quadruple of outputs indistinguishable from random. And so let's do a quick proof of this, we'll just do a simple proof by pictures. So here's our generator that we want to prove is secure. And what that means is that we want to argue that this distribution is indistinguishable from a random fordable in K to the fourth. Okay so our goal is to prove that these two are indistinguishable. Well let's do it one step at a time. We know that the generator is a secure generator, therefore in fact the output of the first level is indistinguishable from random. In other words, if we replace the first level by truly random strings these two are truly random picked in the key space, then no efficient adversary should be able to distinguish these two distributions. In fact, if you could distinguish these two distributions, it's easy to show that you would break the original PRG. Okay, but essentially you see that the reason we can do this replacement, we can replace the output of G, with truly random values, is exactly because of the definition of the PRG, which says the out put of the PRG is indistinguishable from random, so we might as well just put random there, and no efficient adversary can distinguish the resulting two distributions. Okay, so far so good, but now we can do the same thing again to the left hand side. In other words, we can replace these two pseudo random outputs, by truly random outputs. And again because the generator G is secure, no efficient adversary can tell the difference between these two distributions. But differently, if an adversary can distinguish these two distributions, then we would also give an attack on the generator G. And now finally we're gonna do this one last time. We're gonna replace this pseudo random pair By a truly random pair, and low and behold we get the actual distribution that we were shooting for, we would get a distribution that is really made of four independent blocks. And so now we have proved this transition basically that these two indistinguishable, these two indistinguishable, and these two indistinguishable, and therefore these two are indistinguishable, which is what we wanted to prove. Okay so this is kind of the high level idea for the proof, it is not too difficult to make this rigorous, but i just wanted to show you kinda intuition for how the proof works. Well, if we were able to extend the generators outputs once, there's nothing preventing us from doing it again so here is a generator G1 that outputs four elements in the key space. And remember the output here is indistinguishable from our random four couple, that's what we just proved. And so there's nothing preventing us from applying the generator again. So we'll take the generator apply it to this random looking thing and we should be able to get this random looking thing. This pair over here that's random looking. And we can do the same thing again, and again, and again. And now basically we've built a new generator that outputs elements in K to the eighth, as opposed to K to the fourth. And again the proof of security is very much the same as the one I just showed you essentially you gradually change the outputs into truly random outputs. So we would change this to a truly random output, then this, then that, then this, then that and so on and so forth. Until finally we get something that's truly random and therefore the original two distributions we started with G2K and truly random are indistinguishable. Okay, so far so good. So now we have a generator that outputs elements in K to the eighth. Now if we do that basically we get a three bit PRF. In other words, at zero, zero, zero this PRF would output this block, and so on and so forth until one, one, one it would output this block. Now the interesting thing is that in fact this PRF is easy to compute. For example, suppose we wanted to compute the PRF at the point one zero one. Okay, it's a three bit PRF. Okay so one zero one. How would we do that? Well basically we would start from the original key K. And now we would apply the generator G but we would only pay attention to the right output of G, because the first bit is one. And then we will apply the generator again, but we would only pay attention to the left of the output of the generator because the second bit is zero. And then we would apply the generator again and only pay attention to the right outputs because the third bit is one and that would be the final output. Right, so you can see that, that lead us to 101, and in fact because the [inaudible] generator is pseudo random, we know that, in particular that, this output here is pseudo random. Okay, so this gives us a three bit PRF. Well, if it worked three times, there's no reason why it can't work N times. And so if we apply this transformation again and again, we arrive at what's called a GGMPRF. Ggm stands for Goldreich, Goldwasser and Micali these are the inventors of this PRF and the way it works is as follows. So we start off with a generator just doubles its outputs, and now we're able to build a PRF that acts on a large domain mainly a domain of size zero one to the N. Or N could be as big as 128 or even more. So let's see, suppose we're given an input in 01 to the N, let me show you how to evaluate the PRF. Well by now you should actually have a good idea for how to do it. Essentially we start from the original key and then we apply the generator and we take either the left or the right side depending on the bit X0 and then we arrive at the next key, K1. And then we apply the generator again and we take the left or the right side depending on X1 and we arrive at the next key. And then we do this again and again, until finally we are arrive at the output. So we have processed all end bits, and we arrive at the output of this function. And basically we can prove security again pretty much along the same lines as we did before, and we can show that if G is a secure PRG, then in fact we get a secure PRF, on 01 to the N, on a very large domain. So that's fantastic. Now we have we have essential, we have a PRF that's provably secure, assuming that the underlying generator is secure, and the generator is supposedly much easier to build than an actual PRF. And in fact it works on blocks that can be very large, in particular, 01 to the 128th, which is what we needed. So you might ask well why isn't this thing being used in practice? And the reason is, that it's actually fairly slow. So imagine we plug in as a generator we plug in the salsa generator. So now to evaluate this PRF at a 128 bit inputs, we would basically have to run the salsa generator 128 times. One time per bit of the input. But then we would get a PRF that's 128 times slower than the original salsa. And that's much, much, much slower than AES. Aes is a heuristic PRF. But nevertheless it's much faster then what we just got here. And so even though this is a very elegant construction, it's not used in practice to build pseudo random functions although in a week we will be using this type of construction to build a message integrity mechanism. So the last step, is basically now that we've built a PRF, the questions is whether we can actually build the block cypher. In other words, can we actually build a secure PRP from a secure PRG. Everything we've done so far is not reversible. Again if you look at this construction here, we can't decrypt basically given the final outputs. It is not possible to go back or at least we don't know how to go back the, the original inputs. So now the question of interest is so can we actually solve the problem we wanted solve initially? Mainly, can we actually build a block cipher from a secure PRG? So ill let you think about this for a second, and mark the answer. So of course I hope everyone said the answer is yes and you already have all the ingredients to do it. In particular, you already know how to build a PRF from a pseudo random generator. And we said that once we have a PRF we can plug it into the Luby-Rackoff construction, which if you remember, is just a three-round feistel. So we said that if you plug a secure PRF into a three-round feistel, you get a secure PRP. So combining these two together, basically gives us a secure PRP from a pseudo random generator. And this is provably secure as long as the underlying generator is secure. So it's a beautiful result but unfortunately again it's not used in practice because it's considerably slower than heuristics constructions like AES. Okay so this completes our module on constructing pseudo random permutations, and pseudo random functions. And then in the next module we're gonna talk about how to use these things to do proper encryption.
