Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
ElGamal Security
Loading...
From the course by Stanford University
Cryptography I
2044 оценки
From the lesson
Public-Key Encryption
Week 6. This week's topic is public key encryption: how to encrypt using a public key and decrypt using a secret key. Public key encryption is used for key management in encrypted file systems, in encrypted messaging systems, and for many other tasks. The videos cover two families of public key encryption systems: one based on trapdoor functions (RSA in particular) and the other based on the Diffie-Hellman protocol. We construct systems that are secure against tampering, also known as chosen ciphertext security (CCA security). There has been a ton of research on CCA security over the past decade and given the allotted time we can only summarize the main results from the last few years. The lectures contain suggestions for further readings for those interested in learning more about CCA secure public-key systems. The problem set this week involves a bit more math than usual, but should expand your understanding of public-key encryption. Please don't be shy about posting questions in the forum. This is the last week of this Crypto I course. I hope everyone learned a lot and enjoyed the material. Crypto is a beautiful topic with lots of open problems and room for further research. I look forward to seeing you in Crypto II where we will cover additional core topics and a few more advanced topics.
Meet the Instructors
Dan BonehProfessor
Computer Science
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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
