0:00

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.