-
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.