ElGamal Security (14 min)

In this segment, we're gonna study the
security of the ElGamal public key

encryption system. So let me remind you
that when we first presented the

Diffie-Hellman protocol, we said that the
security is based on the assumption that

says that given G, G to the A, G to the B,
it's difficult to compute the

Diffie-Hellman secret, G to the AB. This
is basically what the attacker has to do.

He sees Alice's contribution. He sees
Bob's contribution and then his goal is to

figure out what the Diffie-Hellman secret
is. And we said that this problem is

difficult. The statement that the problem
is difficult is what's called the

computational Diffie-Hellman assumption.
So, let's take this assumption more

precisely. So, as usual we're going to
look at a finite cyclic group of order N,

so G is some group, in your head you should be
thinking ZP star, but there could

be other groups, for example, like an ellipctic curve group. And then we say that

the computational Diffie-Hellman
assumption. I've often used the shorthand

CDH for Computational Diffie Hellman.
We'll say this assumption holds in G if

the following condition holds, namely for
all efficient algorithms. If we choose a

random generator, and then we choose
random exponents A, B in ZN. Then when

we give the algorithm G, G to the A, and G
to the B, the probability that the

algorithm will produce the Diffie Hellman
secret is negligible. If this is true for

all efficient algorithms, then we say that
the CDH assumption holds for G. CDH, as I

said, stands for Computational Diffie
Hellman. As it turns out, this assumption

is not ideal for analyzing the security of
the ElGamal system. And instead I'm gonna

go ahead and make a slightly stronger
assumption called a hash Diffie-Hellman

assumption. Okay. So what is hash
Diffie-Hellman assumption? Again, we are

focusing on a particular group G and now
we're also gonna introduce a hash function

H that maps pairs of elements in G into
the key space of some symmetric encryption

system. And then we say that the hash
Diffie-Hellman a ssumption, or HDH for

short, holds for this pair, G comma H for
the group in the hash function if the

following is true. Basically, if I choose
a random generator and then I choose

random exponents A and B in ZN and then I
also choose a random R and K, then the

following distributions are
computationally indistinguishable. That

is, if I give you G, G to the A, G to the
B, and then this hash value, this should

look familiar to you. This is the hash
value that's used in the ElGamal system to

derive the symmetric encryption key. What
we're saying is that this distribution is

indistinguishable from a distribution
where you're also given. G, G to the A, G

to the B. But now, instead of giving the
hash, you're given just really random key.

So what this assumption says is that the
symmetric key that was derived during

encryption in the ElGamal system,
essentially is indistinguishable from a

truly random key that is derived
independently from the rest of the

parameters of the system. It's a truly
independent random key, looks basically

the same as the key that we used, to
derive from the G to the A and the G to

the B. Now I'd like to point out that the
Hash Diffie-Hellman assumption is actually

a stronger assumption than the
Computational Diffie-Hellman assumption.

The way to see that is using the contra
positive, that is suppose the

Computational Diffie-Hellman assumption
happens to be easy in the group G. Then I

claim that in fact the Hash Diffie-Hellman
assumption is also easy in the group G. In

fact, I'll say for G, H and this is true
in fact for all hash functions where the

image of the hash function. It contains at
least two elements. In other words all I

want to say is that the Hash Diffie-Hellman assumption
and it's easy for all

hash functions to go match everything to a
single point. Which is true for almost all

hash functions of interest to us. So
actually, this is a really simple

statement to prove. Basically, if the
Computational Diffie-Hellman assumption is easy, what that

says is that, given G to the A and G to the B, I can actually calculate G to the AB

myself. Cuz I know the hash function H, I
can calculate this complete value here. So

if you give me a tuple that's
sampled from the left or sampled from the

right. I can very easily tell where it's
from. If it's sampled from the left, then

once I've calculated G to the AB myself, I
can just test that the last element in the

tuple is, in fact, the hash of G to
the B and G to the AB. If it is, I know

the sample is from the left. If it isn't,
I know the sample is from the right. Okay,

so this gives me pretty high advantage, in
distinguishing these two distributions. So

CDH is easy, it's very easy to see that
these distributions are distinguishable.

And this basically says that if the Hash
Diffie-Hellman is in fact hard, then CDH

must also be hard. Which then we say, that
therefore the Hash Diffie-Hellman is a

