0:00:00.000,0:00:03.574
In the last segment, we saw that the[br]ElGamal public key encryption system is

0:00:03.574,0:00:07.525
chosen cipher text secure under a somewhat[br]strange assumption. In this segment, we're

0:00:07.525,0:00:11.146
gonna look at variants of ElGamal that[br]have a much better chosen cipher text

0:00:11.146,0:00:14.909
security analysis. Now, I should say that[br]over the past decade, there's been a ton

0:00:14.909,0:00:18.766
of research on constructing, public key[br]encryptions that are chosen cipher text

0:00:18.766,0:00:22.387
secure. I actually debated for some time[br]on how to best present this here. And

0:00:22.387,0:00:26.197
finally, I decided to kind of show you a[br]survey of the main results from the last

0:00:26.197,0:00:29.960
decades, specifically as they apply to the[br]ElGamal system. And then, at the end of

0:00:29.960,0:00:33.770
the module, I suggest a number of papers[br]that you can look at for further reading.

0:00:33.770,0:00:38.332
So let me start by reminding you how the[br]ElGamal encryption system works. I'm sure

0:00:38.332,0:00:42.783
by now you all remember how ElGamal works,[br]but just to be safe, let me remind you

0:00:42.783,0:00:47.623
that key generation in ElGamal picks a[br]random generator, a random exponent from ZN

0:00:47.623,0:00:51.963
and then the public key is simply the[br]generator and this element g to the a,

0:00:51.963,0:00:56.332
whereas the secret key is simply the[br]discrete log of h base g. This value A.

0:00:56.332,0:01:01.255
Now the way we encrypt is we pick a random[br]exponent B from ZN. We compute the hash of

0:01:01.255,0:01:05.947
G to the B and H to the B. And I'm gonna[br]remind you that H to the B is the Diffie

0:01:05.947,0:01:10.233
Hellman secret, G to the AB. And then we[br]actually encrypt a message using a

0:01:10.233,0:01:15.156
symmetric encryption system with the key K[br]that's derived from the hash function. And

0:01:15.156,0:01:19.731
finally, the output cipher text is G to[br]the B, and the symmetric cipher text. The

0:01:19.731,0:01:24.654
way we decrypt is you know, as we've seen[br]before basically, by hashing U and the

0:01:24.654,0:01:28.940
Diffie Hellman secrets, decrypting the[br]symmetric system, and outputting the

0:01:28.940,0:01:33.645
message M. Now in the last segment we said[br]that ElGamal is chosen ciphertext secure under

0:01:33.645,0:01:37.881
this funny Interactive Diffie-Hellman[br]assumption. I am not gonna remind you what

0:01:37.881,0:01:42.447
the assumption is here but I'll also say[br]that this theorem kind of raises two very

0:01:42.447,0:01:46.683
natural questions. The first question is[br]can we prove CCA security of

0:01:46.683,0:01:50.864
ElGamal just based on the standard[br]Computational Diffie-Hellman assumption,

0:01:50.864,0:01:55.011
namely the G to the A, G to the B, you[br]can't compute G to the AB. Can we prove

0:01:55.011,0:01:59.259
chosen-ciphertext security just based on[br]that? And the truth's that there are two

0:01:59.259,0:02:03.454
ways to do it. The first option is to use[br]a group where the computational Diffie

0:02:03.454,0:02:07.306
Hellman assumption is hard. But is[br]provably equivalent to the Interactive

0:02:07.306,0:02:11.227
Diffie Hellman assumption. And it turns[br]out it's actually not that hard to

0:02:11.227,0:02:15.147
construct such groups. These groups are[br]called bilinear groups. And in such

0:02:15.147,0:02:19.544
groups, we know that the ElGamal system is[br]chosen cipher text secure, strictly based

0:02:19.544,0:02:23.782
under the Computational Diffie Hellman[br]assumption, at least in the random oracle

0:02:23.782,0:02:28.983
model. I'll tell you that these bi-linear[br]groups are actually constructed from very

0:02:28.983,0:02:33.715
special elliptic curves. So there's a bit[br]more algebraic structure that enables us

