0:00:00.000,0:00:04.388
In this segment we ask whether we can[br]build block ciphers from simpler

0:00:04.388,0:00:09.456
primitives like pseudo random generators.[br]The answer is yes. So to begin with, let's

0:00:09.456,0:00:14.215
ask whether we can build pseudo random[br]functions as opposed to pseudo random

0:00:14.215,0:00:18.789
permutations from a pseudo random[br]generator. Can we build a PRF from a PRG?

0:00:18.789,0:00:23.873
Our ultimate goal though is to build a[br]block cipher which is a PRP. And we'll get

0:00:23.873,0:00:29.130
to that at the end. Okay, for now we build[br]a PRF. So let's start with a PRG that

0:00:29.130,0:00:34.590
doubles its inputs so the seeds for the[br]PRG is an element in K and the output is

0:00:34.590,0:00:39.420
actually two elements in K. So here we[br]have a schematic of the generator, that

0:00:39.420,0:00:44.296
basically takes his input of C and K, and[br]outputs two elements, in K as its output.

0:00:44.296,0:00:48.992
And now what does it mean for this purity[br]to be secure, recall this means that

0:00:48.992,0:00:52.965
essentially the output is[br]indistinguishable from a random element

0:00:52.965,0:00:58.355
inside of K squared Now it turns out that[br]it's very easy to define basically what's

0:00:58.355,0:01:03.455
called a one bit PRF from this PRG. So[br]what's a one bit PRF is basically a PRF

0:01:03.455,0:01:08.360
who's domain is only one bit. Okay, so[br]it's a PRF that just takes one bit as

0:01:08.360,0:01:13.461
input. Okay, and the way we'll do it is[br]we'll say is if the input bit X is zero

0:01:13.461,0:01:18.627
I'll put the left output and if the input[br]bit X is one then I'll put the right

0:01:18.627,0:01:23.678
output of the PRF. Okay, in symbols we[br]basically have what we wrote here. Now it

0:01:23.678,0:01:28.523
is straightforward to show, that in fact G[br]is a secure PRG, then this one bit PRF is

0:01:28.523,0:01:32.901
in fact a secure PRF. If you think about[br]it for a second, this really is not

0:01:32.901,0:01:37.571
[inaudible]. Its really just stating the[br]same thing twice. So i will leave it for

0:01:37.571,0:01:42.241
you to think about this briefly and see[br]and convince yourself that in fact this

0:01:42.241,0:01:46.853
theorem is true. The real questions is[br]whether we can build a PRF, that actually

0:01:46.853,0:01:51.756
has a domain that is bigger than one bit.[br]Ideally we would like the domain to be 128

0:01:51.756,0:01:56.425
bits, just say as a [inaudible] has. So[br]the question is can we build 128 bit PRS

0:01:56.425,0:02:01.197
from a pseudo random generator. Well so[br]let's see if we can make progress. So the

0:02:01.197,0:02:05.970
first thing we're gonna do is we're gonna[br]say, well again, let's start with a PRG

0:02:05.970,0:02:10.863
that doubles its input let's see if we can[br]build a PRG that quadruples its inputs.

0:02:10.863,0:02:15.797
Okay? So it goes from K to K to the fourth[br]instead of K to K squared. Okay, so let's

0:02:15.797,0:02:20.809
see how to do this. So here we start with[br]our original PRG that just doubles its

0:02:20.809,0:02:25.884
inputs, now remember that the fact that[br]his is a PRG means that the output of the

0:02:25.884,0:02:30.771
PRG is indistinguishable from two random[br]values in K. Well, if the output looks

0:02:30.771,0:02:35.847
like two random values in K, we can simply[br]apply the generator again to those two

0:02:35.847,0:02:40.358
outputs. So let's say we apply the[br]generator once to the left output, and

0:02:40.358,0:02:45.342
once to the rights outputs. And we are[br]going to call the output of that, this

0:02:45.342,0:02:50.448
quadruple of elements, we are, are going[br]to call that G1K. And i wrote down in

0:02:50.448,0:02:55.554
symbols what this generator does, but you[br]can see basically from this figure,

0:02:55.554,0:03:00.862
exactly how the generator works. So now[br]that we have a generator from K to K to

