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.