0:02:33.715,0:02:38.404
to prove this equivalence of IDH and CDH.[br]But in general, who knows, maybe you don't

0:02:38.404,0:02:42.928
want to use elliptic curve groups, maybe[br]you want to use ZP star for some reason.

0:02:42.928,0:02:47.817
So it's a pretty natural question to ask.[br]Can we change the ElGamal system such that

0:02:47.817,0:02:52.828
chosen ciphertext security of ElGamal now can be proven, directly based on CDH, for any group

0:02:52.828,0:02:57.840
where CDH is hard? [Now with that ??] assuming[br]any additional structure about the group,

0:02:57.840,0:03:02.132
And it turns out the answer is yes. And[br]there's kind of an elegant construction

0:03:02.132,0:03:06.696
called twin ElGamal, so let me show you[br]how twin ElGamal works. It's a very simple

0:03:06.696,0:03:10.607
variation of ElGamal that does the[br]following. Again, in key generation, we

0:03:10.607,0:03:14.954
choose a random generator. But this time,[br]we're gonna choose two exponents, A1 and

0:03:14.954,0:03:19.409
A2 as the secret key. So the secret key is[br]gonna consist of these two exponents, A1

0:03:19.409,0:03:23.783
and A2. You know the public key of course[br]is gonna consist of our generator. And

0:03:23.783,0:03:28.340
then we're gonna release G to the A1 and G[br]to the A2. So remember that in regular

0:03:28.340,0:03:32.840
ElGamal what the public key is simply g[br]to the A and that's it. Here we have two

0:03:32.840,0:03:37.340
exponents A1 and A2 and therefore we, we[br]release both G to the A1 and G to the A2.

0:03:37.340,0:03:42.297
Now the way we encrypt, you'll notice the[br]public key here is one element longer than

0:03:42.297,0:03:47.137
regular ElGamal. The way we encrypt using[br]this public key is actually very similar

0:03:47.137,0:03:51.859
to regular ElGamal. We choose a random B,[br]and now what we'll hash is actually not

0:03:51.859,0:03:56.522
just G to the B and H1 to the B, but,[br]in fact, G to the B, H1 to the B, and H2

0:03:56.522,0:04:01.691
to the B. Okay so we basically hashing[br]three elements instead of two elements and

0:04:01.691,0:04:06.642
then we basically encrypt the message[br]using the derived symmetric encryption key

0:04:06.642,0:04:11.410
and as usual we output g to the b and c as our[br]final ciphertext. How do we decrypt?

0:04:11.410,0:04:16.027
Well, so now the secret key consists of[br]these two exponents, A1 and A2. And the

0:04:16.027,0:04:20.584
cipher text consists of U, and the[br]symmetric cipher text C. So let me ask you

0:04:20.584,0:04:25.501
a puzzle, and see if you can figure out[br]how to derive the symmetric encryption key

0:04:25.501,0:04:31.934
K, just given the secret key and the value[br]U. So it's kind of a cute puzzle and I

0:04:31.934,0:04:37.250
hope everybody worked out, the solution[br]which is basically what we can do is we

0:04:37.250,0:04:42.566
can take U to the power of A1, and that is[br]basically G to the B A1 And U to the A2

0:04:42.566,0:04:48.012
which is G to the B A2. And that basically[br]gives us exactly the same values, as H1 to

0:04:48.012,0:04:53.069
the B and H2 to the B. So this way the[br]decryptor arrives at the same symmetric

0:04:53.069,0:04:58.515
key that the encryptor did. Then he decrypts[br]the ciphertext using the symmetric system

0:04:58.515,0:05:03.389
and finally outputs the message M. So you[br]notice this is a very simple modification

0:05:03.389,0:05:07.802
to regular ElGamal. All we do is we stick[br]one more element to the public key. When

0:05:07.802,0:05:11.888
we do the hashing, we hash one more[br]element, as opposed to just two elements.

0:05:11.888,0:05:16.246
We hash three elements. And similarly, we[br]do doing decryption, and nothing else

0:05:16.246,0:05:20.491
changes. The cipher text is the same[br]length as before, and that's it, Now the

