0:00:00.000,0:00:03.827
In the last segment, we explained what is[br]a public key encryption system. And we

0:00:03.827,0:00:07.557
defined what it means for a public key[br]encryption system to be secure. If you

0:00:07.557,0:00:11.142
remember, we required security against[br]active attacks. And in particular, we

0:00:11.142,0:00:15.211
defined chosen cipher text security as our[br]goal. This week, we're gonna construct two

0:00:15.211,0:00:19.281
families of public key encryption systems[br]that are chosen cipher text secure. And in

0:00:19.281,0:00:22.914
this segment, we're gonna start by[br]constructing public key encryptions from,

0:00:23.059,0:00:27.124
a concept called a trapdoor[br]permutation. So let's start by defining a

0:00:27.124,0:00:31.064
general concept called a trapdoor[br]function. So what is a trapdoor function?

0:00:31.064,0:00:35.484
Well, a trapdoor function basically is a[br]function that goes from some set X to some

0:00:35.484,0:00:39.585
set Y. And it's really defined by a triple[br]of algorithms. There's a generation

0:00:39.585,0:00:43.685
algorithm, the function f, and the inverse[br]of the function f. So the generation

0:00:43.685,0:00:47.892
algorithm, basically what it does when you[br]run it, it will generate a key pair, a

0:00:47.892,0:00:52.098
public key and a secret key. The public[br]key is gonna define a specific function

0:00:52.098,0:00:56.869
from the set X to the set Y. And then the[br]secret key is going to define the inverse

0:00:56.869,0:01:01.639
function now from the set Y to the set[br]X. So the idea is that you can evaluate

0:01:01.639,0:01:06.588
the function at any point using a public key[br]PK and then you can invert that function

0:01:06.588,0:01:12.443
using the secret key, SK. So what do I[br]mean by inversion? More precisely, if we

0:01:12.443,0:01:17.255
look at any public key and secret key pair[br]generated by the key generation algorithm

0:01:17.255,0:01:21.727
G, then it so happens that if I evaluate[br]the function at the point X, and then I

0:01:21.727,0:01:26.142
evaluate the inverse at the resulting[br]point, I should get the original point X

0:01:26.142,0:01:30.670
back. So the picture you should have in[br]your mind, is there is this big set X and

0:01:30.670,0:01:35.857
this big set Y And then, this function[br]will map any point in X to a point in Y,

0:01:35.857,0:01:41.508
and this can be done using the public key.[br]So again any point in X can be mapped, to

0:01:41.508,0:01:46.897
a point in Y. And then if someone has the[br]secret key, then basically they can go in

0:01:46.897,0:01:53.758
the reverse direction by applying, this[br]secret key sk. So now that we

0:01:53.758,0:01:58.289
understand what a trapdoor function is,[br]let's define what it means for a trapdoor

0:01:58.289,0:02:02.652
function to be secure. And so we'll say[br]that this triple, (G, F, F inverse), is secure

0:02:02.652,0:02:06.903
if in fact this function F(PK, .) is what's[br]called a one way function. And let me

0:02:06.903,0:02:10.986
explain what a, what is a one way[br]function. The idea is that basically the

0:02:10.986,0:02:15.516
function can be evaluated at any point,[br]but inverting it is difficult without the

0:02:15.516,0:02:19.639
secret key SK. So let's define that more[br]precisely. As usual we define that using a

0:02:19.639,0:02:23.764
game. So here we have our game between the[br]challenger and the adversary. And the game

0:02:23.764,0:02:27.496
proceeds as follows. Basically the[br]challenger will generate a public key and

0:02:27.496,0:02:31.622
a secret key. And then they will generate[br]a random X. It will send the public key

0:02:31.622,0:02:36.116
over to the adversary and then it will[br]evaluate the function at the point X and

0:02:36.116,0:02:40.160
send the resulting Y also to the[br]adversary. So all the adversary gets to

0:02:40.160,0:02:44.653
see is just a public key, which defines[br]what the function is, and then he gets to

0:02:44.653,0:02:49.483
see the image of this function on a random[br]point X and is goal is basically to invert

0:02:49.483,0:02:54.097
the function at this point Y. Okay, so he[br]outputs some X prime. And we said that the

0:02:54.097,0:02:58.507
trap door function is secure if the[br]probability that the ad, adversary inverts

0:02:58.507,0:03:03.143
the given at point y is negligible. In[br]other words, given y the probability that

0:03:03.143,0:03:07.271
the adversary's able to alter the pre[br]image of y is in fact a negligible

0:03:07.271,0:03:11.907
probability and if that's true for all[br]efficient algorithms then we say that this

0:03:11.907,0:03:17.882
trapdor function is secure. So again[br]abstractly, it's a really interesting

0:03:17.882,0:03:21.885
concept in that you can evaluate the[br]function in the forward direction very

0:03:21.885,0:03:26.150
easily. But then no one can evaluate the[br]function in the reverse direction unless

0:03:26.150,0:03:30.311
they have this trapdoor, the secret key[br]SK, which then all of a sudden lets them

0:03:30.311,0:03:35.424
invert the function very, very easily. So[br]using the concept of a trapdoor function,

