Constructions (11 min)

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.