0:05:20.491,0:05:24.647
amazing thing is that this simple[br]modification allows us to now prove chosen

0:05:24.647,0:05:28.640
cipher text security directly based on[br]standard Computational Diffie-Hellman

0:05:28.640,0:05:32.795
assumption, okay? Still we're going to[br]need to assume that we have a symmetric

0:05:32.795,0:05:36.897
encryption system that provides us[br]authenticated encryption and that the hash

0:05:36.897,0:05:41.430
function that we're using is an ideal hash[br]function in what we call a random oracle

0:05:41.430,0:05:45.747
But nevertheless given that, we can[br]prove chosen cipher text security strictly

0:05:45.747,0:05:49.803
based on a Computational Diffie-Hellman[br]assumption. So now what's the cost of this?

0:05:49.803,0:05:53.966
Of course, if you think about this, during[br]encryption and decryption, encryption has

0:05:53.966,0:05:57.418
to do one more exponentiation, and the[br]decryption has to do one more

0:05:57.418,0:06:01.581
exponentiation. So the encryptor now does[br]three exponentiations instead of two, and

0:06:01.581,0:06:05.490
the decryptor does two exponentiations[br]instead of one. So the question is now,

0:06:05.490,0:06:09.965
now it's a philosophical question. Is this[br]extra effort worth it? So you do more work

0:06:09.965,0:06:14.228
during encryption and decryption. And your[br]public key is a little bit bigger, but

0:06:14.228,0:06:18.331
that doesn't really matter. The work[br]during encryption and decryption is more

0:06:18.331,0:06:22.434
significant. And as a result you get[br]chosen ciphertext security based on kind

0:06:22.434,0:06:26.644
of a more natural assumption, namely[br]Computational Diffie-Hellman as opposed to

0:06:26.644,0:06:30.480
these odd-looking Interactive[br]Diffie-Hellman assumption. But is it worth

0:06:30.480,0:06:34.743
it? Kind of the question is are there[br]groups where CDH holds but IDH does not

0:06:34.743,0:06:38.815
hold? If there were such groups, then it[br]would definitely be worth it, because

0:06:38.815,0:06:43.050
those groups, the twin ElGamal would be[br]secure, but the regular ElGamal would not

0:06:43.050,0:06:47.508
be CCA secure. But unfortunately we don't[br]know if there is any such group and in

0:06:47.508,0:06:51.383
fact as far as we know, it's certainly[br]possible that any group where CDH holds,

0:06:51.383,0:06:55.307
IDH also holds. So the answer is, really,[br]we don't know whether the extra cost is

0:06:55.307,0:06:59.530
worth it or not but then nevertheless it's[br]a cute result that shows that if you want

0:06:59.530,0:07:03.256
to achieve chosen ciphertext[br]security directly from CDH, you could do

0:07:03.256,0:07:08.051
it without too many changes to the ElGamal[br]system. The next question is whether we

0:07:08.051,0:07:12.230
can get rid of this assumption that the[br]hash function is an ideal hash function

0:07:12.230,0:07:16.617
mainly that it's a random oracle. And this[br]is actually a huge topic. There's a lot of

0:07:16.617,0:07:20.482
work in this area on how to build[br]efficient public key encryption systems

0:07:20.482,0:07:24.922
that are chosen ciphertext secure without[br]random oracles. This is a very active area

0:07:24.922,0:07:29.192
of research as I said in the past decade[br]and even longer. And I'll mention that as

0:07:29.192,0:07:33.379
it applies to ElGamal, they are basically,[br]again two families of constructions. The

0:07:33.379,0:07:37.515
first construction's a construction that[br]uses these special groups called these

0:07:37.515,0:07:41.599
bilinear groups that I just mentioned[br]before. It turns out the extra structure

0:07:41.599,0:07:45.682
of these bilinear groups allows us to[br]build very efficient chosen ciphertext

0:07:45.682,0:07:50.128
secure systems without referring to random[br]oracles and as I said at the end of the

0:07:50.128,0:07:54.367
module, I point to a number of papers that[br]explain how to do that. This is quite an

