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.

Â