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.

Constructions

Cryptography I

Meet the Instructors