0:07:54.367,0:07:58.876
interesting construction. But it will take[br]me several hours to kind of explain how it

0:07:58.876,0:08:03.434
works. The other alternative is actually[br]to use groups where a stronger assumption

0:08:03.434,0:08:07.830
called the Decision Diffie-Hellman assumption[br]holds. Again, I am not gonna define this

0:08:07.830,0:08:11.798
assumption here. I'll just tell you that[br]this assumption actually holds in

0:08:11.798,0:08:16.141
subgroups of ZP star, in particular if we[br]look at the prime order of a subgroup of

0:08:16.141,0:08:19.812
ZP star. The Decision Diffie-Hellman[br]assumption seems to hold in those groups

0:08:19.812,0:08:23.852
and then in those groups we can actually[br]build a variant of ElGamal, called the

0:08:23.852,0:08:27.141
Cramer Shoup system that is chosen[br]ciphertext secure and the Decision

0:08:27.141,0:08:30.665
Diffie-Hellman assumption without random[br]oracles. Again, this is a beautiful,

0:08:30.665,0:08:34.659
beautiful result but again it would take a[br]couple of hours to explain and so I'm not

0:08:34.659,0:08:38.324
gonna do that here. This is probably one[br]of these things that I gonna leave to

0:08:38.324,0:08:42.083
either the advanced topics or to do an[br]advanced course so that we'll do it at a

0:08:42.083,0:08:46.335
later time. But again I points to a paper[br]at the end of the module just in case you

0:08:46.335,0:08:50.626
want to read more about this. So here is a[br]list of papers that provides more reading

0:08:50.626,0:08:54.208
material. So if you wanna read about[br]Diffie Hellman assumptions, I guess I

0:08:54.208,0:08:58.036
wrote a paper about this a long time ago,[br]that talks about various assumptions

0:08:58.036,0:09:01.716
related to, to Diffie Hellman. And in[br]particular, studies the Decision Diffie

0:09:01.716,0:09:05.685
Hellman assumption. And if you wanna learn[br]about how to build chosen ciphertext

0:09:05.685,0:09:10.098
secure system from Decision Diffie-Hellman[br]and assumptions like it. There's a very

0:09:10.098,0:09:14.563
cute paper by Kramer and Shoup back[br]from 2002 that shows how to do it. This is

0:09:14.563,0:09:18.618
again a very highly recommended paper. If[br]you want to learn how to build chosen

0:09:18.618,0:09:22.672
ciphertext security from these[br]bilinear groups, then the paper to read is

0:09:22.672,0:09:26.983
the one, cited here, which actually uses a[br]general mechanism called Identity Based

0:09:26.983,0:09:30.884
Encryption which very surprisingly it[br]turns out to actually gives us chosen

0:09:30.884,0:09:34.638
ciphertext security almost for free.[br]So, once we build identity-based

0:09:34.638,0:09:38.486
encryption chosen ciphertext security falls[br]immediately. And that's covered in this

0:09:38.486,0:09:42.283
paper that I, that I describe her. The[br]Twin Diffie-Hellman construction and its

0:09:42.283,0:09:46.381
proof is described in this paper that I[br]reference here And finally, if you kind of

0:09:46.381,0:09:50.135
want to see a very recent paper. That[br]gives a very general framework for

0:09:50.135,0:09:54.345
building, chosen ciphertext secure systems, using[br]what's called extractable hash proofs that

0:09:54.345,0:09:58.506
is again a nice paper by Hoeteck Wee, that[br]was just recently published. I definitely

0:09:58.506,0:10:02.416
recommend reading it all, all have[br]very, very elegant ideas in them. I wish I

0:10:02.416,0:10:06.426
could cover all of them in the basic[br]course but I'm gonna have to leave some of

0:10:06.426,0:10:10.436
these to the more advanced course or[br]perhaps the more advanced topics at the

0:10:10.436,0:10:14.446
end of this course. Okay, so I'll stop[br]here and in the next segment I'm gonna tie

0:10:14.446,0:10:18.506
ElGamal and RSA encryption[br]together so that you see how the two kind

0:10:18.506,0:10:20.512
of follow from a more general principle.