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.