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.

Â