0:03:35.424,0:03:39.552
it's not too difficult to build a public key encryption system, and let me show you how

0:03:39.552,0:03:43.528
to do it. So here we have we our trap door[br]function, (G, F, and F inverse). The other

0:03:43.528,0:03:47.605
tool that we are going to need is a symmetric encryption scheme, and I'm going to

0:03:47.605,0:03:51.531
assume that this encryption scheme is actually[br]secure against active attacks, so in

0:03:51.531,0:03:55.350
particular I needed to provide[br]authenticated encryption. Notice that the

0:03:55.350,0:04:00.726
symmetric encryption system takes keys in[br]K and the trapdoor function takes inputs

0:04:00.726,0:04:05.790
in X. Those are two different sets and so[br]we're also gonna need the hash function.

0:04:05.790,0:04:09.937
That goes from X to K. In other words, it[br]maps elements in the set X into keys for

0:04:09.937,0:04:14.033
the symmetric encryption systems. And now[br]once we have these three components, we

0:04:14.033,0:04:17.821
can actually construct the public key encryption system as follows: so the key

0:04:17.821,0:04:21.764
generation for the public key encryption[br]system is basically exactly the same as

0:04:21.764,0:04:25.655
the key generation for the trap door[br]function. So we run G for the trap door

0:04:25.655,0:04:29.956
function, we get a public key and a secret[br]key. And those are gonna be the public and

0:04:29.956,0:04:34.171
secret keys for the public key encryption[br]system. And how do we encrypt and decrypt? Let's

0:04:34.171,0:04:38.978
start with encryption. So the encryption[br]algorithm takes a public key and a message

0:04:38.978,0:04:43.898
as input. So what it will do is it will[br]generate a random X from the set capital

0:04:43.898,0:04:48.545
X. It will then apply the trapdoor[br]function to this random X, to obtain Y. So

0:04:48.545,0:04:53.130
Y is the image of X under the trapdoor[br]function. Then it will go ahead and

0:04:53.130,0:04:58.272
generate a symmetric key by hashing X. So[br]this is a symmetric key for the symmetric

0:04:58.272,0:05:03.290
key system. And then finally it encrypts[br]the plain text message 'm' using this key that was

0:05:03.290,0:05:08.123
just generated. And then it outputs the[br]value Y that it just computed, which is

0:05:08.123,0:05:13.260
the image of X, along the encryption under[br]the symmetric system of the message M. So

0:05:13.260,0:05:18.366
that's how encryption works. And I want to[br]emphasize again that the trapdoor function

0:05:18.366,0:05:23.112
is only applied to this random value X,[br]whereas the message itself is encrypted

0:05:23.112,0:05:28.098
using a symmetric key system using a key[br]that was derived from the value X that we

0:05:28.098,0:05:32.959
chose at random. So now that we understand[br]encryption, let's see how to decrypt.

0:05:32.959,0:05:37.366
While the decryption algorithm takes a[br]secret key as input, and the ciphertext.

0:05:37.366,0:05:41.551
The ciphertext itself contains two[br]components, the value Y and the value C.

0:05:41.551,0:05:46.070
So the first step we're gonna do, is we're[br]gonna apply the inverse transformation,

0:05:46.070,0:05:50.366
the inverse trap door function to the[br]value Y, and that will give us back the

0:05:50.366,0:05:54.495
original X that was chosen during[br]encryption. So now let me ask you, how do

0:05:54.495,0:06:00.042
we derive the symmetric decryption key K[br]from this X that we just obtained? Well,

0:06:00.042,0:06:04.736
so that's an easy question. We basically[br]hash X again. That gives us K just as

0:06:04.736,0:06:09.372
during encryption. And now that we have[br]this symmetric encryption key we can apply

0:06:09.372,0:06:13.783
the, the symmetric decryption algorithm to[br]decrypt the ciphertext C. We get the

0:06:13.783,0:06:17.741
original message M and that's what we[br]output. So, that's how the public key

0:06:17.741,0:06:22.321
encryption system works were this trap[br]door function is only used for encrypting

0:06:22.321,0:06:26.788
some sort of a random value X and the[br]actual message is encrypted using the

0:06:26.788,0:06:31.244
symmetric system. So in pictures here, we[br]have the message M obviously the plain

0:06:31.244,0:06:35.545
text could be quite large. So, here we[br]have the body of the deciphered text which

0:06:35.545,0:06:39.953
can be quite long is actually encrypted[br]using the symmetric system. And then again

0:06:39.953,0:06:44.039
I emphasize that the key for the[br]symmetric system is simply the hash of X.

0:06:44.039,0:06:48.232
And then the header of ciphertext is simply[br]this application of the trapdoor

0:06:48.232,0:06:52.641
function to this random X that we picked.[br]And so during decryption what happens is

0:06:52.641,0:06:56.888
we first decrypt the header to get X and[br]then we decrypt the body using the

0:06:56.888,0:07:01.829
symmetric system to actually get the[br]original plain text M. So as usual when I

0:07:01.829,0:07:06.542
show you a system like this, obviously you[br]want to verify that decryption in fact is

