0:00

In the last segment, we explained what is a public key encryption system. And we

Â defined what it means for a public key encryption system to be secure. If you

Â remember, we required security against active attacks. And in particular, we

Â defined chosen cipher text security as our goal. This week, we're gonna construct two

Â families of public key encryption systems that are chosen cipher text secure. And in

Â this segment, we're gonna start by constructing public key encryptions from,

Â a concept called a trapdoor permutation. So let's start by defining a

Â general concept called a trapdoor function. So what is a trapdoor function?

Â Well, a trapdoor function basically is a function that goes from some set X to some

Â set Y. And it's really defined by a triple of algorithms. There's a generation

Â algorithm, the function f, and the inverse of the function f. So the generation

Â algorithm, basically what it does when you run it, it will generate a key pair, a

Â public key and a secret key. The public key is gonna define a specific function

Â from the set X to the set Y. And then the secret key is going to define the inverse

Â function now from the set Y to the set X. So the idea is that you can evaluate

Â the function at any point using a public key PK and then you can invert that function

Â using the secret key, SK. So what do I mean by inversion? More precisely, if we

Â look at any public key and secret key pair generated by the key generation algorithm

Â G, then it so happens that if I evaluate the function at the point X, and then I

Â evaluate the inverse at the resulting point, I should get the original point X

Â back. So the picture you should have in your mind, is there is this big set X and

Â this big set Y And then, this function will map any point in X to a point in Y,

Â and this can be done using the public key. So again any point in X can be mapped, to

Â a point in Y. And then if someone has the secret key, then basically they can go in

Â the reverse direction by applying, this secret key sk. So now that we

Â understand what a trapdoor function is, let's define what it means for a trapdoor

Â function to be secure. And so we'll say that this triple, (G, F, F inverse), is secure

Â if in fact this function F(PK, .) is what's called a one way function. And let me

Â explain what a, what is a one way function. The idea is that basically the

Â function can be evaluated at any point, but inverting it is difficult without the

Â secret key SK. So let's define that more precisely. As usual we define that using a

Â game. So here we have our game between the challenger and the adversary. And the game

Â proceeds as follows. Basically the challenger will generate a public key and

Â a secret key. And then they will generate a random X. It will send the public key

Â over to the adversary and then it will evaluate the function at the point X and

Â send the resulting Y also to the adversary. So all the adversary gets to

Â see is just a public key, which defines what the function is, and then he gets to

Â see the image of this function on a random point X and is goal is basically to invert

Â the function at this point Y. Okay, so he outputs some X prime. And we said that the

Â trap door function is secure if the probability that the ad, adversary inverts

Â the given at point y is negligible. In other words, given y the probability that

Â the adversary's able to alter the pre image of y is in fact a negligible

Â probability and if that's true for all efficient algorithms then we say that this

Â trapdor function is secure. So again abstractly, it's a really interesting

Â concept in that you can evaluate the function in the forward direction very

Â easily. But then no one can evaluate the function in the reverse direction unless

Â they have this trapdoor, the secret key SK, which then all of a sudden lets them

Â invert the function very, very easily. So using the concept of a trapdoor function,

Â it's not too difficult to build a public key encryption system, and let me show you how

Â to do it. So here we have we our trap door function, (G, F, and F inverse). The other

Â tool that we are going to need is a symmetric encryption scheme, and I'm going to

Â assume that this encryption scheme is actually secure against active attacks, so in

Â particular I needed to provide authenticated encryption. Notice that the

Â symmetric encryption system takes keys in K and the trapdoor function takes inputs

Â in X. Those are two different sets and so we're also gonna need the hash function.

Â That goes from X to K. In other words, it maps elements in the set X into keys for

Â the symmetric encryption systems. And now once we have these three components, we

Â can actually construct the public key encryption system as follows: so the key

Â generation for the public key encryption system is basically exactly the same as

Â the key generation for the trap door function. So we run G for the trap door

Â function, we get a public key and a secret key. And those are gonna be the public and

Â secret keys for the public key encryption system. And how do we encrypt and decrypt? Let's

Â start with encryption. So the encryption algorithm takes a public key and a message

Â as input. So what it will do is it will generate a random X from the set capital

Â X. It will then apply the trapdoor function to this random X, to obtain Y. So

Â Y is the image of X under the trapdoor function. Then it will go ahead and

Â generate a symmetric key by hashing X. So this is a symmetric key for the symmetric

Â key system. And then finally it encrypts the plain text message 'm' using this key that was

Â just generated. And then it outputs the value Y that it just computed, which is

Â the image of X, along the encryption under the symmetric system of the message M. So

Â that's how encryption works. And I want to emphasize again that the trapdoor function

