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