0:03:00.862,0:03:06.170
the fourth, We actually get a two bit PRF.[br]Namely, what we will do is, we will say,

0:03:06.170,0:03:11.410
given two bits, 000110 or eleven, wills[br]imply output the appropriate block that

0:03:11.410,0:03:16.070
the output of G1K. Okay, so now we can[br]basically have a PRF that takes four

0:03:16.070,0:03:21.061
possible inputs as opposed to just two[br]possible inputs as before. So the question

0:03:21.061,0:03:26.113
you should be asking me is why is this G1[br]case secure? Why is it a secure PRG? That

0:03:26.113,0:03:30.611
is why is this quadruple of outputs[br]indistinguishable from random. And so

0:03:30.611,0:03:35.664
let's do a quick proof of this, we'll just[br]do a simple proof by pictures. So here's

0:03:35.664,0:03:40.408
our generator that we want to prove is[br]secure. And what that means is that we

0:03:40.408,0:03:45.399
want to argue that this distribution is[br]indistinguishable from a random fordable

0:03:45.399,0:03:49.292
in K to the fourth. Okay so our goal is to[br]prove that these two are

0:03:49.292,0:03:53.887
indistinguishable. Well let's do it one[br]step at a time. We know that the generator

0:03:53.887,0:03:58.028
is a secure generator, therefore in fact[br]the output of the first level is

0:03:58.028,0:04:02.453
indistinguishable from random. In other[br]words, if we replace the first level by

0:04:02.453,0:04:06.991
truly random strings these two are truly[br]random picked in the key space, then no

0:04:10.267,0:04:11.359
efficient adversary should be able to[br]distinguish these two distributions. In

0:04:11.359,0:04:15.954
fact, if you could distinguish these two[br]distributions, it's easy to show that you

0:04:15.954,0:04:20.768
would break the original PRG. Okay, but[br]essentially you see that the reason we can

0:04:20.768,0:04:25.581
do this replacement, we can replace the[br]output of G, with truly random values, is

0:04:25.581,0:04:30.578
exactly because of the definition of the[br]PRG, which says the out put of the PRG is

0:04:30.578,0:04:35.391
indistinguishable from random, so we might[br]as well just put random there, and no

0:04:35.391,0:04:40.265
efficient adversary can distinguish the[br]resulting two distributions. Okay, so far

0:04:40.265,0:04:45.018
so good, but now we can do the same thing[br]again to the left hand side. In other

0:04:45.018,0:04:49.710
words, we can replace these two pseudo[br]random outputs, by truly random outputs.

0:04:49.710,0:04:53.925
And again because the generator G is[br]secure, no efficient adversary can tell

0:04:54.091,0:04:57.807
the difference between these two[br]distributions. But differently, if an

0:04:57.807,0:05:02.077
adversary can distinguish these two[br]distributions, then we would also give an

0:05:02.077,0:05:06.707
attack on the generator G. And now finally[br]we're gonna do this one last time. We're

0:05:06.707,0:05:11.280
gonna replace this pseudo random pair By a[br]truly random pair, and low and behold we

0:05:11.280,0:05:15.672
get the actual distribution that we were[br]shooting for, we would get a distribution

0:05:15.672,0:05:19.851
that is really made of four independent[br]blocks. And so now we have proved this

0:05:19.851,0:05:23.279
transition basically that these two[br]indistinguishable, these two

0:05:23.279,0:05:27.243
indistinguishable, and these two[br]indistinguishable, and therefore these two

0:05:27.243,0:05:31.475
are indistinguishable, which is what we[br]wanted to prove. Okay so this is kind of

0:05:31.475,0:05:35.760
the high level idea for the proof, it is[br]not too difficult to make this rigorous,

0:05:35.760,0:05:39.792
but i just wanted to show you kinda[br]intuition for how the proof works. Well,

0:05:39.792,0:05:44.363
if we were able to extend the generators[br]outputs once, there's nothing preventing

0:05:44.363,0:05:48.822
us from doing it again so here is a[br]generator G1 that outputs four elements in

0:05:48.822,0:05:53.337
the key space. And remember the output[br]here is indistinguishable from our random

