This week, we saw two families of public encryption systems. One family was built
from trapdoor functions, and particularly RSA, and the other family was built from
the Diffie-Hellman protocol. In this last segment, I wanna show you that both
families in fact follow from a more general principle. The unifying theme is
what's called a one-way function. So what is a one-way function? Well, we've already
seen this concept briefly before. But basically, a function from, one set to
another, say, from X to Y is said to be one way, if, in fact, there's an efficient
algorithm that allows us to evaluate the function F. So anyone can evaluate the
function F at any point of their choice. However, inverting the function F should
be difficult. That's what makes the function one way. So what do I mean by
that? Well, you can think of the function F as a function again mapping the set X to
the set Y. But it so happens in many points in X could actually be mapped into
a single point in Y. Now when they say that the function is difficult to invert,
what I mean is that when I give you some point inside of Y and I ask you find me
pre-image of this point, you won't be able to point to any of these as a pre-image.
In other words, no efficient algorithm can find any point that is the inverse of the
given point Y. Now the way we say that more precisely is that we say that for all
efficient algorithm A, if I chose a random X in the set, capital X, and now I'm gonna
give f(x) to algorithm A. And then, what I'm gonna ask algorithm A to do, is
basically produce a pre-image of the point f(x). Well, what does it mean that A
produced a pre-image of the point f(x)? It means that if I apply the function f to
the output of A, what I should get back is, well, f(x). Let's think through this
one more time. So I chose a random point x in Capital X. You know I give algorithm A
f(x). So I'm gonna give algorithm A this point here. And now A is gonna produce
some points. So let's pretend that A produces this point over here. And now I
wanna say that if I apply the function F to this point here, that A produced, the
probability that I get the same point that I started with is negligible. In other
words the probability that algorithm A was able to produce one of these three points is, in
fact, negligible. All he can do is produce some other point that maps into something
other than f(x), okay? So, again, all this is trying to do is just capture the
fact that given f(x), it's hard to find some pre-image of f(x). So here's some
easy examples of functions that are not one-way. For example, the identity
function f(x) is equal to x is trivially not one way because given f(x), I can
easily come up with an inverse of f(x), namely x. Similarly the function that will
maps everything to zero is also not one way. So in our picture, let the function
maps everything to zero simply looks as follows. It takes all its points and maps
them all to a single point. Well this function is not one way because if I give
you this point in the image, it's trivial to find the pre-image. Namely, just pick
any point in capital X, and there will be a pre-image of zero. And so, f(x) equal
to zero is also not a one-way function. And by the way, I didn't want to do it
here. But if I define one-way functions more formally, then it turns out that
proving that one-way functions exist, we'll have also proven that P is not equal
to NP. So, since we can't today, prove that P is not equal to NP, basically we
can't prove that one-way functions exist. And we just have to assume that they do.
So let's look at our first example of a 1-way function. Or at least a presumed
1-way function. And so we're gonna build it from a pseudo random generator. And
suppose I have a function F from x to y there is a secure pseudo random generator.
So the output of f s much larger than the input. Remember, a pseudo-random
generator takes a small seed and expands it into a much larger output. And for
example you can, you know, the pseudo random generator maybe is built using
deterministic counter mode out of AES. Well, it's fairly easy to see that if, in
fact, F is a secure pseudo random generator, then F is in fact a one-way
function. So our first example of a one-way function is directly built from a
pseudo random generator. This is actually kind of a trivial proof, so let's prove
the contra positive. So suppose I have an efficient algorithm that inverts F, okay?
So I'm proving the contra positive. Suppose F is not one way. Then A is an
efficient algorithm than an inverse F. And now I need to build an algorithm B that
breaks the pseudorandom generator. Ok, so I'm proving again by contra-positive. Okay so how do I break the
pseudo-random generator? Well, all we do is the following. So algorithm B is given
some y in the set Y. And what it's gonna do is the following, it's gonna try and
run algorithm a on the input y. And now, well, if y is the output of the
pseudorandom generator, then algorithm A will output the seed, and namely
[inaudible] an element in X with, you know, non-negligible probability. So what
we'll do is we'll apply the pseudorandom generator again to the output of algorithm
A. As I said, if y was the output of a generator, then [A of A ???] will have output
the seed cuz it inverted the pseudorandom generator. So if we apply the pseudorandom
generator again to the output of A, what we should get back is basically the y that
we started with. Okay, so if this condition holds we're gonna say we're
gonna output zero. And if this condition doesn't hold, we're gonna output one
otherwise. That's it, that's our distinguisher against a pseudo-random
generator. So if our distinguisher is given a y that is the output of the pseudo
random generator, then with non-negligible probability, our distinguisher B will
output zero. However, if our distinguisher B is given a truly random string. Well, a
truly random string doesn't have any seed that causes the generator to output that
string. And therefore our distinguishable output one with again, with also very high
probability. And again I hope that's clear. Basically, if we look at the set of
all possible outputs, namely the set Y, very few of those outputs happened to
be the output of the pseudorandom generator. So if we are just given an
output y over hearsay, that's not the output of the pseudorandom generator, then
we rerun algorithm A on it. It can't possibly produce a seed that will output
this point starr because there is no such seed. And as a result, since most
points actually are not in the image of the pseudorandom generator, most points
will not have a seed that, maps the generator to them and there's also where
we were given a random point in Y, a truly uniform point in Y, our distinguishable B
will output 1 with very high probability. However, if we are given a
pseudo random output of a generator, then algorithm A will output the corresponding
seed. When we apply the generator to that seed, we'll get the initial output y and
therefore we'll output zero with non-negligible probability. Okay, so if A
was able to invert F, then B is able to break the generator. And since the
generator is secure, algorithm A can't invert F. And in particular, no efficient
algorithm can invert F. And therefore, F is a one-way function. Excellent, so this
is a long discussion of kind of a minor point. But all I wanted to show you is
that in fact, a pseudo-random generator directly gives us a one-way function.
Unfortunately, this one-way function has no special properties. And what that means
is it's actually difficult to use it for key exchange or for public key encryption.
In some sense, the best key exchange we can do with this, as far as we know, is
Merkle puzzles. So now let's look at our second example. The second example is
what I'm gonna call the discrete log one way function. So let's fix a group, a
cyclic group of order N the group G and let g be some generator of the group
capital G so again I remind you that all that means is, if I look at all powers of
g, then I basically span the entire group capital G. And now let's define the
following function. The function goes from ZN to G and it's defined basically as the
exponentiation to the power of X. Okay, so this maps any element between zero and n-1
to an element of the group capital G simply by raising g, little g to the
appropriate power. And it's kind of obvious that if the discrete log problem
in the group capital G is hard, then in fact f is one way. In fact, the one
wayness of f is the discrete log assumption. So if the discrete log is
hard, f is one way. Now the interesting thing about this one-way functions is it's
got some interesting properties. In particular, if I give you f(x) and f(y)
I claim that it's very easy to compute f(x + y). Even though we have no idea
what x or y are. All we're given is just f(x) and f(y), nevertheless, we can
compute f(x + y). Let me ask you, how would you do that? Well, just by rules of
exponentiation, basically, f(x + y) is simply f(x) times f(y). And again,
this is all done inside the group G. If you're not convinced, simply recall that f(x + y)
is g to the (x + y). Which is simply g to the x times g to the y, which
is exactly what we have here. And this simple property, this simple fact that the
function has this additive property, if you think about it, is exactly what
enables key exchange and public key encryption. So, this additional property
of the one-way function is what enabled all of public key cryptography. So let's
look at our next example the RSA one way function so here we're going to choose two
primes p and q we're going to set N to be p times q then were going to choose e that's
relatively prime to phi(N). And then, we define the functions, and simply as a
function from ZN star to ZN star, simply as f(x) equals x to the e. Okay,
so raising x to the power of e. And again we say that this function is one way,
simply under the RSA assumption. Again, the RSA assumption is the assumption that
this function is one way. And the interesting thing about this function is
that it has properties similar to the one that we saw on the previous slide, namely
the given f(x) and f(y), now we can compute f(x y) as opposed to f(x + y)
So we say that this function has a multiplicative property as opposed to
the additive property on the previous slide. But more importantly this is kind of
not the most interesting thing about this function. The really exciting thing about
this function is it in fact has a trapdoor. In other words there's a secret
key that all of a sudden allows us to invert this function. Even though without
the secret key the function is one way. As far as we know. And this property, I'll
say, the fact that it has a trap door, again, enabled all of public key
cryptography. I'll say that this trap door also makes the RSA function especially
well suited for digital signatures. In week seven, we're gonna see that both the
RSA function and the discrete log functions let us construct digital
signatures. But the RSA function, because it has a trap door, makes it very, very
easy to construct digital signatures from it. And so, in fact, most digital
signatures out there in the world, in fact, rely on the RSA function just
because it's so simple to build digital signatures from it. So again, we see that
this one-way function with the special properties. It has a multiplicative
property and a trap door. Essentially again, enables all of public key crypto. So
to summarize, the reason we are able to build public key cryptography namely, the
reason we're able to do key exchange and public key encryption and so on, is
because we're able to construct one-way functions that have very, very special
properties. In particular, they have these properties that are sometimes called
homomorphic properties, namely they're given f(x) and f(y). We can construct
a f(x + y) or, f(x y), and some functions, like RSA, even have trap
doors, which let us build digital signatures very, very easily. But the main
thing I wanted to show you is that the magic of public key crypto is basically made
possible because of these one-way functions with their special properties. So
that's the end of this module and then in week seven, we'll start with digital signatures.
