ElGamal Variants With Better Security (11 min)

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.