0:05:53.337,0:05:57.909
four couple, that's what we just proved.[br]And so there's nothing preventing us from

0:05:57.909,0:06:02.480
applying the generator again. So we'll[br]take the generator apply it to this random

0:06:02.480,0:06:07.221
looking thing and we should be able to get[br]this random looking thing. This pair over

0:06:07.221,0:06:11.511
here that's random looking. And we can do[br]the same thing again, and again, and

0:06:11.511,0:06:16.405
again. And now basically we've built a new[br]generator that outputs elements in K to

0:06:16.405,0:06:21.261
the eighth, as opposed to K to the fourth.[br]And again the proof of security is very

0:06:21.261,0:06:26.056
much the same as the one I just showed you[br]essentially you gradually change the

0:06:26.056,0:06:30.612
outputs into truly random outputs. So we[br]would change this to a truly random

0:06:30.612,0:06:35.168
output, then this, then that, then this,[br]then that and so on and so forth. Until

0:06:35.168,0:06:39.724
finally we get something that's truly[br]random and therefore the original two

0:06:39.724,0:06:44.396
distributions we started with G2K and[br]truly random are indistinguishable. Okay,

0:06:44.396,0:06:49.325
so far so good. So now we have a generator[br]that outputs elements in K to the eighth.

0:06:49.325,0:06:54.016
Now if we do that basically we get a three[br]bit PRF. In other words, at zero, zero,

0:06:54.016,0:06:58.884
zero this PRF would output this block, and[br]so on and so forth until one, one, one it

0:06:58.884,0:07:03.163
would output this block. Now the[br]interesting thing is that in fact this PRF

0:07:03.163,0:07:07.695
is easy to compute. For example, suppose[br]we wanted to compute the PRF at the point

0:07:07.695,0:07:11.948
one zero one. Okay, it's a three bit PRF.[br]Okay so one zero one. How would we do

0:07:11.948,0:07:16.536
that? Well basically we would start from[br]the original key K. And now we would apply

0:07:16.536,0:07:20.620
the generator G but we would only pay[br]attention to the right output of G,

0:07:20.620,0:07:25.040
because the first bit is one. And then we[br]will apply the generator again, but we

0:07:25.040,0:07:29.516
would only pay attention to the left of[br]the output of the generator because the

0:07:29.516,0:07:33.864
second bit is zero. And then we would[br]apply the generator again and only pay

0:07:33.864,0:07:38.588
attention to the right outputs because the[br]third bit is one and that would be the

0:07:38.588,0:07:43.140
final output. Right, so you can see that,[br]that lead us to 101, and in fact because

0:07:43.140,0:07:47.461
the [inaudible] generator is pseudo[br]random, we know that, in particular that,

0:07:47.461,0:07:52.796
this output here is pseudo random. Okay,[br]so this gives us a three bit PRF. Well, if

0:07:52.796,0:07:58.632
it worked three times, there's no reason[br]why it can't work N times. And so if we

0:07:58.632,0:08:03.501
apply this transformation again and again,[br]we arrive at what's called a GGMPRF. Ggm

0:08:03.501,0:08:07.956
stands for Goldreich, Goldwasser and[br]Micali these are the inventors of

0:08:07.956,0:08:12.528
this PRF and the way it works is as[br]follows. So we start off with a generator

0:08:12.528,0:08:17.279
just doubles its outputs, and now we're[br]able to build a PRF that acts on a large

0:08:17.279,0:08:22.236
domain mainly a domain of size zero one to[br]the N. Or N could be as big as 128 or even

0:08:22.236,0:08:26.897
more. So let's see, suppose we're given an[br]input in 01 to the N, let me show you how

0:08:26.897,0:08:31.274
to evaluate the PRF. Well by now you[br]should actually have a good idea for how

0:08:31.274,0:08:35.480
to do it. Essentially we start from the[br]original key and then we apply the

0:08:35.480,0:08:40.255
generator and we take either the left or[br]the right side depending on the bit X0 and

0:08:40.255,0:08:44.746
then we arrive at the next key, K1. And[br]then we apply the generator again and we

0:08:44.746,0:08:49.444
take the left or the right side depending[br]on X1 and we arrive at the next key. And

