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.