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.