0:00

In the last segment, we saw that the ElGamal public key encryption system is

chosen cipher text secure under a somewhat strange assumption. In this segment, we're

gonna look at variants of ElGamal that have a much better chosen cipher text

security analysis. Now, I should say that over the past decade, there's been a ton

of research on constructing, public key encryptions that are chosen cipher text

secure. I actually debated for some time on how to best present this here. And

finally, I decided to kind of show you a survey of the main results from the last

decades, specifically as they apply to the ElGamal system. And then, at the end of

the module, I suggest a number of papers that you can look at for further reading.

So let me start by reminding you how the ElGamal encryption system works. I'm sure

by now you all remember how ElGamal works, but just to be safe, let me remind you

that key generation in ElGamal picks a random generator, a random exponent from ZN

and then the public key is simply the generator and this element g to the a,

whereas the secret key is simply the discrete log of h base g. This value A.

Now the way we encrypt is we pick a random exponent B from ZN. We compute the hash of

G to the B and H to the B. And I'm gonna remind you that H to the B is the Diffie

Hellman secret, G to the AB. And then we actually encrypt a message using a

symmetric encryption system with the key K that's derived from the hash function. And

finally, the output cipher text is G to the B, and the symmetric cipher text. The

way we decrypt is you know, as we've seen before basically, by hashing U and the

Diffie Hellman secrets, decrypting the symmetric system, and outputting the

message M. Now in the last segment we said that ElGamal is chosen ciphertext secure under

this funny Interactive Diffie-Hellman assumption. I am not gonna remind you what

the assumption is here but I'll also say that this theorem kind of raises two very

natural questions. The first question is can we prove CCA security of

ElGamal just based on the standard Computational Diffie-Hellman assumption,

namely the G to the A, G to the B, you can't compute G to the AB. Can we prove

chosen-ciphertext security just based on that? And the truth's that there are two

ways to do it. The first option is to use a group where the computational Diffie

Hellman assumption is hard. But is provably equivalent to the Interactive

Diffie Hellman assumption. And it turns out it's actually not that hard to

construct such groups. These groups are called bilinear groups. And in such

groups, we know that the ElGamal system is chosen cipher text secure, strictly based

under the Computational Diffie Hellman assumption, at least in the random oracle

model. I'll tell you that these bi-linear groups are actually constructed from very

special elliptic curves. So there's a bit more algebraic structure that enables us

to prove this equivalence of IDH and CDH. But in general, who knows, maybe you don't

want to use elliptic curve groups, maybe you want to use ZP star for some reason.

So it's a pretty natural question to ask. Can we change the ElGamal system such that

chosen ciphertext security of ElGamal now can be proven, directly based on CDH, for any group

where CDH is hard? [Now with that ??] assuming any additional structure about the group,

And it turns out the answer is yes. And there's kind of an elegant construction

called twin ElGamal, so let me show you how twin ElGamal works. It's a very simple

variation of ElGamal that does the following. Again, in key generation, we

choose a random generator. But this time, we're gonna choose two exponents, A1 and

A2 as the secret key. So the secret key is gonna consist of these two exponents, A1

and A2. You know the public key of course is gonna consist of our generator. And

then we're gonna release G to the A1 and G to the A2. So remember that in regular

ElGamal what the public key is simply g to the A and that's it. Here we have two

exponents A1 and A2 and therefore we, we release both G to the A1 and G to the A2.

Now the way we encrypt, you'll notice the public key here is one element longer than

regular ElGamal. The way we encrypt using this public key is actually very similar

to regular ElGamal. We choose a random B, and now what we'll hash is actually not

just G to the B and H1 to the B, but, in fact, G to the B, H1 to the B, and H2

to the B. Okay so we basically hashing three elements instead of two elements and

then we basically encrypt the message using the derived symmetric encryption key

and as usual we output g to the b and c as our final ciphertext. How do we decrypt?

Well, so now the secret key consists of these two exponents, A1 and A2. And the

cipher text consists of U, and the symmetric cipher text C. So let me ask you

a puzzle, and see if you can figure out how to derive the symmetric encryption key

K, just given the secret key and the value U. So it's kind of a cute puzzle and I

hope everybody worked out, the solution which is basically what we can do is we

can take U to the power of A1, and that is basically G to the B A1 And U to the A2

which is G to the B A2. And that basically gives us exactly the same values, as H1 to

the B and H2 to the B. So this way the decryptor arrives at the same symmetric

key that the encryptor did. Then he decrypts the ciphertext using the symmetric system

and finally outputs the message M. So you notice this is a very simple modification

to regular ElGamal. All we do is we stick one more element to the public key. When

we do the hashing, we hash one more element, as opposed to just two elements.

We hash three elements. And similarly, we do doing decryption, and nothing else