0:07:06.542,0:07:10.605
the inverse of encryption. But more[br]importantly you want to ask why is this

0:07:10.605,0:07:14.963
system secure. And in fact there's a nice[br]security theorem here that says. That if

0:07:14.963,0:07:18.900
the trap door function that we started[br]with is secure. In other words, that's a

0:07:18.900,0:07:22.634
one way function if the adversary doesn't[br]have a secret key. The symmetric

0:07:22.634,0:07:26.621
encryption system provides authenticated[br]encryption. And the hash function is a

0:07:26.621,0:07:30.558
random oracle, which simply means that[br]it's a random function from the set X to

0:07:30.558,0:07:34.696
the set of keys K. So a random oracle is[br]some sort of an idealization of, what a

0:07:34.696,0:07:38.280
hash function is supposed to be. In[br]practice, of course, when you come to

0:07:38.280,0:07:42.317
implement a system like this, you would[br]just use, SHA-256, or any of the

0:07:42.317,0:07:47.252
other hash functions that we discussed in[br]class. So, under those three conditions in

0:07:47.252,0:07:51.863
fact the system that we just described is[br]chosen cipher text secure so it is CCA

0:07:51.863,0:07:56.416
secure, the little ro here just denote the[br]fact that security is set in whats called

0:07:56.416,0:08:00.572
a random oracle model. But, that's a detail[br]that's actually not so important for

0:08:00.572,0:08:05.012
discussion here, what I want you to[br]remember is that if the trap door function

0:08:05.012,0:08:09.000
is in fact a secure trap door function. The[br]symmetric encryption system is secure

0:08:09.000,0:08:13.017
against tampering so it provides[br]authenticated encryption. And H

0:08:13.017,0:08:17.468
is in some sense a good hash function.[br]It's a random, function, which in practice

0:08:17.468,0:08:22.245
you would just use SHA-256, then in[br]fact the system that we just showed is CCA

0:08:22.245,0:08:27.615
secure, is chosen ciphertext secure. I should[br]tell you that there's actually an ISO

0:08:27.615,0:08:31.752
standard that, defines this mode of[br]encryption, of public encryption. ISO

0:08:31.752,0:08:35.781
stands for International Standards[br]Organization. So in fact this particular

0:08:35.781,0:08:40.456
system has actually been standardized, and[br]this is a fine thing to use. I'll refer to

0:08:40.456,0:08:44.947
this as the ISO encryption in the next few[br]segments. To conclude this segment, I want

0:08:44.947,0:08:48.925
to warn you about an incorrect way of[br]using a trapdoor function to build a

0:08:48.925,0:08:53.328
public key encryption system. And in fact[br]this method might be the first thing that

0:08:53.328,0:08:57.572
comes to mind, and yet it's completely[br]insecure. So let me show you, how not to

0:08:57.572,0:09:01.762
encrypt using a trapdoor function. Well[br]the first thing that might come to mind

0:09:01.762,0:09:05.696
is, well, let's apply the trapdoor[br]function directly to the message M. So we

0:09:05.696,0:09:10.047
encrypt simply by applying a function to[br]the message M, and we decrypt simply by

0:09:10.047,0:09:14.180
applying F inverse to the ciphertext C to[br]recover the original message M. So

0:09:14.180,0:09:18.639
functionally, this is in fact, decryption[br]is the inverse of encryption, and yet this

0:09:18.639,0:09:22.881
is completely insecure for many, many[br]different reasons. The easiest way to see

0:09:22.881,0:09:26.960
that this is insecure, is that it's[br]simply, this is deterministic encryption.

0:09:26.960,0:09:30.944
You notice there is no randomness being[br]used here. When we encrypt a message

0:09:30.944,0:09:34.154
M, and since it is[br]deterministic, it's cannot possibly be

0:09:34.154,0:09:37.948
semantically secure. But in fact, as I[br]said, when we instantiate this trap door

0:09:37.948,0:09:41.644
function with particular implementations,[br]for example with the RSA trap door

0:09:41.644,0:09:44.951
function, then there are many, many[br]attacks that are possible on this

0:09:44.951,0:09:48.794
particular construction, and so you should[br]never, ever, ever use it, and I'm gonna

0:09:48.794,0:09:52.830
repeat this throughout this module, and in[br]fact in the next segment I'll show you a

0:09:52.830,0:09:56.699
number of attacks on this particular[br]implementation. Okay so, what I would like

0:09:56.699,0:10:00.717
you to remember is that you should be[br]using an encryption system like the ISO

0:10:00.717,0:10:04.992
standard, and you should never apply the[br]trap door function directly to the message M.

0:10:04.992,0:10:09.010
Although in the next segment we'll[br]see other ways to encrypt using a trap

0:10:09.010,0:10:13.233
door function that are also correct, but[br]this particular method is clearly, clearly

0:10:13.233,0:10:17.560
incorrect. Okay, so now that we understand[br]how to build public key encryption

0:10:17.560,0:10:21.423
given a trap door function, the next[br]question is how to construct trap door

0:10:21.423,0:10:24.360
functions, and we're going to do that in[br]the next segment.