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.