[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.83,Default,,0000,0000,0000,,In the last segment, we explained what is\Na public key encryption system. And we
Dialogue: 0,0:00:03.83,0:00:07.56,Default,,0000,0000,0000,,defined what it means for a public key\Nencryption system to be secure. If you
Dialogue: 0,0:00:07.56,0:00:11.14,Default,,0000,0000,0000,,remember, we required security against\Nactive attacks. And in particular, we
Dialogue: 0,0:00:11.14,0:00:15.21,Default,,0000,0000,0000,,defined chosen cipher text security as our\Ngoal. This week, we're gonna construct two
Dialogue: 0,0:00:15.21,0:00:19.28,Default,,0000,0000,0000,,families of public key encryption systems\Nthat are chosen cipher text secure. And in
Dialogue: 0,0:00:19.28,0:00:22.91,Default,,0000,0000,0000,,this segment, we're gonna start by\Nconstructing public key encryptions from,
Dialogue: 0,0:00:23.06,0:00:27.12,Default,,0000,0000,0000,,a concept called a trapdoor\Npermutation. So let's start by defining a
Dialogue: 0,0:00:27.12,0:00:31.06,Default,,0000,0000,0000,,general concept called a trapdoor\Nfunction. So what is a trapdoor function?
Dialogue: 0,0:00:31.06,0:00:35.48,Default,,0000,0000,0000,,Well, a trapdoor function basically is a\Nfunction that goes from some set X to some
Dialogue: 0,0:00:35.48,0:00:39.58,Default,,0000,0000,0000,,set Y. And it's really defined by a triple\Nof algorithms. There's a generation
Dialogue: 0,0:00:39.58,0:00:43.68,Default,,0000,0000,0000,,algorithm, the function f, and the inverse\Nof the function f. So the generation
Dialogue: 0,0:00:43.68,0:00:47.89,Default,,0000,0000,0000,,algorithm, basically what it does when you\Nrun it, it will generate a key pair, a
Dialogue: 0,0:00:47.89,0:00:52.10,Default,,0000,0000,0000,,public key and a secret key. The public\Nkey is gonna define a specific function
Dialogue: 0,0:00:52.10,0:00:56.87,Default,,0000,0000,0000,,from the set X to the set Y. And then the\Nsecret key is going to define the inverse
Dialogue: 0,0:00:56.87,0:01:01.64,Default,,0000,0000,0000,,function now from the set Y to the set\NX. So the idea is that you can evaluate
Dialogue: 0,0:01:01.64,0:01:06.59,Default,,0000,0000,0000,,the function at any point using a public key\NPK and then you can invert that function
Dialogue: 0,0:01:06.59,0:01:12.44,Default,,0000,0000,0000,,using the secret key, SK. So what do I\Nmean by inversion? More precisely, if we
Dialogue: 0,0:01:12.44,0:01:17.26,Default,,0000,0000,0000,,look at any public key and secret key pair\Ngenerated by the key generation algorithm
Dialogue: 0,0:01:17.26,0:01:21.73,Default,,0000,0000,0000,,G, then it so happens that if I evaluate\Nthe function at the point X, and then I
Dialogue: 0,0:01:21.73,0:01:26.14,Default,,0000,0000,0000,,evaluate the inverse at the resulting\Npoint, I should get the original point X
Dialogue: 0,0:01:26.14,0:01:30.67,Default,,0000,0000,0000,,back. So the picture you should have in\Nyour mind, is there is this big set X and
Dialogue: 0,0:01:30.67,0:01:35.86,Default,,0000,0000,0000,,this big set Y And then, this function\Nwill map any point in X to a point in Y,
Dialogue: 0,0:01:35.86,0:01:41.51,Default,,0000,0000,0000,,and this can be done using the public key.\NSo again any point in X can be mapped, to
Dialogue: 0,0:01:41.51,0:01:46.90,Default,,0000,0000,0000,,a point in Y. And then if someone has the\Nsecret key, then basically they can go in
Dialogue: 0,0:01:46.90,0:01:53.76,Default,,0000,0000,0000,,the reverse direction by applying, this\Nsecret key sk. So now that we
Dialogue: 0,0:01:53.76,0:01:58.29,Default,,0000,0000,0000,,understand what a trapdoor function is,\Nlet's define what it means for a trapdoor
Dialogue: 0,0:01:58.29,0:02:02.65,Default,,0000,0000,0000,,function to be secure. And so we'll say\Nthat this triple, (G, F, F inverse), is secure
Dialogue: 0,0:02:02.65,0:02:06.90,Default,,0000,0000,0000,,if in fact this function F(PK, .) is what's\Ncalled a one way function. And let me
Dialogue: 0,0:02:06.90,0:02:10.99,Default,,0000,0000,0000,,explain what a, what is a one way\Nfunction. The idea is that basically the
Dialogue: 0,0:02:10.99,0:02:15.52,Default,,0000,0000,0000,,function can be evaluated at any point,\Nbut inverting it is difficult without the
Dialogue: 0,0:02:15.52,0:02:19.64,Default,,0000,0000,0000,,secret key SK. So let's define that more\Nprecisely. As usual we define that using a
Dialogue: 0,0:02:19.64,0:02:23.76,Default,,0000,0000,0000,,game. So here we have our game between the\Nchallenger and the adversary. And the game
Dialogue: 0,0:02:23.76,0:02:27.50,Default,,0000,0000,0000,,proceeds as follows. Basically the\Nchallenger will generate a public key and
Dialogue: 0,0:02:27.50,0:02:31.62,Default,,0000,0000,0000,,a secret key. And then they will generate\Na random X. It will send the public key
Dialogue: 0,0:02:31.62,0:02:36.12,Default,,0000,0000,0000,,over to the adversary and then it will\Nevaluate the function at the point X and
Dialogue: 0,0:02:36.12,0:02:40.16,Default,,0000,0000,0000,,send the resulting Y also to the\Nadversary. So all the adversary gets to
Dialogue: 0,0:02:40.16,0:02:44.65,Default,,0000,0000,0000,,see is just a public key, which defines\Nwhat the function is, and then he gets to
Dialogue: 0,0:02:44.65,0:02:49.48,Default,,0000,0000,0000,,see the image of this function on a random\Npoint X and is goal is basically to invert
Dialogue: 0,0:02:49.48,0:02:54.10,Default,,0000,0000,0000,,the function at this point Y. Okay, so he\Noutputs some X prime. And we said that the
Dialogue: 0,0:02:54.10,0:02:58.51,Default,,0000,0000,0000,,trap door function is secure if the\Nprobability that the ad, adversary inverts
Dialogue: 0,0:02:58.51,0:03:03.14,Default,,0000,0000,0000,,the given at point y is negligible. In\Nother words, given y the probability that
Dialogue: 0,0:03:03.14,0:03:07.27,Default,,0000,0000,0000,,the adversary's able to alter the pre\Nimage of y is in fact a negligible
Dialogue: 0,0:03:07.27,0:03:11.91,Default,,0000,0000,0000,,probability and if that's true for all\Nefficient algorithms then we say that this
Dialogue: 0,0:03:11.91,0:03:17.88,Default,,0000,0000,0000,,trapdor function is secure. So again\Nabstractly, it's a really interesting
Dialogue: 0,0:03:17.88,0:03:21.88,Default,,0000,0000,0000,,concept in that you can evaluate the\Nfunction in the forward direction very
Dialogue: 0,0:03:21.88,0:03:26.15,Default,,0000,0000,0000,,easily. But then no one can evaluate the\Nfunction in the reverse direction unless
Dialogue: 0,0:03:26.15,0:03:30.31,Default,,0000,0000,0000,,they have this trapdoor, the secret key\NSK, which then all of a sudden lets them
Dialogue: 0,0:03:30.31,0:03:35.42,Default,,0000,0000,0000,,invert the function very, very easily. So\Nusing the concept of a trapdoor function,
Dialogue: 0,0:03:35.42,0:03:39.55,Default,,0000,0000,0000,,it's not too difficult to build a public key encryption system, and let me show you how
Dialogue: 0,0:03:39.55,0:03:43.53,Default,,0000,0000,0000,,to do it. So here we have we our trap door\Nfunction, (G, F, and F inverse). The other
Dialogue: 0,0:03:43.53,0:03:47.60,Default,,0000,0000,0000,,tool that we are going to need is a symmetric encryption scheme, and I'm going to
Dialogue: 0,0:03:47.60,0:03:51.53,Default,,0000,0000,0000,,assume that this encryption scheme is actually\Nsecure against active attacks, so in
Dialogue: 0,0:03:51.53,0:03:55.35,Default,,0000,0000,0000,,particular I needed to provide\Nauthenticated encryption. Notice that the
Dialogue: 0,0:03:55.35,0:04:00.73,Default,,0000,0000,0000,,symmetric encryption system takes keys in\NK and the trapdoor function takes inputs
Dialogue: 0,0:04:00.73,0:04:05.79,Default,,0000,0000,0000,,in X. Those are two different sets and so\Nwe're also gonna need the hash function.
Dialogue: 0,0:04:05.79,0:04:09.94,Default,,0000,0000,0000,,That goes from X to K. In other words, it\Nmaps elements in the set X into keys for
Dialogue: 0,0:04:09.94,0:04:14.03,Default,,0000,0000,0000,,the symmetric encryption systems. And now\Nonce we have these three components, we
Dialogue: 0,0:04:14.03,0:04:17.82,Default,,0000,0000,0000,,can actually construct the public key encryption system as follows: so the key
Dialogue: 0,0:04:17.82,0:04:21.76,Default,,0000,0000,0000,,generation for the public key encryption\Nsystem is basically exactly the same as
Dialogue: 0,0:04:21.76,0:04:25.66,Default,,0000,0000,0000,,the key generation for the trap door\Nfunction. So we run G for the trap door
Dialogue: 0,0:04:25.66,0:04:29.96,Default,,0000,0000,0000,,function, we get a public key and a secret\Nkey. And those are gonna be the public and
Dialogue: 0,0:04:29.96,0:04:34.17,Default,,0000,0000,0000,,secret keys for the public key encryption\Nsystem. And how do we encrypt and decrypt? Let's
Dialogue: 0,0:04:34.17,0:04:38.98,Default,,0000,0000,0000,,start with encryption. So the encryption\Nalgorithm takes a public key and a message
Dialogue: 0,0:04:38.98,0:04:43.90,Default,,0000,0000,0000,,as input. So what it will do is it will\Ngenerate a random X from the set capital
Dialogue: 0,0:04:43.90,0:04:48.54,Default,,0000,0000,0000,,X. It will then apply the trapdoor\Nfunction to this random X, to obtain Y. So
Dialogue: 0,0:04:48.54,0:04:53.13,Default,,0000,0000,0000,,Y is the image of X under the trapdoor\Nfunction. Then it will go ahead and
Dialogue: 0,0:04:53.13,0:04:58.27,Default,,0000,0000,0000,,generate a symmetric key by hashing X. So\Nthis is a symmetric key for the symmetric
Dialogue: 0,0:04:58.27,0:05:03.29,Default,,0000,0000,0000,,key system. And then finally it encrypts\Nthe plain text message 'm' using this key that was
Dialogue: 0,0:05:03.29,0:05:08.12,Default,,0000,0000,0000,,just generated. And then it outputs the\Nvalue Y that it just computed, which is
Dialogue: 0,0:05:08.12,0:05:13.26,Default,,0000,0000,0000,,the image of X, along the encryption under\Nthe symmetric system of the message M. So
Dialogue: 0,0:05:13.26,0:05:18.37,Default,,0000,0000,0000,,that's how encryption works. And I want to\Nemphasize again that the trapdoor function
Dialogue: 0,0:05:18.37,0:05:23.11,Default,,0000,0000,0000,,is only applied to this random value X,\Nwhereas the message itself is encrypted
Dialogue: 0,0:05:23.11,0:05:28.10,Default,,0000,0000,0000,,using a symmetric key system using a key\Nthat was derived from the value X that we
Dialogue: 0,0:05:28.10,0:05:32.96,Default,,0000,0000,0000,,chose at random. So now that we understand\Nencryption, let's see how to decrypt.
Dialogue: 0,0:05:32.96,0:05:37.37,Default,,0000,0000,0000,,While the decryption algorithm takes a\Nsecret key as input, and the ciphertext.
Dialogue: 0,0:05:37.37,0:05:41.55,Default,,0000,0000,0000,,The ciphertext itself contains two\Ncomponents, the value Y and the value C.
Dialogue: 0,0:05:41.55,0:05:46.07,Default,,0000,0000,0000,,So the first step we're gonna do, is we're\Ngonna apply the inverse transformation,
Dialogue: 0,0:05:46.07,0:05:50.37,Default,,0000,0000,0000,,the inverse trap door function to the\Nvalue Y, and that will give us back the
Dialogue: 0,0:05:50.37,0:05:54.50,Default,,0000,0000,0000,,original X that was chosen during\Nencryption. So now let me ask you, how do
Dialogue: 0,0:05:54.50,0:06:00.04,Default,,0000,0000,0000,,we derive the symmetric decryption key K\Nfrom this X that we just obtained? Well,
Dialogue: 0,0:06:00.04,0:06:04.74,Default,,0000,0000,0000,,so that's an easy question. We basically\Nhash X again. That gives us K just as
Dialogue: 0,0:06:04.74,0:06:09.37,Default,,0000,0000,0000,,during encryption. And now that we have\Nthis symmetric encryption key we can apply
Dialogue: 0,0:06:09.37,0:06:13.78,Default,,0000,0000,0000,,the, the symmetric decryption algorithm to\Ndecrypt the ciphertext C. We get the
Dialogue: 0,0:06:13.78,0:06:17.74,Default,,0000,0000,0000,,original message M and that's what we\Noutput. So, that's how the public key
Dialogue: 0,0:06:17.74,0:06:22.32,Default,,0000,0000,0000,,encryption system works were this trap\Ndoor function is only used for encrypting
Dialogue: 0,0:06:22.32,0:06:26.79,Default,,0000,0000,0000,,some sort of a random value X and the\Nactual message is encrypted using the
Dialogue: 0,0:06:26.79,0:06:31.24,Default,,0000,0000,0000,,symmetric system. So in pictures here, we\Nhave the message M obviously the plain
Dialogue: 0,0:06:31.24,0:06:35.54,Default,,0000,0000,0000,,text could be quite large. So, here we\Nhave the body of the deciphered text which
Dialogue: 0,0:06:35.54,0:06:39.95,Default,,0000,0000,0000,,can be quite long is actually encrypted\Nusing the symmetric system. And then again
Dialogue: 0,0:06:39.95,0:06:44.04,Default,,0000,0000,0000,,I emphasize that the key for the\Nsymmetric system is simply the hash of X.
Dialogue: 0,0:06:44.04,0:06:48.23,Default,,0000,0000,0000,,And then the header of ciphertext is simply\Nthis application of the trapdoor
Dialogue: 0,0:06:48.23,0:06:52.64,Default,,0000,0000,0000,,function to this random X that we picked.\NAnd so during decryption what happens is
Dialogue: 0,0:06:52.64,0:06:56.89,Default,,0000,0000,0000,,we first decrypt the header to get X and\Nthen we decrypt the body using the
Dialogue: 0,0:06:56.89,0:07:01.83,Default,,0000,0000,0000,,symmetric system to actually get the\Noriginal plain text M. So as usual when I
Dialogue: 0,0:07:01.83,0:07:06.54,Default,,0000,0000,0000,,show you a system like this, obviously you\Nwant to verify that decryption in fact is
Dialogue: 0,0:07:06.54,0:07:10.60,Default,,0000,0000,0000,,the inverse of encryption. But more\Nimportantly you want to ask why is this
Dialogue: 0,0:07:10.60,0:07:14.96,Default,,0000,0000,0000,,system secure. And in fact there's a nice\Nsecurity theorem here that says. That if
Dialogue: 0,0:07:14.96,0:07:18.90,Default,,0000,0000,0000,,the trap door function that we started\Nwith is secure. In other words, that's a
Dialogue: 0,0:07:18.90,0:07:22.63,Default,,0000,0000,0000,,one way function if the adversary doesn't\Nhave a secret key. The symmetric
Dialogue: 0,0:07:22.63,0:07:26.62,Default,,0000,0000,0000,,encryption system provides authenticated\Nencryption. And the hash function is a
Dialogue: 0,0:07:26.62,0:07:30.56,Default,,0000,0000,0000,,random oracle, which simply means that\Nit's a random function from the set X to
Dialogue: 0,0:07:30.56,0:07:34.70,Default,,0000,0000,0000,,the set of keys K. So a random oracle is\Nsome sort of an idealization of, what a
Dialogue: 0,0:07:34.70,0:07:38.28,Default,,0000,0000,0000,,hash function is supposed to be. In\Npractice, of course, when you come to
Dialogue: 0,0:07:38.28,0:07:42.32,Default,,0000,0000,0000,,implement a system like this, you would\Njust use, SHA-256, or any of the
Dialogue: 0,0:07:42.32,0:07:47.25,Default,,0000,0000,0000,,other hash functions that we discussed in\Nclass. So, under those three conditions in
Dialogue: 0,0:07:47.25,0:07:51.86,Default,,0000,0000,0000,,fact the system that we just described is\Nchosen cipher text secure so it is CCA
Dialogue: 0,0:07:51.86,0:07:56.42,Default,,0000,0000,0000,,secure, the little ro here just denote the\Nfact that security is set in whats called
Dialogue: 0,0:07:56.42,0:08:00.57,Default,,0000,0000,0000,,a random oracle model. But, that's a detail\Nthat's actually not so important for
Dialogue: 0,0:08:00.57,0:08:05.01,Default,,0000,0000,0000,,discussion here, what I want you to\Nremember is that if the trap door function
Dialogue: 0,0:08:05.01,0:08:09.00,Default,,0000,0000,0000,,is in fact a secure trap door function. The\Nsymmetric encryption system is secure
Dialogue: 0,0:08:09.00,0:08:13.02,Default,,0000,0000,0000,,against tampering so it provides\Nauthenticated encryption. And H
Dialogue: 0,0:08:13.02,0:08:17.47,Default,,0000,0000,0000,,is in some sense a good hash function.\NIt's a random, function, which in practice
Dialogue: 0,0:08:17.47,0:08:22.24,Default,,0000,0000,0000,,you would just use SHA-256, then in\Nfact the system that we just showed is CCA
Dialogue: 0,0:08:22.24,0:08:27.62,Default,,0000,0000,0000,,secure, is chosen ciphertext secure. I should\Ntell you that there's actually an ISO
Dialogue: 0,0:08:27.62,0:08:31.75,Default,,0000,0000,0000,,standard that, defines this mode of\Nencryption, of public encryption. ISO
Dialogue: 0,0:08:31.75,0:08:35.78,Default,,0000,0000,0000,,stands for International Standards\NOrganization. So in fact this particular
Dialogue: 0,0:08:35.78,0:08:40.46,Default,,0000,0000,0000,,system has actually been standardized, and\Nthis is a fine thing to use. I'll refer to
Dialogue: 0,0:08:40.46,0:08:44.95,Default,,0000,0000,0000,,this as the ISO encryption in the next few\Nsegments. To conclude this segment, I want
Dialogue: 0,0:08:44.95,0:08:48.92,Default,,0000,0000,0000,,to warn you about an incorrect way of\Nusing a trapdoor function to build a
Dialogue: 0,0:08:48.92,0:08:53.33,Default,,0000,0000,0000,,public key encryption system. And in fact\Nthis method might be the first thing that
Dialogue: 0,0:08:53.33,0:08:57.57,Default,,0000,0000,0000,,comes to mind, and yet it's completely\Ninsecure. So let me show you, how not to
Dialogue: 0,0:08:57.57,0:09:01.76,Default,,0000,0000,0000,,encrypt using a trapdoor function. Well\Nthe first thing that might come to mind
Dialogue: 0,0:09:01.76,0:09:05.70,Default,,0000,0000,0000,,is, well, let's apply the trapdoor\Nfunction directly to the message M. So we
Dialogue: 0,0:09:05.70,0:09:10.05,Default,,0000,0000,0000,,encrypt simply by applying a function to\Nthe message M, and we decrypt simply by
Dialogue: 0,0:09:10.05,0:09:14.18,Default,,0000,0000,0000,,applying F inverse to the ciphertext C to\Nrecover the original message M. So
Dialogue: 0,0:09:14.18,0:09:18.64,Default,,0000,0000,0000,,functionally, this is in fact, decryption\Nis the inverse of encryption, and yet this
Dialogue: 0,0:09:18.64,0:09:22.88,Default,,0000,0000,0000,,is completely insecure for many, many\Ndifferent reasons. The easiest way to see
Dialogue: 0,0:09:22.88,0:09:26.96,Default,,0000,0000,0000,,that this is insecure, is that it's\Nsimply, this is deterministic encryption.
Dialogue: 0,0:09:26.96,0:09:30.94,Default,,0000,0000,0000,,You notice there is no randomness being\Nused here. When we encrypt a message
Dialogue: 0,0:09:30.94,0:09:34.15,Default,,0000,0000,0000,,M, and since it is\Ndeterministic, it's cannot possibly be
Dialogue: 0,0:09:34.15,0:09:37.95,Default,,0000,0000,0000,,semantically secure. But in fact, as I\Nsaid, when we instantiate this trap door
Dialogue: 0,0:09:37.95,0:09:41.64,Default,,0000,0000,0000,,function with particular implementations,\Nfor example with the RSA trap door
Dialogue: 0,0:09:41.64,0:09:44.95,Default,,0000,0000,0000,,function, then there are many, many\Nattacks that are possible on this
Dialogue: 0,0:09:44.95,0:09:48.79,Default,,0000,0000,0000,,particular construction, and so you should\Nnever, ever, ever use it, and I'm gonna
Dialogue: 0,0:09:48.79,0:09:52.83,Default,,0000,0000,0000,,repeat this throughout this module, and in\Nfact in the next segment I'll show you a
Dialogue: 0,0:09:52.83,0:09:56.70,Default,,0000,0000,0000,,number of attacks on this particular\Nimplementation. Okay so, what I would like
Dialogue: 0,0:09:56.70,0:10:00.72,Default,,0000,0000,0000,,you to remember is that you should be\Nusing an encryption system like the ISO
Dialogue: 0,0:10:00.72,0:10:04.99,Default,,0000,0000,0000,,standard, and you should never apply the\Ntrap door function directly to the message M.
Dialogue: 0,0:10:04.99,0:10:09.01,Default,,0000,0000,0000,,Although in the next segment we'll\Nsee other ways to encrypt using a trap
Dialogue: 0,0:10:09.01,0:10:13.23,Default,,0000,0000,0000,,door function that are also correct, but\Nthis particular method is clearly, clearly
Dialogue: 0,0:10:13.23,0:10:17.56,Default,,0000,0000,0000,,incorrect. Okay, so now that we understand\Nhow to build public key encryption
Dialogue: 0,0:10:17.56,0:10:21.42,Default,,0000,0000,0000,,given a trap door function, the next\Nquestion is how to construct trap door
Dialogue: 0,0:10:21.42,0:10:24.36,Default,,0000,0000,0000,,functions, and we're going to do that in\Nthe next segment.