stronger assumption. There might be group
where CDH is hard, but HDH is not hard.

Okay. So we say HDH is a
stronger assumption. If you found this

discussion of weak assumption versus
strong assumption confusing, it's not

really that important, it's fine to ignore
it. The important thing that I want to

show you is in fact that the Hash
Diffie-Hellman assumption is sufficient to

prove the semantic security of the ElGamal
system. Before we do that let me quickly

ask you the following puzzle just to make
sure the Hash Diffie-Hellman assumption is

clear. So imagine our key space is {0, 1} to the 128. So 128 bit strings and our

hash function will map pairs of group
elements into this 128 byte strings.

Suppose it so happens that we chose a hash
function Such that it always outputs

strings that begin with zero. In other
words, of the 128 bit strings the most

significant bit of the output is always
zero. If we chose such a hash function,

does the Hash Diffie-Hellman assumption
hold for this pair, G comma H. So the

answer is no it doesn't hold. And the
reason is because it now very easy to

distinguish the two distributions that we
have here. The distribution on the left

an the distribution on the right. And the
way you would distinguish the two is

basically if I choose a truly random
element in K, in {0, 1} to the 128,

then mostly it can very well be zero with
probability one half. However, the tuple

that's given to me is chosen from the left
distribution, then the most significant

bit of the hash will always be zero and
therefore if I see zero, I'm gonna say the

distribution is a distribution on the
left. If I see one, I'm gonna say the

distribution is a distribution on the
right. That will give me advantage one

half in distinguishing these two
distributions. And so as a result, the

Hash Diffie-Hillman assumption is false in
this case. So clearly you could see that,

even though CDH might be hard in a certain
group G, if you choose a bad hash

function, then HDH will not hold for the
pair G comma H. Okay. But suppose it so

happens that we choose a group G and a
hash function H for which the Hash Diffie

Hellman assumption holds. And in fact, if
you choose the hash function to be just

SHA-256, for all we know, the Hash
Diffie Hellman assumption holds in the

group ZP star, and holds in elliptic curve
groups. My goal then is to show you that

ElGamal is semantically secure under
the Hash Diffie-Hellman assumption. So let me

quickly remind you how theElGamal
system works. While we're gonna choose a

random generator G, we're gonna choose a
random 'a' in ZN, the public key is

gonna be G, and G to the A, the secret key
is simply gonna be A. And now here I wrote

shorthand for the ElGamal encryption.
Basically, what to encrypt, what we do is

we choose a random B. We hash G as being H
to the B. Remember this H to the B is the

value G to the AB. This is the Diffie
Hellman secret. The hash function gave us

a symmetric encryption key K. We encrypt
the message with K, and we output G to the

B and the symmetric cipher text. To
decrypt we have to value U, and the Diffie

Hellman secret, G to the A. To derive a
symmetric key, we decrypt the cipher text.

And then we output the plaintext message m. So let's see how to argue that,

in fact, ElGamal is semantically secure under
this Hash Diffie-Hillman assumption is

fairly simple. So well we have to argue,
remember we had, in semantic security, we

have these two experiments. One
experiment, the attacker is given the

encryption of m0. In the other experiment,
the attacker is given the encryption of m1.

So I wrote the two experiments here. Here
you notice that the attacker starts by

sending off the public key to the
adversary. The adversary then chooses two

equal length messages m0 and m1. And then
if he gets the ElGamal encryption of M0,

and a kind of rough shorthand for what
ElGamal ciphertext is, okay? Similarly, in

encryption one, he simply gets the
encryption of M1 instead of M0, and

everything else is the same about these
two experiments. Now, because of the Hash

Diffie-Hellman assumption, we know that
even though the attacker got to see G, G

to the a and G to the b, we know that the
output of the hash of G to the b, G to the

ab is indistinguishable from random.
Therefore, if we replace the actual hash

function by a truly generated random key K
that's independent of everything else, by

the Hash Diffie-Hellman assumption, the
attacker can't distinguish these two

games. And again, it's a simple exercise
for you to show that if he could

distinguish these two games, then he would
break the Hash Diffie-Hellman assumption.

But then the same is true for experiment
one. The attacker also could not

distinguish the output of the hash
function from a truly random key, that was

used the generate the challenge cipher
text. Okay. So now basically we look at

