0:00

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.