In this module I want to show you another approach to key exchange based on the concept of public key encryption. So again, just to remind you of the settings, we have our friends Alice and Bob as usual and their goal is to exchange a secret key, K. The eavesdropper gets to see the message they send to one another, but even though, he shouldn't learn anything about the key K that they exchanged. And as usual in this module, we're only gonna be looking at eavesdropping security. That is, we don't allow the attackers to tamper with data or to mount any other form of active attack. So just to remind you, earlier in this module we saw an inefficient mechanism based on generic blog cyphers. In the previous segment, we saw the Diffie-Hellman key exchange mechanism, which has an exponential gap between the work that the participants have to do versus the work that the attacker has to do. And in fact, this Diffie-Hellman protocol is used all over the web very frequently. In this segment, I want to show you a different approach based on public key encryption. So what is public key encryption? So just as in the case of symmetric encryption, there's an encryption algorithm and a decryption algorithm. However, here the encryption algorithm is given one key, which we're gonna call a public key, let's call this the public key that belongs to Bob. And the decryption algorithm is given a different key, we'll call it a secret key, that also belongs to Bob. So these two keys are sometimes called a key pair. One half of the pair is the public key, and the other half of the pair is the secret key. Now, the way you encrypt this as usual, a message would come in. The encryption algorithm would generate a cipher text that is the encryption of this message using the given public key. And then when the cipher text is given to the decryption algorithm, the decryption algorithm basically outputs the corresponding message. So as I said, PK is called the public key, and SK is called the secret key. So more precisely, what is public key encryption? Well, public key encryption is actually made up of three algorithms, G, E, and D. Algorithm G is what's called the key generation algorithm. When you run algorithm G, it will output two keys, the public key and the secret key. The encryption algorithm basically, given the public key in a message, will output the corresponding cypher text, and the decryption algorithm, given the secret key in the cypher text, will output the message or it will output bottom if an error occurred. And as usual, we have the usual consistency properties that say that for any public key and secret key that could have been output by the key generation algorithm, if we encrypt a message using a public key, and then decrypt using the secret key, we should get the original message back. Now what does it mean for a public key system to be secure? Well, we use the same concept of semantic security that we used before, except the games now are a little bit different. So let me explain how we define semantic security for a public key system. So here, the challenger is going to run the key generation algorithm to generate a public key and a secret key pair, and he's going to give the public key to the adversary. The challenger keeps the secret key to himself. What the adversary will do is he will out put two equal length messages, m0 and m1 as before. And then the challenger will give him the encryption of m0 or m1. As usual, we define two experiments, experiment zero and experiment one. In experiment 0, the adversary is given the encryption of m0, in experiment 1, the adversary is given the encryption of m1. And then the adversary's goal is to guess which encryption he was given. Was he given the encryption of m0, or was he given the encryption of m1? And we refer to his guess as the output of experiment zero or experiment one. One thing I wanna emphasize is that in the case of public key encryption, there's no need to give the attacker the ability to mount a chosen plain text attack. Why is that? Well, in the case of a symmetric key system, the attacker had to request the encryption of messages of his choice. In the case of a public key system, the attacker has the public key and therefore, he can by himself encrypt for himself any message that he wants. He doesn't need the challenger's help to create encryptions of messages of his choice. And as a result, in a public key settings, a chosen plaintiff attack is inerrant. There's no reason to give the attacker extra power to mount a chosen plain text attack. And that's why we never discuss chosen plaintiffs' queries in the context of defining semantic security for public key systems. Now that we've defined the game, we're gonna say that a public key system, GED, is semantically secure. It's basically, the attacker cannot distinguish experiment zero from experiment one. In other words, the adversary's probability of opening one and experiment zero is about the same as its probability of opening one in experiment one. So again, the attacker can't tell whether he was given the encryption of m0 or the encryption of m1. Now that we understand what public key encryption is, let's see how to use it to establish a shared secret. So here are our friends, Alice and Bob. Alice will start off by generating a random public key, secret key pair for herself, using the key generation algorithm. And then she's going to send to Bob, the public key, pk. And then she also says, hey, this message is from Alice. What Bob will do is he will generate a random 128-bit value x and he will send that to Alice saying, hey, this message is from Bob. And he'll send back the encryption of x under Alice's public key. Alice will receive the cypher text. She'll decrypt it using her secret key. And that will give her the value x. And now this value x can be used basically as a shared secret between the two of them. I want to emphasize that this protocol is very different from the Diffie-Hellman protocol that we saw in the last segment in the sense that here, the parties have to take turns, in the sense that Bob cannot send his message until he receives the message from Alice. In other words, Bob cannot encrypt x to Alice's public key until he receives the public key from Alice. In a Diffie-Hellman protocol, however, the two parties could send their messages at arbitrary times, and there was no ordering enforced on those messages. As a result, we have this nice application of Diffie-Hellman where everybody could post their messages to Facebook, for example, and then just by looking at Facebook profiles, any pair would already have a shared key without any need for additional communication. Here this is not quite true, even if everybody posts their public keys to Facebook, there would still be a need to send this message before a shared key can be established. So now that we understand the protocol, the first question we need to ask is, why is this protocol secure? And as usual, we're only gonna look at eavesdropping security. So in this protocol, the attacker gets to see the public key and the encryption of x under the public key, and what he wants to get is basically this value x. Now we know that the system, the public use system that we used, is semantically secure. What that means is that the attacker cannot distinguish the encryption of x from the encryption of something random. In other words, just given the encryption of x, the attacker can't tell whether the plain text is x or just some random junk that was chosen from M. And because of that, that basically says that, just by looking at messages in this protocol, the value of x is indistinguishable in the attacker's view from a random element in M. And as a result, x can be used as a session key between the two parties. It's just a random value which the attacker cannot actually guess other than by trying all possible values of M. And I should say that showing that these two distributions are distinguishable follow directly from semantic security, and in fact this is a simple exercise to show that if the attacker could distinguish this distribution from that distribution, then the attacker could also break semantic security. And as usual, even though this protocol is secure against eavesdropping, it's completely insecure against the man-in-the-middle attack. So let's see a simple man-in-the-middle attack. Well, so here we have Alice generating her public key, secret key pair. At the same time the man in the middle is still going to generate his own public key, secret key pair. Now when Alice sends her public key over to Bob, the man in the middle will intercept that and instead he'll say, yeah this is a message from Alice, but Alice's public key really is really pk prime. So now Bob will receives this message. He thinks he got a message from Alice. What he'll send back is, well, he's gonna choose his random x, and he'll send that encryption of x under pk prime. The man in the middle is gonna intercept this message, and is gonna replace it with something else. So his goal is to make sure that the key exchange succeeds. In other words, Alice thinks that she got a message from Bob, and yet the man in the middle should know exactly what the exchange secret is. So what should the man in the middle send to Alice in this case? So here, let's call this cypher text C. What the man in the middle will do, is he will decrypt the cypher text C, using his own sequence key. And that will reveal x to the man in the middle. And then he's gonna go ahead and encrypt x under Alice's public key, send the value back to Alice. Alice will obtain this x and as far as she's concerned, she just did a key exchange with Bob where both of them learned the value x. But the problem, of course, is that the man in the middle also knows the value x. So this protocol becomes completely insecure once the man in the middle can tamper with messages from Alice to Bob and from Bob to Alice. So again, we have to do something to this protocol to make it secure, and we're gonna see how to do that actually in two weeks, after we introduce digital signatures. So now that I've shown you that public encryption implies key exchange secure against eavesdropping, the next question is, how do we construct public key encryption systems? And it turns out that these constructions generally rely on number theory and some algebra, and just like the Diffie-Hellman protocol relied on some algebra, and so before we go into these protocols in more detail, what I'd like to do is kind of take a quick detour. In the next module, we're going to look at the relevant number theoretic background. We'll just do one module on this and then we'll come back and talk about these public key constructions and more constructions for key exchange. So this is the end of this module, and as further reading, I just wanted to point to this paper that shows that if, in fact, all we do is rely on symmetric ciphers and hash functions, then Merkle Puzzles are optimal for key exchange. And in fact, we cannot achieve more than a quadratic app as long as we treat the primitives we're given as a black box. So basically this shows that a quadratic app is the best possible. And also, I wanted to point to another paper that kind of summarizes some of these key exchange mechanisms that we talked about. Key exchange using public key cryptography, and key exchange using the Diffie-Hellman. You can take a look at this paper and it kind of will give you a look ahead into what's coming and how to make these key exchange protocols secure against man in the middle and not just secure against eavesdropping. Okay, so that's the end of this module and the next module, we'll take a brief detour and do a kind of a brief overview of algebra and number theory.