these two experiments and we realize that,
wait a minute, what's going on in these

two experiments? Basically everything is
the same except in one experiment, the

attacker gets the encryption under
a symmetric encryption system of m0. In the

other one, he gets the encryption under a
symmetric encryption system of m1 and the

key is chosen at random independently over
everything else. So by the fact that the

symmetric encryption system is
semantically secure, these two games are

indistinguishable. If they were
distinguishable, then the attacker could

break the semantic security of this
symmetric encryption system. So now we

kinda prove this, you know, this chain of
equivalences. And that proves that the

original games, in fact, are
indistinguishable, computationally

indistinguishable. And therefore, the
ElGamal system is semantically secure.

Okay so it's like I said a very simple
proof by pictures and you can make this

into a rigorous proof without too much
work. But semantic security isn't enough,

what we really want is chosen ciphertext
security, and the question is ElGamal chosen ciphertext

secure? So it turns out to prove the
chosen ciphertext security of ElGamal we

actually need a stronger assumption, Hash Diffie-Hellman or Computational Diffie-Hellman

are actually not enough to prove
chosen ciphertext security of the system as far

as we know. So to prove chosen-ciphertext
security, I'm going to introduce a new

assumption called Interactive Diffie
Hellman assumption. And actually,

technically we really don't like this
assumption. And we're going to try to get

rid of this, later on. But for now, we
just want to analyze the security of the

basic ElGamal system against chosen
ciphertext attack. So to argue that it is

chosen ciphertext secure, here is what the
assumption says. Basically the challenger

starts, you know, plays a game with the
adversary, he generates a random G,

generates two exponents, and then he says
to the adversary as usual, G, G to the a

and G to the b. Now the adversary's goal
is basically to figure out the

Diffie-Helmman's secrets, mainly g to the
ab. He outputs the value of V and he wins

the game if V happens to be equal to G to
the AB. So, so far this looks identical to

the Computational Diffie-Hellman assumption,
there's no difference - this is

the Computational Diffie-Hellman assumption
except in Interactive Diffie-Hellman would

give the attacker a little bit more power.
So because the attacker has more power,

it's harder to satisfy the assumption,
which is why we say that this assumption

is stronger than Computational
Diffie-Hellman. Now what is this power to be

given? We are given the ability to make
queries. In particular, he gets to submit

two elements from the group G, so U1, V1
disappear from the group G. And then he's

told whether U1 to the A is equal to V1,
so he gets one. If you wanted the A equals

to V1 get zero, otherwise it's kind of a
bizarre type of query. What, how does it

be possibly help the attacker? But it
turns out we need to be able to answer

these types of queries to the adversary in
order to be able to prove chosen

ciphertext security. And in fact, he can
do these type of queries again and again

and again. So he can issue as many
queries like these as he wants and then the

assumption says that despite all these
queries he still can't figure out the

Diffie-Hellman secret, namely despite
making all these queries, the probability

that he outputs the
Diffie-Hellman secret is negligible. Okay.

So clearly if this assumption holds, that the Computational Diffie-Hellman assumption

holds, because here, the adversary has more power,
and as a result we say that this assumption

is stronger that Computational Diffie-Hellman, the thing,
we really don't like about this

assumption, is the fact, that, it's
interactive, and that the adversary is allowed to

make queries to the challenger, and as I
said, we're gonna trying to get rid

of this interaction later on. But for now
I'll tell you that under this Interactive

Diffie-Hellman assumption and under the
assumption that the symmetric encryption

system provides authenticated encryption, and
under the assumption that the hash

function is kind of an ideal hash
function, what we call the random oracle,

then in fact the ElGamal system is chosen ciphertext secure and again this

RO here denotes the fact that it's in the
random oracle model. Which is not

important, so much for our purposes. The
main thing to remember that under

kind of this weird, interactive
assumption we can actually prove that

ElGamal is a chosen ciphertext secure.
And as far as we know this assumption

actually holds for the group ZP star.
So what we're gonna do next is basically

answer this question of whether we can get
rid of the interactive assumption. Can we

prove security strictly based on CDH? And
similarly can we proof security without

relying on random oracles? Just you know
without having to assume, that the hash

function is ideal. Just you know, can we
prove security using a concrete hash

function. And we'll do that very briefly
in the next segment.