Â is only applied to this random value X, whereas the message itself is encrypted

Â using a symmetric key system using a key that was derived from the value X that we

Â chose at random. So now that we understand encryption, let's see how to decrypt.

Â While the decryption algorithm takes a secret key as input, and the ciphertext.

Â The ciphertext itself contains two components, the value Y and the value C.

Â So the first step we're gonna do, is we're gonna apply the inverse transformation,

Â the inverse trap door function to the value Y, and that will give us back the

Â original X that was chosen during encryption. So now let me ask you, how do

Â we derive the symmetric decryption key K from this X that we just obtained? Well,

Â so that's an easy question. We basically hash X again. That gives us K just as

Â during encryption. And now that we have this symmetric encryption key we can apply

Â the, the symmetric decryption algorithm to decrypt the ciphertext C. We get the

Â original message M and that's what we output. So, that's how the public key

Â encryption system works were this trap door function is only used for encrypting

Â some sort of a random value X and the actual message is encrypted using the

Â symmetric system. So in pictures here, we have the message M obviously the plain

Â text could be quite large. So, here we have the body of the deciphered text which

Â can be quite long is actually encrypted using the symmetric system. And then again

Â I emphasize that the key for the symmetric system is simply the hash of X.

Â And then the header of ciphertext is simply this application of the trapdoor

Â function to this random X that we picked. And so during decryption what happens is

Â we first decrypt the header to get X and then we decrypt the body using the

Â symmetric system to actually get the original plain text M. So as usual when I

Â show you a system like this, obviously you want to verify that decryption in fact is

Â the inverse of encryption. But more importantly you want to ask why is this

Â system secure. And in fact there's a nice security theorem here that says. That if

Â the trap door function that we started with is secure. In other words, that's a

Â one way function if the adversary doesn't have a secret key. The symmetric

Â encryption system provides authenticated encryption. And the hash function is a

Â random oracle, which simply means that it's a random function from the set X to

Â the set of keys K. So a random oracle is some sort of an idealization of, what a

Â hash function is supposed to be. In practice, of course, when you come to

Â implement a system like this, you would just use, SHA-256, or any of the

Â other hash functions that we discussed in class. So, under those three conditions in

Â fact the system that we just described is chosen cipher text secure so it is CCA

Â secure, the little ro here just denote the fact that security is set in whats called

Â a random oracle model. But, that's a detail that's actually not so important for

Â discussion here, what I want you to remember is that if the trap door function

Â is in fact a secure trap door function. The symmetric encryption system is secure

Â against tampering so it provides authenticated encryption. And H

Â is in some sense a good hash function. It's a random, function, which in practice

Â you would just use SHA-256, then in fact the system that we just showed is CCA

Â secure, is chosen ciphertext secure. I should tell you that there's actually an ISO

Â standard that, defines this mode of encryption, of public encryption. ISO

Â stands for International Standards Organization. So in fact this particular

Â system has actually been standardized, and this is a fine thing to use. I'll refer to

Â this as the ISO encryption in the next few segments. To conclude this segment, I want

Â to warn you about an incorrect way of using a trapdoor function to build a

Â public key encryption system. And in fact this method might be the first thing that

Â comes to mind, and yet it's completely insecure. So let me show you, how not to

Â encrypt using a trapdoor function. Well the first thing that might come to mind

Â is, well, let's apply the trapdoor function directly to the message M. So we

Â encrypt simply by applying a function to the message M, and we decrypt simply by

Â applying F inverse to the ciphertext C to recover the original message M. So

Â functionally, this is in fact, decryption is the inverse of encryption, and yet this

Â is completely insecure for many, many different reasons. The easiest way to see

Â that this is insecure, is that it's simply, this is deterministic encryption.

Â You notice there is no randomness being used here. When we encrypt a message

Â M, and since it is deterministic, it's cannot possibly be

Â semantically secure. But in fact, as I said, when we instantiate this trap door

Â function with particular implementations, for example with the RSA trap door

Â function, then there are many, many attacks that are possible on this

Â particular construction, and so you should never, ever, ever use it, and I'm gonna

Â repeat this throughout this module, and in fact in the next segment I'll show you a

Â number of attacks on this particular implementation. Okay so, what I would like

Â you to remember is that you should be using an encryption system like the ISO

Â standard, and you should never apply the trap door function directly to the message M.

Â Although in the next segment we'll see other ways to encrypt using a trap

Â door function that are also correct, but this particular method is clearly, clearly

Â incorrect. Okay, so now that we understand how to build public key encryption

Â given a trap door function, the next question is how to construct trap door

Â functions, and we're going to do that in the next segment.

Â