0:00

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

Â 4:10

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.

Â