changes. The cipher text is the same length as before, and that's it, Now the

amazing thing is that this simple modification allows us to now prove chosen

cipher text security directly based on standard Computational Diffie-Hellman

assumption, okay? Still we're going to need to assume that we have a symmetric

encryption system that provides us authenticated encryption and that the hash

function that we're using is an ideal hash function in what we call a random oracle

But nevertheless given that, we can prove chosen cipher text security strictly

based on a Computational Diffie-Hellman assumption. So now what's the cost of this?

Of course, if you think about this, during encryption and decryption, encryption has

to do one more exponentiation, and the decryption has to do one more

exponentiation. So the encryptor now does three exponentiations instead of two, and

the decryptor does two exponentiations instead of one. So the question is now,

now it's a philosophical question. Is this extra effort worth it? So you do more work

during encryption and decryption. And your public key is a little bit bigger, but

that doesn't really matter. The work during encryption and decryption is more

significant. And as a result you get chosen ciphertext security based on kind

of a more natural assumption, namely Computational Diffie-Hellman as opposed to

these odd-looking Interactive Diffie-Hellman assumption. But is it worth

it? Kind of the question is are there groups where CDH holds but IDH does not

hold? If there were such groups, then it would definitely be worth it, because

those groups, the twin ElGamal would be secure, but the regular ElGamal would not

be CCA secure. But unfortunately we don't know if there is any such group and in

fact as far as we know, it's certainly possible that any group where CDH holds,

IDH also holds. So the answer is, really, we don't know whether the extra cost is

worth it or not but then nevertheless it's a cute result that shows that if you want

to achieve chosen ciphertext security directly from CDH, you could do

it without too many changes to the ElGamal system. The next question is whether we

can get rid of this assumption that the hash function is an ideal hash function

mainly that it's a random oracle. And this is actually a huge topic. There's a lot of

work in this area on how to build efficient public key encryption systems

that are chosen ciphertext secure without random oracles. This is a very active area

of research as I said in the past decade and even longer. And I'll mention that as

it applies to ElGamal, they are basically, again two families of constructions. The

first construction's a construction that uses these special groups called these

bilinear groups that I just mentioned before. It turns out the extra structure

of these bilinear groups allows us to build very efficient chosen ciphertext

secure systems without referring to random oracles and as I said at the end of the

module, I point to a number of papers that explain how to do that. This is quite an

interesting construction. But it will take me several hours to kind of explain how it

works. The other alternative is actually to use groups where a stronger assumption

called the Decision Diffie-Hellman assumption holds. Again, I am not gonna define this

assumption here. I'll just tell you that this assumption actually holds in

subgroups of ZP star, in particular if we look at the prime order of a subgroup of

ZP star. The Decision Diffie-Hellman assumption seems to hold in those groups

and then in those groups we can actually build a variant of ElGamal, called the

Cramer Shoup system that is chosen ciphertext secure and the Decision

Diffie-Hellman assumption without random oracles. Again, this is a beautiful,

beautiful result but again it would take a couple of hours to explain and so I'm not

gonna do that here. This is probably one of these things that I gonna leave to

either the advanced topics or to do an advanced course so that we'll do it at a

later time. But again I points to a paper at the end of the module just in case you

want to read more about this. So here is a list of papers that provides more reading

material. So if you wanna read about Diffie Hellman assumptions, I guess I

wrote a paper about this a long time ago, that talks about various assumptions

related to, to Diffie Hellman. And in particular, studies the Decision Diffie

Hellman assumption. And if you wanna learn about how to build chosen ciphertext

secure system from Decision Diffie-Hellman and assumptions like it. There's a very

cute paper by Kramer and Shoup back from 2002 that shows how to do it. This is

again a very highly recommended paper. If you want to learn how to build chosen

ciphertext security from these bilinear groups, then the paper to read is

the one, cited here, which actually uses a general mechanism called Identity Based

Encryption which very surprisingly it turns out to actually gives us chosen

ciphertext security almost for free. So, once we build identity-based

encryption chosen ciphertext security falls immediately. And that's covered in this

paper that I, that I describe her. The Twin Diffie-Hellman construction and its

proof is described in this paper that I reference here And finally, if you kind of

want to see a very recent paper. That gives a very general framework for

building, chosen ciphertext secure systems, using what's called extractable hash proofs that

is again a nice paper by Hoeteck Wee, that was just recently published. I definitely

recommend reading it all, all have very, very elegant ideas in them. I wish I

could cover all of them in the basic course but I'm gonna have to leave some of

these to the more advanced course or perhaps the more advanced topics at the

end of this course. Okay, so I'll stop here and in the next segment I'm gonna tie

ElGamal and RSA encryption together so that you see how the two kind

of follow from a more general principle.