0:00:00.000,0:00:04.069 In this segment, we're gonna look at the[br]Diffie-Hellman protocol, which is our 0:00:04.069,0:00:08.234 first practical key exchange mechanism. So[br]let me remind you of the settings. Our 0:00:08.234,0:00:12.442 friends here, Alice and Bob, have never[br]met and yet they wanna exchange a shared 0:00:12.442,0:00:16.445 secret key that they can then use to[br]communicate securely with one another. 0:00:16.445,0:00:20.088 In this segment and the next, we're only[br]gonna be looking at eavesdropping 0:00:20.088,0:00:23.937 security. In other words, we only care[br]about eavesdroppers. The attackers are 0:00:23.937,0:00:27.992 actually not allowed to tamper with data[br]in the network. They're not allowed to 0:00:27.992,0:00:32.046 inject packets. They're not allowed to[br]change packets in any way. All they do is 0:00:32.046,0:00:36.336 to just eavesdrop on the traffic. And at[br]the end of the protocol, the key exchange 0:00:36.336,0:00:40.880 protocol our friends Alice and Bob should[br]have a shared secret key but the attacker 0:00:40.880,0:00:45.031 namely the eavesdropper has no idea what[br]that key's gonna be. In the previous 0:00:45.031,0:00:49.343 segment we looked at a key segment called[br]Merkle puzzles. That's just using block 0:00:49.343,0:00:53.708 ciphers or hash functions. And I showed[br]you that there that basically the attacker 0:00:53.708,0:00:57.487 has a quadratic gap compared to the[br]participants. In other words if the 0:00:57.487,0:01:01.799 participants spent time proportional to N[br]the attacker can break the protocol in 0:01:01.799,0:01:06.163 time proportional to N squared. And as a[br]result that protocol is to insecure to be 0:01:06.163,0:01:10.369 considered practical. In this segment we[br]are going to ask whether we can do the 0:01:10.369,0:01:14.733 same thing but now we'd like to achieve an[br]exponential gap between the attacker's 0:01:14.733,0:01:19.051 work Ended up in the participant's work.[br]In other words, Alice and Bob might do 0:01:19.051,0:01:23.602 work proportional to N, but to break the[br]protocol the attacker is gonna have to do 0:01:23.602,0:01:27.876 work proportional to some exponential in[br]N. So now there's an exponential gap 0:01:27.876,0:01:32.702 between the participants work and the[br]attacker's work. So as I said in the 0:01:32.702,0:01:37.985 previous segment we can't achieve this[br]exponential gap from blog ciphers like AES 0:01:37.985,0:01:43.143 or SHA-256. We have to use hard problems[br]that have more structure than just those 0:01:43.143,0:01:48.714 symmetric primitives. And so instead what[br]we're gonna do is use a little bit of algebra. 0:01:48.714,0:01:51.600 In this segment I'm gonna[br]describe the Diffie-Hellman protocol very 0:01:51.600,0:01:55.769 concretely and somewhat informally. When[br]we're gonna come back to Diffie-Hellman next week 0:01:55.769,0:02:00.090 and we're gonna describe the protocol more[br]abstractly and we're gonna do a much more 0:02:00.090,0:02:04.198 rigorous security analysis of this[br]protocol. Okay, so how does Diffie-Hellman 0:02:04.198,0:02:08.173 work? What we're gonna do is, first of[br]all, we're gonna fix some large prime 0:02:08.334,0:02:12.684 which I'm gonna call p. Actually p I'll[br]usually use to denote primes. And you 0:02:12.684,0:02:16.820 should be thinking of really gigantic[br]primes. Like, primes that are made up of 0:02:16.820,0:02:21.009 600 digits are so. And just for those of[br]you who like to think in binary, a 600 0:02:21.009,0:02:25.413 digit prime roughly corresponds to about[br]2000 bits. So just writing down the prime 0:02:25.413,0:02:29.932 takes about two kilo bits of data. And[br]then we're also gonna fix an integer g 0:02:29.932,0:02:35.067 that happens to live in the range one to[br]p. So these values p and g are parameters 0:02:35.067,0:02:40.014 of the Diffie-Hellman protocol. They are[br]chosen once and they're fixed forever. Now 0:02:40.014,0:02:45.087 the protocol works as follow. So here's[br]our friends Alice and Bob. So what Alice's 0:02:45.087,0:02:50.347 going to do is she's gonna starts off by[br]choosing some random number a in the range 1 to p-1 0:02:50.347,0:02:55.420 And then she is gonna compute[br]the number g to the power of a modulo p. 0:02:55.420,0:02:59.802 Okay, so she computes this exponention,[br]and reduces the result modular the prime p. 0:02:59.802,0:03:04.407 And we're actually going to see how to[br]compute this efficiently the next module, 0:03:04.407,0:03:07.817 so for now just believe me that this[br]computation can be done efficiently. 0:03:07.817,0:03:13.118 Now, let's call capital A the result of this[br]value. So, what Alice will do is she will 0:03:13.118,0:03:17.501 send capital A over to Bob. Now Bob is[br]going to do the same thing. He's going to 0:03:17.501,0:03:22.161 choose a random number b in the range 1[br]to p-1. He's going to compute g to 0:03:22.161,0:03:26.322 the b module of p and let's call this[br]number B and he's going to send this 0:03:26.322,0:03:31.114 number B over to Alice. So Alice sends A[br]to Bob. Bob sends B. To Alice. And now 0:03:31.114,0:03:36.848 they claim that they can generate a shared[br]secret key. So what's a shared secret key? 0:03:36.848,0:03:41.968 Well, it's defined as. Let's call it[br]K_AB. And it's basically defined as the 0:03:41.968,0:03:47.410 value g to the power of a times b. Now the[br]amazing observation of Diffie-Hellman had 0:03:47.410,0:03:53.040 back in 1976 is that in fact both parties[br]can compute this value g to the ab. 0:03:53.040,0:03:58.738 So let's see, Alice can compute this value[br]because she can take her value B that she 0:03:58.738,0:04:04.232 received from Bob. She can take this value[br]B, raise it to the power of a and, let's 0:04:04.232,0:04:09.116 see, what she'll get is g to the b to the[br]power of b. And by the rules of 0:04:09.116,0:04:14.935 exponentiation, g to the power of b to the[br]power of a is equal to g to the ab. Bob 0:04:14.935,0:04:19.986 turns out, can do something similar, so[br]his goal is to compute g to the a to the b, 0:04:19.986,0:04:24.972 which again, is g to the ab, so both[br]Alice and Bob will have computed K_AB, and 0:04:24.972,0:04:32.567 let me ask you, how does Bob actually[br]compute this quantity g to the ab? 0:04:32.567,0:04:37.894 Well so all he does is he takes the value A that[br]he received from Alice and he raises it to 0:04:37.894,0:04:43.412 his own secret b and that gives him the[br]shared secret g to the ab. So you can see 0:04:43.412,0:04:48.450 now that both parties even though they[br]seemingly computed different values. In 0:04:48.450,0:04:53.495 fact they both end up with the same value[br]namely g ab module p. I should mention by 0:04:53.495,0:04:57.703 the way that Martie Hellman and Wig[br]Diffiie came up with this protocol back in 0:04:57.703,0:05:01.752 1976. Martie Hellman was a professor here[br]at Stanford and Wig Diffie was his 0:05:01.752,0:05:06.120 graduate student. They came up with this[br]protocol and this protocol really changed 0:05:06.120,0:05:10.541 the world. In that it introduced this new[br]age in cryptography. Where now it's not just 0:05:10.541,0:05:14.536 about developing block ciphers but it's[br]actually about designing algebraic 0:05:14.536,0:05:19.293 protocols that have properties like the[br]one we see here. So you notice that what 0:05:19.293,0:05:24.336 makes this protocol works is basically[br]properties of exponentiation. Namely that, 0:05:24.525,0:05:29.443 g to the b to the power of a is the same[br]as g to the a to the power of b, okay? 0:05:29.443,0:05:33.568 These are just properties of[br]exponentiations. Now when I describe a 0:05:33.568,0:05:38.041 protocol like the one I just showed you.[br]The real question that should be in your 0:05:38.041,0:05:41.941 mind is not why the protocol works. In[br]other words, it's very easy to verify 0:05:41.941,0:05:45.840 that, in fact, both Alice and Bob end up[br]with the same secret key. The bigger 0:05:45.840,0:05:49.636 question is why is this protocol secure?[br]In other words, why is it that an 0:05:49.636,0:05:53.847 eavesdropper cannot figure out the same[br]shared key due to the AB that both Alice 0:05:53.847,0:05:57.902 and Bob computed by themselves? So let's[br]analyze this a little bit, then, like I 0:05:57.902,0:06:02.114 said, we're gonna do a much more in-depth[br]analysis next week. But, let's, for now, 0:06:02.114,0:06:06.221 just see intuitively why this protocol is[br]gonna be secure. Well, what does the 0:06:06.566,0:06:11.106 eavesdropper see? Well, he sees the prime[br]and the generator. These are just fixed 0:06:11.106,0:06:15.876 forever and everybody knows who they are.[br]He also sees the value that Alice sent to 0:06:15.876,0:06:20.531 Bob, namely this capital A. And he sees[br]the value that Bob sent to Alice, namely 0:06:20.531,0:06:25.187 this capital B. And the question is, can[br]the, can the eavesdropper compute g to the 0:06:25.187,0:06:29.899 ab just given these four values? So more[br]generally, what we can do is we can define 0:06:29.899,0:06:34.497 this Diffie-Hellman function. So we'll say[br]that the Diffie-Hellman function is defined 0:06:34.497,0:06:39.373 based on some value g. And the question is[br]given g to the a, and g to the b. Can you 0:06:39.373,0:06:44.743 compute g to the ab? And what we're[br]asking is how hard is it to compute this 0:06:44.743,0:06:49.580 function module over very large prime p.[br]Remember p was something like 600 digits. 0:06:49.580,0:06:53.968 So the real question we need to answer is[br]how hard is this, is this Diffie-Hellman 0:06:53.968,0:06:58.850 function? So let me show you what's known[br]about this. So suppose the prime happens 0:06:58.850,0:07:04.406 to be n bits long. Okay, so in our case[br]say n is 2,000 bits. It turns out the best 0:07:04.406,0:07:08.783 known algorithm for computing the[br]Diffie–Hellman function. Is actually a 0:07:08.783,0:07:12.853 more general algorithm that computes the[br]discrete log function, which we're gonna 0:07:12.853,0:07:16.822 talk about next week. But for now, let's[br]just say that this algorithm computes a 0:07:16.822,0:07:20.742 Diffie-Hellman function. The algorithm is[br]called a general number field sieve. I'm 0:07:20.742,0:07:24.912 not gonna describe how it works, although[br]if you'd want to hear how it works, let me 0:07:24.912,0:07:28.982 know, and that could be one of the special[br]topics that we cover at the end of the 0:07:28.982,0:07:33.002 course. But the interesting thing is that[br]it's running time is exponential in 0:07:33.002,0:07:36.771 roughly the cube root of n. In other[br]words, the running time is roughly e to 0:07:36.771,0:07:41.028 the power of o of cube root of n. So in[br]fact the exact expression for the running 0:07:41.028,0:07:44.853 time, of this algorithm is much more[br]complicated than this. I'm deliberately 0:07:44.853,0:07:49.035 simplifying it here just to kind of get[br]the point across. The point that I want to 0:07:49.035,0:07:52.809 emphasize is that in fact, this is not[br]quite an exponential time algorithm. 0:07:52.809,0:07:57.093 Exponential would be e to the power of n.[br]This is sometimes called a sub-exponential 0:07:57.093,0:08:01.377 algorithm because the exponent is really[br]just proportional to the cube root of n, 0:08:01.377,0:08:05.847 as opposed to linear n. What this says is[br]that even though this problem is quite 0:08:05.847,0:08:10.360 difficult, it's not really an exponential[br]time problem. The running time in the 0:08:10.360,0:08:15.175 exponent is gonna be just proportional to[br]the cube root of n. So let's look at some 0:08:15.175,0:08:19.848 examples. Suppose I happen to be looking[br]at a modulus that happens to be about a 0:08:19.848,0:08:23.879 thousand bits long. What this algorithm[br]says is that we can solve the 0:08:23.879,0:08:28.436 Diffie-Hellman problem in time that's[br]approximately e to the qube root of 1,024. 0:08:28.436,0:08:33.285 Now this is not really correct, in fact[br]there are more constants in the exponent. 0:08:33.285,0:08:38.192 But again, just to get, the point across,[br]we can say that the running time would be 0:08:38.192,0:08:42.866 roughly e to the qube root of 1,024; which[br]is actually very small, roughly e to the 10. 0:08:42.866,0:08:47.231 So the simple example shows you that[br]if you have a sub-exponential algorithm, 0:08:47.231,0:08:51.589 you see that even if the problem is quite[br]large, like 1,000 bits. Because of the 0:08:51.589,0:08:56.277 cube root effect the exponent actually is not[br]that big overall. Now to be honest I'm 0:08:56.277,0:09:00.849 actually lying here. General number field[br]sieve actually have many other 0:09:00.849,0:09:05.420 constants in the exponents so in fact this[br]is not going to be ten at all. It's 0:09:05.420,0:09:09.816 actually going to be something like 80.[br]Because of various constants in the 0:09:09.816,0:09:14.622 exponents. But nevertheless but you see[br]the problem is much harder than say 2 to 0:09:14.622,0:09:19.428 the 1000. Even though describing it takes[br]1,000 bits, solving it does not take time 0:09:19.428,0:09:23.587 to the 1,000. So here I roll down the[br]table that kind of shows you the rough 0:09:23.587,0:09:27.309 difficulty of breaking down the[br]Diffie-Hellman protocol compared to the 0:09:27.309,0:09:31.785 difficulty of breaking down a cipher with[br]a appropriate number of bits. For example, 0:09:31.785,0:09:36.261 if your cipher has 80 bit keys. That would[br]be roughly comparable to using 1,000 bit 0:09:36.261,0:09:40.792 modules. In other words breaking a cipher[br]with 80 bit keys takes time roughly 2 to the 80 0:09:40.792,0:09:45.053 which means that[br]breaking if you have Diffie-Hellman function with a 1,000 0:09:45.053,0:09:47.701 bit module will take time 2 to the 80. 0:09:47.701,0:09:53.989 If your cipher uses 128 bit keys like AES, you should be[br]really using a 3,000 bit modulus, 0:09:53.989,0:09:58.734 even though nobody really does this. In reality[br]people would use 2,000 bit modulus. And 0:09:58.734,0:10:03.083 then if your key is very large, like if[br]we're using a 256 bit AES key, then in 0:10:03.083,0:10:07.715 fact your modulus needs to be very, very[br]large. Again, you, you can really see the 0:10:07.715,0:10:12.346 cube root effect here. We doubled the size[br]of our key and because of the cube root 0:10:12.346,0:10:16.752 effect, what that means is we have to[br]increase the size of, of our modulus by a 0:10:16.752,0:10:21.327 factor of two cubed, namely a factor of[br]eight, which is where this 15,000 comes from. 0:10:21.327,0:10:25.952 from. And again I should mention there's[br]not exactly a factor of eight because of 0:10:25.952,0:10:30.251 the extra constants in the exponent. So[br]this is a nice table that shows you that 0:10:30.251,0:10:34.481 if you're gonna be using Diffie-Hellman to[br]exchange, a session key. And that session 0:10:34.481,0:10:38.608 key is gonna be used for a block cipher[br]with a certain key size, this table shows 0:10:38.608,0:10:42.633 you what modular size you need to use so[br]that the security of the key exchange 0:10:42.633,0:10:46.709 protocol is comparable to the security of[br]the block cipher you're gonna be using after. 0:10:46.709,0:10:50.837 Now this last row should[br]really be disturbing to you. I should tell 0:10:50.837,0:10:54.913 you that working with such a large modulus[br]is very problematic. This is actually 0:10:54.913,0:10:59.040 gonna be quite slow, and so the question[br]is whether there is anything better that 0:10:59.040,0:11:03.832 we can do? And it turns out there is. In[br]fact the way I describe the Diffie-Hellman 0:11:03.832,0:11:08.984 function is I describe it at the way[br]Diffie and Hellman described it in 1976 0:11:08.984,0:11:13.516 using arithmetic module of primes. The[br]problem with arithmetic modular primes is 0:11:13.516,0:11:17.539 that the Diffie-Hellman function is hard[br]to compute, but it's not as hard as you'd 0:11:17.539,0:11:21.611 like. There's this cube root effect that[br]makes it a little easier than what you'd 0:11:21.611,0:11:26.158 really like. And so the question is can we[br]run the Diffie-Hellman protocol in other 0:11:26.158,0:11:30.300 settings. And it turns out the answer is[br]yes. In fact we can literally translate 0:11:30.300,0:11:34.308 the Diffie-Hellman protocol from an[br]arithmetic model of primes to a different 0:11:34.308,0:11:38.752 type of algebraic object and solving the[br]Diffie-Hellman problem on that other 0:11:38.752,0:11:43.196 algebraic object is much, much harder.[br]This other algebraic object is what's 0:11:43.196,0:11:47.758 called an elliptic curve. And as I said,[br]computing the Diffie-Hellman function on 0:11:47.758,0:11:52.735 these elliptic curves is much harder than[br]computing the Diffie-Hellman modulo primes. 0:11:52.735,0:11:57.476 Because the problem is so much harder, now[br]we can use much smaller objects in 0:11:57.476,0:12:02.453 particular, you know we'd be using primes[br]that are only a 160 bits or 80 bit keys or 0:12:02.453,0:12:06.780 only 512 bits for 256 bit keys. So because[br]these module don't grow as 0:12:06.780,0:12:10.914 fast on elliptic curves, there's generally[br]a slow transition away from using module 0:12:10.914,0:12:14.949 arithmetic, to using elliptic curves. I'm[br]not going to describe elliptic curves 0:12:14.949,0:12:18.735 right now for you, but if this is[br]something you'd like to learn about I can 0:12:18.735,0:12:22.421 do that at the very last week of the[br]course, when we discuss more advanced 0:12:22.421,0:12:27.149 topics. But in fact when we come back to[br]Diffie-Hellman next week I'm gonna describe it 0:12:27.149,0:12:31.933 more abstractly so that it really doesn't[br]matter which algebraic structure you use 0:12:31.933,0:12:36.831 whether you use arithmetic model of primes[br]or whether you use a elliptic curve we 0:12:36.831,0:12:41.557 can kinda abstract that whole issue away[br]and then use the Diffie-Hellman concept a for 0:12:41.557,0:12:46.109 key exchange and for other things as well.[br]And as I said we'll see that more 0:12:46.109,0:12:50.321 abstractly next week. So as usual I wanna[br]show that this beautiful protocol that I 0:12:50.321,0:12:54.307 just showed you, the Diffie-Hellman protocol,[br]is as is, is actually completely insecure 0:12:54.307,0:12:58.195 against an active attack. Namely, it's[br]completely insecure against what's called 0:12:58.195,0:13:02.132 the man in the middle attack. We need to[br]do something more than this protocol to 0:13:02.132,0:13:06.019 make is secure against man in the middle.[br]And again we're gonna come back to Diffie 0:13:06.019,0:13:10.135 Hellman and make it secure against man in[br]the middle next week. Okay. So let's see 0:13:10.135,0:13:14.649 why the protocol that I just showed you is[br]insecure against active attacks. Well 0:13:14.649,0:13:18.767 suppose we have this man in the middle[br]that's trying to eavesdrop on the 0:13:18.767,0:13:23.393 conversation between Alice and Bob. Well[br]so, the protocol starts with Alice sending 0:13:23.563,0:13:28.309 g to the a over to Bob. Well, so the man[br]in the middle is gonna intercept that and 0:13:28.309,0:13:32.777 he's gonna take the message that Alice[br]sent and he's gonna replace it with his 0:13:32.777,0:13:37.113 own message. So it's called A', And[br]let's write that is g to the a'. 0:13:37.113,0:13:41.939 Okay? So the man in the middle chooses his[br]own a' and what he sends to Bob is 0:13:41.939,0:13:46.588 actually g to the a'. Now poor Bob[br]doesn't know that the man in the middle 0:13:46.588,0:13:51.356 actually did anything to this traffic, all[br]he sees is he got the value A'. As 0:13:51.356,0:13:55.946 far as he knows, that value came from[br]Alice. So what is he gonna do in response? 0:13:55.946,0:14:00.723 Well, he's gonna send back his value B out[br]which is g to the b back to Alice. Well 0:14:00.723,0:14:05.457 again the man in the middle is gonna[br]intercept this B. He's gonna generate his 0:14:05.457,0:14:10.434 own b' and what he actually sends[br]back to Alice is B' which is g to the b'. 0:14:10.434,0:14:16.807 Okay, now what happens? Well[br]Alice is gonna compute her part of the 0:14:16.807,0:14:22.808 secret key and she's gonna get g to the ab'. Bob is gonna compute his part of 0:14:22.808,0:14:28.281 the secret key and he's gonna get g to the[br]b times a'. Okay, these now you 0:14:28.281,0:14:33.592 notice these are not the same keys. In the[br]man in the middle because he knows both A' 0:14:33.592,0:14:38.903 and B' he can compute both g to[br]the ab' and g to ba'. Yeah it's 0:14:38.903,0:14:44.215 not difficult to see the man in the middle[br]knows both values. And as a result, now he 0:14:44.215,0:14:49.526 can basically play this man in the middle[br]and when Alice sends an encrypted message 0:14:49.526,0:14:54.711 to Bob the man in the middle can simply[br]decrypt this message because he knows the 0:14:54.711,0:14:59.622 secret key that Alice encrypted message[br]with, re-encrypt it using Bob's key. And 0:14:59.622,0:15:04.105 then send the message on over to Bob. And[br]this way Alice sent the message, Bob 0:15:04.105,0:15:08.239 received the message. Bob thinks the[br]message is secure. But in fact that 0:15:08.239,0:15:12.605 message went through the man in the[br]middle. The man in the middle decrypted 0:15:12.605,0:15:17.146 it, re-encrypted it for Bob. At the same[br]time he was able to completely read it, 0:15:17.146,0:15:21.746 modify it if he wants to, and so on. So,[br]the protocol becomes completely insecure 0:15:21.746,0:15:26.531 give n a man in the middle. And so as I[br]said we're gonna have to enhance the 0:15:26.531,0:15:30.697 protocol somehow to defend against men in[br]the middle but it turns out that it's 0:15:30.697,0:15:34.915 actually not that difficult to enhance and[br]prevent man in the middle attacks. 0:15:34.915,0:15:39.377 And we're gonna come back to that and see that[br]in a week or two. The last think I want to 0:15:39.377,0:15:43.658 do is show you an interesting property of[br]the Diffie-Hellman protocol. In fact, I 0:15:43.658,0:15:48.046 want to show you that this protocol can be[br]viewed as a non-interactive protocol. So, 0:15:48.046,0:15:52.487 what do I mean by that? So Imagine we have[br]a whole bunch of users, you know, millions 0:15:52.487,0:15:56.340 of users. Let's call them Alice, Bob,[br]Charlie, David and so on and so forth. 0:15:56.500,0:16:00.567 Each one of them is going to choose a[br]random, secret value, and then on their 0:16:00.567,0:16:04.419 Facebook profiles, they're gonna write[br]down, their contribution to the 0:16:04.419,0:16:08.486 Diffie-Hellman protocol. Alright so[br]everybody just writes down you know g to 0:16:08.486,0:16:13.604 the a, g to the b, g to the c and so on.[br]Now the interesting thing about this is, 0:16:13.604,0:16:18.942 if say Alice and Charlie wanna set up a[br]shared key they don't need to communicate 0:16:18.942,0:16:24.360 at all. Basically Alice would go and read[br]Charlie's public profile. Charlie would go 0:16:24.360,0:16:29.635 and read Alice's public profile. And now,[br]boom, they immediately have a secret key. 0:16:29.635,0:16:34.976 Namely, now, Alice knows, g to the c and[br]a. Charlie knows g to the a and с. And as 0:16:34.976,0:16:39.987 a result, both of them can compute п to[br]the ac. So, in some sense, once they've 0:16:39.987,0:16:44.669 posted their contributions to the[br]Diffie-Hellman protocol to their public 0:16:44.669,0:16:50.076 profiles, they don't need to communicate[br]with each other at all to set up a shared key. 0:16:50.076,0:16:53.919 They immediately have a shared key[br]and now they can start communicating 0:16:53.919,0:16:58.194 securely through Facebook or not with one[br]another. And notice that this is true for 0:16:58.194,0:17:02.121 any Facebook user. So as soon as I read[br]somebody's public profile, I immediately 0:17:02.121,0:17:06.198 have a shared key with them without ever[br]communicating with them. This property is 0:17:06.198,0:17:09.967 sometimes called a non-interactive[br]property of the Diffie-Hellman. So now, let 0:17:09.967,0:17:14.716 me show you an open problem. And this is[br]an open problem that's been open for ages 0:17:14.716,0:17:19.407 and ages and ages. So it'd be really cool[br]if one of you can actually solve it. The 0:17:19.407,0:17:24.041 question is, can we do this for more than[br]two parties? In other words, say we have 0:17:24.041,0:17:28.559 four parties. All of them post their[br]values to their Facebook profiles. And now 0:17:28.559,0:17:33.366 we'd like to make it that just by reading[br]Facebook profiles, all of them can set up 0:17:33.366,0:17:38.057 a shared secret key. In other words, Alice[br]is, what she'll, she'll do is she'll only 0:17:38.057,0:17:42.427 read the public profiles of, the three[br]friends, Bob, Charlie and David. And 0:17:42.427,0:17:47.650 already she can compute a shared key with[br]them. And similarly David is just gonna 0:17:47.650,0:17:54.187 read the public profile of Charlie. Bob[br]and Alice. And already he has a shared key 0:17:54.187,0:17:58.716 with all four of them. Okay, so the[br]question is whether we can kind of setup 0:17:58.885,0:18:03.546 non-interactively these, these shared keys[br]for groups that are larger than just two 0:18:03.546,0:18:07.986 people. So as I said, for n equals two,[br]this is just a Diffie-Hellman protocol. In 0:18:07.986,0:18:12.594 other words, if just two parties want to[br]set up a shared key without communicating 0:18:12.594,0:18:16.696 with one another, that's just[br]Diffie-Hellman. It turns out, for N equals 0:18:16.696,0:18:21.473 three, we also know how to do it, there's[br]a known protocol, it's called protocol due 0:18:21.473,0:18:25.688 to Joux. It already uses very, very fancy[br]mathematics, much more complicated 0:18:25.688,0:18:29.959 mathematics than what I just showed you.[br]And for N equals four, or five, or 0:18:29.959,0:18:34.455 anything above this, above four, this[br]problem is completely open. Nearly the 0:18:34.455,0:18:38.790 case where four people post something to[br]the public profiles and then everybody 0:18:38.790,0:18:42.908 else reads the public profile and then[br]they have a joint shared key, this is 0:18:42.908,0:18:47.459 something we don't know how to do even for[br]four people. And this is a problem that's 0:18:47.459,0:18:52.010 been open for ages and ages, it's kind of[br]a fun problem to think about and so see if 0:18:52.010,0:18:56.073 you can solve it, if you will, it's[br]instant fame in the crypto world. Okay, so 0:18:56.073,0:19:00.516 I'll stop here, and we'll continue with[br]another key exchange mechanism in the next segment.