[SOUND] In the last lecture we introduced the notion of key exchange and here we'll see the example of the Diffie-Hellman key exchange protocol. So, remember that a key exchange protocol was simply a interactive protocol run by two parties. In which they exchange a messages, after which they can both compute a shared key, k. And the security goal was that, from the point of view of an attacker who can observe the entire transcript of messages exchanged between these two parties, the key, k, that these parties share. Should be indistinguishable from a uniform key, from the point of view of that attacker. Now, for the Diffie-Hellman key exchange protocol that we'll see. We're going to need to rely on the decisional Diffie-Hellman problem that we introduced last week. And, I just want to briefly recall that for you here. So we have, in this setting, a group generation algorithm that I'll write with a script of g. Which, on input, a security parameter n outputs a description of a cyclic group g having prime order q, along with a generator g in the group. We didn't assume that the group had prime order always in the context in which we discussed it last week. But here we are going to acquire that the group have prime order because we are going to be relying on the decisional Diffie-Hellman function. And as we mentioned last time there are good reasons to insist that the group does indeed have prime order. The security parameter n determines the length of the prime q. That is the prime q is going to have length equal to n bits and this of course will also determine the size of the group g which is going to be roughly two to the n, have two to the n element in it approximately. Now given this group g of prime order q with generator g. The Decisional Diffie-Hellman or DDH problem is the following. Given elements g to the x and g to the y, where x and y are uniform exponents in the range of zero to q minus one. Distinguish the group element g to the xy from a completely uniform and independent group element chosen uniformly from the group g. We said last week that the hardness of the Decisional Diffie-Hellman problem in particular implies hardness of the discrete-logarithm problem. That is, hardness of computing x from g to the x and equivalently a hardness of computing y, from g to the y. However for our application, we are going to need the stronger decisional Diffie-Hellman problem. The Diffie-Hellman key exchange protocol works in the following way. For the first party, we'll run the group generation algorithm to generate parameters g, q, and g. Again cyclic group g of prime order q with generator g. It then choses a uniform exponent, x, and computes the group element, H1 equal to g to the x, and it sends those parameters, along with H1, as the first message of the protocol. The second party responds by choosing a uniform exponent y and computing h2 equal to the g to the y. And it sends that back as the second message of the protocol. To compute the keys, what the party on the left does is compute its own pk1 as H2 to the x. And the party on the right computes it's own key K2 as H1 to the y. Where x on the left was the secret exponent chosen by the party on the left as we had on the slide a moment ago. And y is the secret exponent chosen by the party on the right. Now the thing to note is that the key k1 computed by the party on the left is equal to h2 to the x, and h2 was equal to g to the y. So, therefore, the key k1 is equal to g to the y to the x, or equivalently, g to the yx. A similar calculation on the right shows that g2, sorry that k2 is equal to g to the xy. And of course the point here is that f to the xy is equal to g to the yx. So the parties have generated identical keys. That is k1 equal to k2. Now in practice, it would be unusual for one of the parties to generate their own parameters, g, q and g. Instead what's done in practice is for the group g of order q and a generator g to be fixed and standardized. And that way all parties in the world whoever want to run this protocol will simply know already what those parameters are and they wouldn't have to be generated fresh as part of the protocol every time. It's believed that this doesn't impact security at all in the sense that in particular there's no way to embed any kind of trap door into the choice of the group or the generator of that group, that would somehow make the protocol insecure. So, then, given those parameters, the par, the parties can simply run in a symmetric fashion, where the party on the left chooses X. And sends h1 equals g to the x. The party on the right chooses y and sends h2 equal g to the y. And then they compute their shared key just like on the previous slide. What can we say about the security of this protocol? Well let's think about it from the point of view of the eavesdropper. So an eavesdropper on the protocol whether the parameters are generated by one of the parties or whether the parameters are standardized and fixed, and fixed in advance. Gets to observe only the parameters g, q and g along with the elements g to the x and g to the y. And the key that's then computed by the parties is equal to g to the x y. Note that computing the key, computing g to the x y from the transcript, would be exactly the computational Diffie-Hellman problem that we also introduced last week. But, as we said in the last lecture, being unable to compute the key from the transcript is a relatively weak security guarantee and we'd like something stronger. Good things for us we have that the decisional Diffie-Hellman problem implies exactly what we need. That is, the DDH problem tells us exactly that distinguishing the shared key k i.e., g to the xy, from a completely uniform and independent group element. Given the transcript which includes g to the x and g to the y. Is hard if the decisional Diffie-Hellman problem. I.E. if the Diffie-Hellman problem is hard, then given the transcript we're still unable to distinguish the shared key g to the xy from a completely uniform group element. And that this means simply is that if the DDH problem is hard relative to the particular group generation algorithm being used, then the Diffie-Hellman key-exchange protocol is secure. Now one subtle key I want to point out, and some of you may already have picked up on this, is that when we defined the key-exchange protocols originally. We define them so as to output for each party a uniform looking key of length n. That is the key should be indistinguishable from a uniform n bit string. And instead in the Diffie–Hellman protocol we end up with a uniform looking group element k. Which for one thing may not have length equal to n. And for another thing may not be a uniform string. Unless it happens to be the case that the group itself, corresponds somehow to a uniform strings of some length. And in general it's not clear how you would use a group element, random or not. As for example 128 bit AES key. Now this is true and it's a technical point perhaps but it's one that must be dealt with in practice and the solution is rather simple. The solution is just use a key derivation mechanism and what this means is that the parties with take their shared secret information k. And map that onto a random looking key of length n. And they can do this by simply, running their shared secret, k, through a suitable hash function to obtain a shared string, a shared secret string, k prime. I don't want to get into too much, discussion about the exact requirements for the hash function h. I'll mention that you need stronger properties than collision resistance, you need some kind of random looking property on h, but I do not want to get into that here. Suffice it to say that this is essentially what is done in practice, to derive a shared bit string of the appropriate length after running the Diffie-Hellman protocol. In the next lecture, I will return to the points we made in a previous lecture. Where we discuss limitations of private key cryptography and we'll see how public key cryptography more generally can address those issues.
