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.