[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.57,Default,,0000,0000,0000,,In the last segment, we saw that the\NElGamal public key encryption system is
Dialogue: 0,0:00:03.57,0:00:07.52,Default,,0000,0000,0000,,chosen cipher text secure under a somewhat\Nstrange assumption. In this segment, we're
Dialogue: 0,0:00:07.52,0:00:11.15,Default,,0000,0000,0000,,gonna look at variants of ElGamal that\Nhave a much better chosen cipher text
Dialogue: 0,0:00:11.15,0:00:14.91,Default,,0000,0000,0000,,security analysis. Now, I should say that\Nover the past decade, there's been a ton
Dialogue: 0,0:00:14.91,0:00:18.77,Default,,0000,0000,0000,,of research on constructing, public key\Nencryptions that are chosen cipher text
Dialogue: 0,0:00:18.77,0:00:22.39,Default,,0000,0000,0000,,secure. I actually debated for some time\Non how to best present this here. And
Dialogue: 0,0:00:22.39,0:00:26.20,Default,,0000,0000,0000,,finally, I decided to kind of show you a\Nsurvey of the main results from the last
Dialogue: 0,0:00:26.20,0:00:29.96,Default,,0000,0000,0000,,decades, specifically as they apply to the\NElGamal system. And then, at the end of
Dialogue: 0,0:00:29.96,0:00:33.77,Default,,0000,0000,0000,,the module, I suggest a number of papers\Nthat you can look at for further reading.
Dialogue: 0,0:00:33.77,0:00:38.33,Default,,0000,0000,0000,,So let me start by reminding you how the\NElGamal encryption system works. I'm sure
Dialogue: 0,0:00:38.33,0:00:42.78,Default,,0000,0000,0000,,by now you all remember how ElGamal works,\Nbut just to be safe, let me remind you
Dialogue: 0,0:00:42.78,0:00:47.62,Default,,0000,0000,0000,,that key generation in ElGamal picks a\Nrandom generator, a random exponent from ZN
Dialogue: 0,0:00:47.62,0:00:51.96,Default,,0000,0000,0000,,and then the public key is simply the\Ngenerator and this element g to the a,
Dialogue: 0,0:00:51.96,0:00:56.33,Default,,0000,0000,0000,,whereas the secret key is simply the\Ndiscrete log of h base g. This value A.
Dialogue: 0,0:00:56.33,0:01:01.26,Default,,0000,0000,0000,,Now the way we encrypt is we pick a random\Nexponent B from ZN. We compute the hash of
Dialogue: 0,0:01:01.26,0:01:05.95,Default,,0000,0000,0000,,G to the B and H to the B. And I'm gonna\Nremind you that H to the B is the Diffie
Dialogue: 0,0:01:05.95,0:01:10.23,Default,,0000,0000,0000,,Hellman secret, G to the AB. And then we\Nactually encrypt a message using a
Dialogue: 0,0:01:10.23,0:01:15.16,Default,,0000,0000,0000,,symmetric encryption system with the key K\Nthat's derived from the hash function. And
Dialogue: 0,0:01:15.16,0:01:19.73,Default,,0000,0000,0000,,finally, the output cipher text is G to\Nthe B, and the symmetric cipher text. The
Dialogue: 0,0:01:19.73,0:01:24.65,Default,,0000,0000,0000,,way we decrypt is you know, as we've seen\Nbefore basically, by hashing U and the
Dialogue: 0,0:01:24.65,0:01:28.94,Default,,0000,0000,0000,,Diffie Hellman secrets, decrypting the\Nsymmetric system, and outputting the
Dialogue: 0,0:01:28.94,0:01:33.64,Default,,0000,0000,0000,,message M. Now in the last segment we said\Nthat ElGamal is chosen ciphertext secure under
Dialogue: 0,0:01:33.64,0:01:37.88,Default,,0000,0000,0000,,this funny Interactive Diffie-Hellman\Nassumption. I am not gonna remind you what
Dialogue: 0,0:01:37.88,0:01:42.45,Default,,0000,0000,0000,,the assumption is here but I'll also say\Nthat this theorem kind of raises two very
Dialogue: 0,0:01:42.45,0:01:46.68,Default,,0000,0000,0000,,natural questions. The first question is\Ncan we prove CCA security of
Dialogue: 0,0:01:46.68,0:01:50.86,Default,,0000,0000,0000,,ElGamal just based on the standard\NComputational Diffie-Hellman assumption,
Dialogue: 0,0:01:50.86,0:01:55.01,Default,,0000,0000,0000,,namely the G to the A, G to the B, you\Ncan't compute G to the AB. Can we prove
Dialogue: 0,0:01:55.01,0:01:59.26,Default,,0000,0000,0000,,chosen-ciphertext security just based on\Nthat? And the truth's that there are two
Dialogue: 0,0:01:59.26,0:02:03.45,Default,,0000,0000,0000,,ways to do it. The first option is to use\Na group where the computational Diffie
Dialogue: 0,0:02:03.45,0:02:07.31,Default,,0000,0000,0000,,Hellman assumption is hard. But is\Nprovably equivalent to the Interactive
Dialogue: 0,0:02:07.31,0:02:11.23,Default,,0000,0000,0000,,Diffie Hellman assumption. And it turns\Nout it's actually not that hard to
Dialogue: 0,0:02:11.23,0:02:15.15,Default,,0000,0000,0000,,construct such groups. These groups are\Ncalled bilinear groups. And in such
Dialogue: 0,0:02:15.15,0:02:19.54,Default,,0000,0000,0000,,groups, we know that the ElGamal system is\Nchosen cipher text secure, strictly based
Dialogue: 0,0:02:19.54,0:02:23.78,Default,,0000,0000,0000,,under the Computational Diffie Hellman\Nassumption, at least in the random oracle
Dialogue: 0,0:02:23.78,0:02:28.98,Default,,0000,0000,0000,,model. I'll tell you that these bi-linear\Ngroups are actually constructed from very
Dialogue: 0,0:02:28.98,0:02:33.72,Default,,0000,0000,0000,,special elliptic curves. So there's a bit\Nmore algebraic structure that enables us
Dialogue: 0,0:02:33.72,0:02:38.40,Default,,0000,0000,0000,,to prove this equivalence of IDH and CDH.\NBut in general, who knows, maybe you don't
Dialogue: 0,0:02:38.40,0:02:42.93,Default,,0000,0000,0000,,want to use elliptic curve groups, maybe\Nyou want to use ZP star for some reason.
Dialogue: 0,0:02:42.93,0:02:47.82,Default,,0000,0000,0000,,So it's a pretty natural question to ask.\NCan we change the ElGamal system such that
Dialogue: 0,0:02:47.82,0:02:52.83,Default,,0000,0000,0000,,chosen ciphertext security of ElGamal now can be proven, directly based on CDH, for any group
Dialogue: 0,0:02:52.83,0:02:57.84,Default,,0000,0000,0000,,where CDH is hard? [Now with that ??] assuming\Nany additional structure about the group,
Dialogue: 0,0:02:57.84,0:03:02.13,Default,,0000,0000,0000,,And it turns out the answer is yes. And\Nthere's kind of an elegant construction
Dialogue: 0,0:03:02.13,0:03:06.70,Default,,0000,0000,0000,,called twin ElGamal, so let me show you\Nhow twin ElGamal works. It's a very simple
Dialogue: 0,0:03:06.70,0:03:10.61,Default,,0000,0000,0000,,variation of ElGamal that does the\Nfollowing. Again, in key generation, we
Dialogue: 0,0:03:10.61,0:03:14.95,Default,,0000,0000,0000,,choose a random generator. But this time,\Nwe're gonna choose two exponents, A1 and
Dialogue: 0,0:03:14.95,0:03:19.41,Default,,0000,0000,0000,,A2 as the secret key. So the secret key is\Ngonna consist of these two exponents, A1
Dialogue: 0,0:03:19.41,0:03:23.78,Default,,0000,0000,0000,,and A2. You know the public key of course\Nis gonna consist of our generator. And
Dialogue: 0,0:03:23.78,0:03:28.34,Default,,0000,0000,0000,,then we're gonna release G to the A1 and G\Nto the A2. So remember that in regular
Dialogue: 0,0:03:28.34,0:03:32.84,Default,,0000,0000,0000,,ElGamal what the public key is simply g\Nto the A and that's it. Here we have two
Dialogue: 0,0:03:32.84,0:03:37.34,Default,,0000,0000,0000,,exponents A1 and A2 and therefore we, we\Nrelease both G to the A1 and G to the A2.
Dialogue: 0,0:03:37.34,0:03:42.30,Default,,0000,0000,0000,,Now the way we encrypt, you'll notice the\Npublic key here is one element longer than
Dialogue: 0,0:03:42.30,0:03:47.14,Default,,0000,0000,0000,,regular ElGamal. The way we encrypt using\Nthis public key is actually very similar
Dialogue: 0,0:03:47.14,0:03:51.86,Default,,0000,0000,0000,,to regular ElGamal. We choose a random B,\Nand now what we'll hash is actually not
Dialogue: 0,0:03:51.86,0:03:56.52,Default,,0000,0000,0000,,just G to the B and H1 to the B, but,\Nin fact, G to the B, H1 to the B, and H2
Dialogue: 0,0:03:56.52,0:04:01.69,Default,,0000,0000,0000,,to the B. Okay so we basically hashing\Nthree elements instead of two elements and
Dialogue: 0,0:04:01.69,0:04:06.64,Default,,0000,0000,0000,,then we basically encrypt the message\Nusing the derived symmetric encryption key
Dialogue: 0,0:04:06.64,0:04:11.41,Default,,0000,0000,0000,,and as usual we output g to the b and c as our\Nfinal ciphertext. How do we decrypt?
Dialogue: 0,0:04:11.41,0:04:16.03,Default,,0000,0000,0000,,Well, so now the secret key consists of\Nthese two exponents, A1 and A2. And the
Dialogue: 0,0:04:16.03,0:04:20.58,Default,,0000,0000,0000,,cipher text consists of U, and the\Nsymmetric cipher text C. So let me ask you
Dialogue: 0,0:04:20.58,0:04:25.50,Default,,0000,0000,0000,,a puzzle, and see if you can figure out\Nhow to derive the symmetric encryption key
Dialogue: 0,0:04:25.50,0:04:31.93,Default,,0000,0000,0000,,K, just given the secret key and the value\NU. So it's kind of a cute puzzle and I
Dialogue: 0,0:04:31.93,0:04:37.25,Default,,0000,0000,0000,,hope everybody worked out, the solution\Nwhich is basically what we can do is we
Dialogue: 0,0:04:37.25,0:04:42.57,Default,,0000,0000,0000,,can take U to the power of A1, and that is\Nbasically G to the B A1 And U to the A2
Dialogue: 0,0:04:42.57,0:04:48.01,Default,,0000,0000,0000,,which is G to the B A2. And that basically\Ngives us exactly the same values, as H1 to
Dialogue: 0,0:04:48.01,0:04:53.07,Default,,0000,0000,0000,,the B and H2 to the B. So this way the\Ndecryptor arrives at the same symmetric
Dialogue: 0,0:04:53.07,0:04:58.52,Default,,0000,0000,0000,,key that the encryptor did. Then he decrypts\Nthe ciphertext using the symmetric system
Dialogue: 0,0:04:58.52,0:05:03.39,Default,,0000,0000,0000,,and finally outputs the message M. So you\Nnotice this is a very simple modification
Dialogue: 0,0:05:03.39,0:05:07.80,Default,,0000,0000,0000,,to regular ElGamal. All we do is we stick\None more element to the public key. When
Dialogue: 0,0:05:07.80,0:05:11.89,Default,,0000,0000,0000,,we do the hashing, we hash one more\Nelement, as opposed to just two elements.
Dialogue: 0,0:05:11.89,0:05:16.25,Default,,0000,0000,0000,,We hash three elements. And similarly, we\Ndo doing decryption, and nothing else
Dialogue: 0,0:05:16.25,0:05:20.49,Default,,0000,0000,0000,,changes. The cipher text is the same\Nlength as before, and that's it, Now the
Dialogue: 0,0:05:20.49,0:05:24.65,Default,,0000,0000,0000,,amazing thing is that this simple\Nmodification allows us to now prove chosen
Dialogue: 0,0:05:24.65,0:05:28.64,Default,,0000,0000,0000,,cipher text security directly based on\Nstandard Computational Diffie-Hellman
Dialogue: 0,0:05:28.64,0:05:32.80,Default,,0000,0000,0000,,assumption, okay? Still we're going to\Nneed to assume that we have a symmetric
Dialogue: 0,0:05:32.80,0:05:36.90,Default,,0000,0000,0000,,encryption system that provides us\Nauthenticated encryption and that the hash
Dialogue: 0,0:05:36.90,0:05:41.43,Default,,0000,0000,0000,,function that we're using is an ideal hash\Nfunction in what we call a random oracle
Dialogue: 0,0:05:41.43,0:05:45.75,Default,,0000,0000,0000,,But nevertheless given that, we can\Nprove chosen cipher text security strictly
Dialogue: 0,0:05:45.75,0:05:49.80,Default,,0000,0000,0000,,based on a Computational Diffie-Hellman\Nassumption. So now what's the cost of this?
Dialogue: 0,0:05:49.80,0:05:53.97,Default,,0000,0000,0000,,Of course, if you think about this, during\Nencryption and decryption, encryption has
Dialogue: 0,0:05:53.97,0:05:57.42,Default,,0000,0000,0000,,to do one more exponentiation, and the\Ndecryption has to do one more
Dialogue: 0,0:05:57.42,0:06:01.58,Default,,0000,0000,0000,,exponentiation. So the encryptor now does\Nthree exponentiations instead of two, and
Dialogue: 0,0:06:01.58,0:06:05.49,Default,,0000,0000,0000,,the decryptor does two exponentiations\Ninstead of one. So the question is now,
Dialogue: 0,0:06:05.49,0:06:09.96,Default,,0000,0000,0000,,now it's a philosophical question. Is this\Nextra effort worth it? So you do more work
Dialogue: 0,0:06:09.96,0:06:14.23,Default,,0000,0000,0000,,during encryption and decryption. And your\Npublic key is a little bit bigger, but
Dialogue: 0,0:06:14.23,0:06:18.33,Default,,0000,0000,0000,,that doesn't really matter. The work\Nduring encryption and decryption is more
Dialogue: 0,0:06:18.33,0:06:22.43,Default,,0000,0000,0000,,significant. And as a result you get\Nchosen ciphertext security based on kind
Dialogue: 0,0:06:22.43,0:06:26.64,Default,,0000,0000,0000,,of a more natural assumption, namely\NComputational Diffie-Hellman as opposed to
Dialogue: 0,0:06:26.64,0:06:30.48,Default,,0000,0000,0000,,these odd-looking Interactive\NDiffie-Hellman assumption. But is it worth
Dialogue: 0,0:06:30.48,0:06:34.74,Default,,0000,0000,0000,,it? Kind of the question is are there\Ngroups where CDH holds but IDH does not
Dialogue: 0,0:06:34.74,0:06:38.82,Default,,0000,0000,0000,,hold? If there were such groups, then it\Nwould definitely be worth it, because
Dialogue: 0,0:06:38.82,0:06:43.05,Default,,0000,0000,0000,,those groups, the twin ElGamal would be\Nsecure, but the regular ElGamal would not
Dialogue: 0,0:06:43.05,0:06:47.51,Default,,0000,0000,0000,,be CCA secure. But unfortunately we don't\Nknow if there is any such group and in
Dialogue: 0,0:06:47.51,0:06:51.38,Default,,0000,0000,0000,,fact as far as we know, it's certainly\Npossible that any group where CDH holds,
Dialogue: 0,0:06:51.38,0:06:55.31,Default,,0000,0000,0000,,IDH also holds. So the answer is, really,\Nwe don't know whether the extra cost is
Dialogue: 0,0:06:55.31,0:06:59.53,Default,,0000,0000,0000,,worth it or not but then nevertheless it's\Na cute result that shows that if you want
Dialogue: 0,0:06:59.53,0:07:03.26,Default,,0000,0000,0000,,to achieve chosen ciphertext\Nsecurity directly from CDH, you could do
Dialogue: 0,0:07:03.26,0:07:08.05,Default,,0000,0000,0000,,it without too many changes to the ElGamal\Nsystem. The next question is whether we
Dialogue: 0,0:07:08.05,0:07:12.23,Default,,0000,0000,0000,,can get rid of this assumption that the\Nhash function is an ideal hash function
Dialogue: 0,0:07:12.23,0:07:16.62,Default,,0000,0000,0000,,mainly that it's a random oracle. And this\Nis actually a huge topic. There's a lot of
Dialogue: 0,0:07:16.62,0:07:20.48,Default,,0000,0000,0000,,work in this area on how to build\Nefficient public key encryption systems
Dialogue: 0,0:07:20.48,0:07:24.92,Default,,0000,0000,0000,,that are chosen ciphertext secure without\Nrandom oracles. This is a very active area
Dialogue: 0,0:07:24.92,0:07:29.19,Default,,0000,0000,0000,,of research as I said in the past decade\Nand even longer. And I'll mention that as
Dialogue: 0,0:07:29.19,0:07:33.38,Default,,0000,0000,0000,,it applies to ElGamal, they are basically,\Nagain two families of constructions. The
Dialogue: 0,0:07:33.38,0:07:37.52,Default,,0000,0000,0000,,first construction's a construction that\Nuses these special groups called these
Dialogue: 0,0:07:37.52,0:07:41.60,Default,,0000,0000,0000,,bilinear groups that I just mentioned\Nbefore. It turns out the extra structure
Dialogue: 0,0:07:41.60,0:07:45.68,Default,,0000,0000,0000,,of these bilinear groups allows us to\Nbuild very efficient chosen ciphertext
Dialogue: 0,0:07:45.68,0:07:50.13,Default,,0000,0000,0000,,secure systems without referring to random\Noracles and as I said at the end of the
Dialogue: 0,0:07:50.13,0:07:54.37,Default,,0000,0000,0000,,module, I point to a number of papers that\Nexplain how to do that. This is quite an
Dialogue: 0,0:07:54.37,0:07:58.88,Default,,0000,0000,0000,,interesting construction. But it will take\Nme several hours to kind of explain how it
Dialogue: 0,0:07:58.88,0:08:03.43,Default,,0000,0000,0000,,works. The other alternative is actually\Nto use groups where a stronger assumption
Dialogue: 0,0:08:03.43,0:08:07.83,Default,,0000,0000,0000,,called the Decision Diffie-Hellman assumption\Nholds. Again, I am not gonna define this
Dialogue: 0,0:08:07.83,0:08:11.80,Default,,0000,0000,0000,,assumption here. I'll just tell you that\Nthis assumption actually holds in
Dialogue: 0,0:08:11.80,0:08:16.14,Default,,0000,0000,0000,,subgroups of ZP star, in particular if we\Nlook at the prime order of a subgroup of
Dialogue: 0,0:08:16.14,0:08:19.81,Default,,0000,0000,0000,,ZP star. The Decision Diffie-Hellman\Nassumption seems to hold in those groups
Dialogue: 0,0:08:19.81,0:08:23.85,Default,,0000,0000,0000,,and then in those groups we can actually\Nbuild a variant of ElGamal, called the
Dialogue: 0,0:08:23.85,0:08:27.14,Default,,0000,0000,0000,,Cramer Shoup system that is chosen\Nciphertext secure and the Decision
Dialogue: 0,0:08:27.14,0:08:30.66,Default,,0000,0000,0000,,Diffie-Hellman assumption without random\Noracles. Again, this is a beautiful,
Dialogue: 0,0:08:30.66,0:08:34.66,Default,,0000,0000,0000,,beautiful result but again it would take a\Ncouple of hours to explain and so I'm not
Dialogue: 0,0:08:34.66,0:08:38.32,Default,,0000,0000,0000,,gonna do that here. This is probably one\Nof these things that I gonna leave to
Dialogue: 0,0:08:38.32,0:08:42.08,Default,,0000,0000,0000,,either the advanced topics or to do an\Nadvanced course so that we'll do it at a
Dialogue: 0,0:08:42.08,0:08:46.34,Default,,0000,0000,0000,,later time. But again I points to a paper\Nat the end of the module just in case you
Dialogue: 0,0:08:46.34,0:08:50.63,Default,,0000,0000,0000,,want to read more about this. So here is a\Nlist of papers that provides more reading
Dialogue: 0,0:08:50.63,0:08:54.21,Default,,0000,0000,0000,,material. So if you wanna read about\NDiffie Hellman assumptions, I guess I
Dialogue: 0,0:08:54.21,0:08:58.04,Default,,0000,0000,0000,,wrote a paper about this a long time ago,\Nthat talks about various assumptions
Dialogue: 0,0:08:58.04,0:09:01.72,Default,,0000,0000,0000,,related to, to Diffie Hellman. And in\Nparticular, studies the Decision Diffie
Dialogue: 0,0:09:01.72,0:09:05.68,Default,,0000,0000,0000,,Hellman assumption. And if you wanna learn\Nabout how to build chosen ciphertext
Dialogue: 0,0:09:05.68,0:09:10.10,Default,,0000,0000,0000,,secure system from Decision Diffie-Hellman\Nand assumptions like it. There's a very
Dialogue: 0,0:09:10.10,0:09:14.56,Default,,0000,0000,0000,,cute paper by Kramer and Shoup back\Nfrom 2002 that shows how to do it. This is
Dialogue: 0,0:09:14.56,0:09:18.62,Default,,0000,0000,0000,,again a very highly recommended paper. If\Nyou want to learn how to build chosen
Dialogue: 0,0:09:18.62,0:09:22.67,Default,,0000,0000,0000,,ciphertext security from these\Nbilinear groups, then the paper to read is
Dialogue: 0,0:09:22.67,0:09:26.98,Default,,0000,0000,0000,,the one, cited here, which actually uses a\Ngeneral mechanism called Identity Based
Dialogue: 0,0:09:26.98,0:09:30.88,Default,,0000,0000,0000,,Encryption which very surprisingly it\Nturns out to actually gives us chosen
Dialogue: 0,0:09:30.88,0:09:34.64,Default,,0000,0000,0000,,ciphertext security almost for free.\NSo, once we build identity-based
Dialogue: 0,0:09:34.64,0:09:38.49,Default,,0000,0000,0000,,encryption chosen ciphertext security falls\Nimmediately. And that's covered in this
Dialogue: 0,0:09:38.49,0:09:42.28,Default,,0000,0000,0000,,paper that I, that I describe her. The\NTwin Diffie-Hellman construction and its
Dialogue: 0,0:09:42.28,0:09:46.38,Default,,0000,0000,0000,,proof is described in this paper that I\Nreference here And finally, if you kind of
Dialogue: 0,0:09:46.38,0:09:50.14,Default,,0000,0000,0000,,want to see a very recent paper. That\Ngives a very general framework for
Dialogue: 0,0:09:50.14,0:09:54.34,Default,,0000,0000,0000,,building, chosen ciphertext secure systems, using\Nwhat's called extractable hash proofs that
Dialogue: 0,0:09:54.34,0:09:58.51,Default,,0000,0000,0000,,is again a nice paper by Hoeteck Wee, that\Nwas just recently published. I definitely
Dialogue: 0,0:09:58.51,0:10:02.42,Default,,0000,0000,0000,,recommend reading it all, all have\Nvery, very elegant ideas in them. I wish I
Dialogue: 0,0:10:02.42,0:10:06.43,Default,,0000,0000,0000,,could cover all of them in the basic\Ncourse but I'm gonna have to leave some of
Dialogue: 0,0:10:06.43,0:10:10.44,Default,,0000,0000,0000,,these to the more advanced course or\Nperhaps the more advanced topics at the
Dialogue: 0,0:10:10.44,0:10:14.45,Default,,0000,0000,0000,,end of this course. Okay, so I'll stop\Nhere and in the next segment I'm gonna tie
Dialogue: 0,0:10:14.45,0:10:18.51,Default,,0000,0000,0000,,ElGamal and RSA encryption\Ntogether so that you see how the two kind
Dialogue: 0,0:10:18.51,0:10:20.51,Default,,0000,0000,0000,,of follow from a more general principle.