0:08:49.444,0:08:54.730
then we do this again and again, until[br]finally we are arrive at the output. So we

0:08:54.730,0:08:59.818
have processed all end bits, and we arrive[br]at the output of this function. And

0:08:59.818,0:09:05.170
basically we can prove security again[br]pretty much along the same lines as we did

0:09:05.170,0:09:10.324
before, and we can show that if G is a[br]secure PRG, then in fact we get a secure

0:09:10.324,0:09:14.917
PRF, on 01 to the N, on a very large[br]domain. So that's fantastic. Now we have

0:09:14.917,0:09:19.064
we have essential, we have a PRF that's[br]provably secure, assuming that the

0:09:19.064,0:09:23.495
underlying generator is secure, and the[br]generator is supposedly much easier to

0:09:23.495,0:09:28.153
build than an actual PRF. And in fact it[br]works on blocks that can be very large, in

0:09:28.153,0:09:33.296
particular, 01 to the 128th, which is what[br]we needed. So you might ask well why isn't

0:09:33.296,0:09:39.122
this thing being used in practice? And the[br]reason is, that it's actually fairly slow.

0:09:39.122,0:09:44.597
So imagine we plug in as a generator we[br]plug in the salsa generator. So now to

0:09:44.597,0:09:50.142
evaluate this PRF at a 128 bit inputs, we[br]would basically have to run the salsa

0:09:50.142,0:09:55.617
generator 128 times. One time per bit of[br]the input. But then we would get a PRF

0:09:55.617,0:10:01.513
that's 128 times slower than the original[br]salsa. And that's much, much, much slower

0:10:01.513,0:10:06.227
than AES. Aes is a heuristic PRF. But[br]nevertheless it's much faster then what we

0:10:06.227,0:10:10.585
just got here. And so even though this is[br]a very elegant construction, it's not used

0:10:10.585,0:10:14.522
in practice to build pseudo random[br]functions although in a week we will be

0:10:14.522,0:10:18.915
using this type of construction to build a[br]message integrity mechanism. So the last

0:10:18.915,0:10:23.183
step, is basically now that we've built a[br]PRF, the questions is whether we can

0:10:23.183,0:10:27.729
actually build the block cypher. In other[br]words, can we actually build a secure PRP

0:10:27.729,0:10:32.054
from a secure PRG. Everything we've done[br]so far is not reversible. Again if you

0:10:32.054,0:10:36.600
look at this construction here, we can't[br]decrypt basically given the final outputs.

0:10:36.600,0:10:40.535
It is not possible to go back or at least[br]we don't know how to go back the, the

0:10:40.535,0:10:44.520
original inputs. So now the question of[br]interest is so can we actually solve the

0:10:44.520,0:10:48.654
problem we wanted solve initially? Mainly,[br]can we actually build a block cipher from

0:10:48.654,0:10:53.540
a secure PRG? So ill let you think about[br]this for a second, and mark the answer. So

0:10:53.540,0:10:57.718
of course I hope everyone said the answer[br]is yes and you already have all the

0:10:57.718,0:11:01.896
ingredients to do it. In particular, you[br]already know how to build a PRF from a

0:11:01.896,0:11:06.395
pseudo random generator. And we said that[br]once we have a PRF we can plug it into the

0:11:06.395,0:11:10.573
Luby-Rackoff construction, which if you[br]remember, is just a three-round feistel.

0:11:10.573,0:11:14.750
So we said that if you plug a secure PRF[br]into a three-round feistel, you get a

0:11:14.750,0:11:19.044
secure PRP. So combining these two[br]together, basically gives us a secure PRP

0:11:19.044,0:11:23.328
from a pseudo random generator. And this[br]is provably secure as long as the

0:11:23.328,0:11:28.075
underlying generator is secure. So it's a[br]beautiful result but unfortunately again

0:11:28.075,0:11:32.475
it's not used in practice because it's[br]considerably slower than heuristics

0:11:32.475,0:11:36.725
constructions like AES. Okay so[br]this completes our module on constructing

0:11:36.725,0:11:40.456
pseudo random permutations, and pseudo[br]random functions. And then in the next

0:11:40.456,0:11:44.287
module we're gonna talk about how to use[br]these things to do proper encryption.