1 00:00:00,000 --> 00:00:04,069 In this segment, we're gonna look at the Diffie-Hellman protocol, which is our 2 00:00:04,069 --> 00:00:08,234 first practical key exchange mechanism. So let me remind you of the settings. Our 3 00:00:08,234 --> 00:00:12,442 friends here, Alice and Bob, have never met and yet they wanna exchange a shared 4 00:00:12,442 --> 00:00:16,445 secret key that they can then use to communicate securely with one another. 5 00:00:16,445 --> 00:00:20,088 In this segment and the next, we're only gonna be looking at eavesdropping 6 00:00:20,088 --> 00:00:23,937 security. In other words, we only care about eavesdroppers. The attackers are 7 00:00:23,937 --> 00:00:27,992 actually not allowed to tamper with data in the network. They're not allowed to 8 00:00:27,992 --> 00:00:32,046 inject packets. They're not allowed to change packets in any way. All they do is 9 00:00:32,046 --> 00:00:36,336 to just eavesdrop on the traffic. And at the end of the protocol, the key exchange 10 00:00:36,336 --> 00:00:40,880 protocol our friends Alice and Bob should have a shared secret key but the attacker 11 00:00:40,880 --> 00:00:45,031 namely the eavesdropper has no idea what that key's gonna be. In the previous 12 00:00:45,031 --> 00:00:49,343 segment we looked at a key segment called Merkle puzzles. That's just using block 13 00:00:49,343 --> 00:00:53,708 ciphers or hash functions. And I showed you that there that basically the attacker 14 00:00:53,708 --> 00:00:57,487 has a quadratic gap compared to the participants. In other words if the 15 00:00:57,487 --> 00:01:01,799 participants spent time proportional to N the attacker can break the protocol in 16 00:01:01,799 --> 00:01:06,163 time proportional to N squared. And as a result that protocol is to insecure to be 17 00:01:06,163 --> 00:01:10,369 considered practical. In this segment we are going to ask whether we can do the 18 00:01:10,369 --> 00:01:14,733 same thing but now we'd like to achieve an exponential gap between the attacker's 19 00:01:14,733 --> 00:01:19,051 work Ended up in the participant's work. In other words, Alice and Bob might do 20 00:01:19,051 --> 00:01:23,602 work proportional to N, but to break the protocol the attacker is gonna have to do 21 00:01:23,602 --> 00:01:27,876 work proportional to some exponential in N. So now there's an exponential gap 22 00:01:27,876 --> 00:01:32,702 between the participants work and the attacker's work. So as I said in the 23 00:01:32,702 --> 00:01:37,985 previous segment we can't achieve this exponential gap from blog ciphers like AES 24 00:01:37,985 --> 00:01:43,143 or SHA-256. We have to use hard problems that have more structure than just those 25 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. 26 00:01:48,714 --> 00:01:51,600 In this segment I'm gonna describe the Diffie-Hellman protocol very 27 00:01:51,600 --> 00:01:55,769 concretely and somewhat informally. When we're gonna come back to Diffie-Hellman next week 28 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 29 00:02:00,090 --> 00:02:04,198 rigorous security analysis of this protocol. Okay, so how does Diffie-Hellman 30 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 31 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 32 00:02:12,684 --> 00:02:16,820 should be thinking of really gigantic primes. Like, primes that are made up of 33 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 34 00:02:21,009 --> 00:02:25,413 digit prime roughly corresponds to about 2000 bits. So just writing down the prime 35 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 36 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 37 00:02:35,067 --> 00:02:40,014 of the Diffie-Hellman protocol. They are chosen once and they're fixed forever. Now 38 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 39 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 40 00:02:50,347 --> 00:02:55,420 And then she is gonna compute the number g to the power of a modulo p. 41 00:02:55,420 --> 00:02:59,802 Okay, so she computes this exponention, and reduces the result modular the prime p. 42 00:02:59,802 --> 00:03:04,407 And we're actually going to see how to compute this efficiently the next module, 43 00:03:04,407 --> 00:03:07,817 so for now just believe me that this computation can be done efficiently. 44 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 45 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 46 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 47 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 48 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 49 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? 50 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 51 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 52 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. 53 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 54 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 55 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 56 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 57 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, 58 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 59 00:04:24,972 --> 00:04:32,567 let me ask you, how does Bob actually compute this quantity g to the ab? 60 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 61 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 62 00:04:43,412 --> 00:04:48,450 now that both parties even though they seemingly computed different values. In 63 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 64 00:04:53,495 --> 00:04:57,703 the way that Martie Hellman and Wig Diffiie came up with this protocol back in 65 00:04:57,703 --> 00:05:01,752 1976. Martie Hellman was a professor here at Stanford and Wig Diffie was his 66 00:05:01,752 --> 00:05:06,120 graduate student. They came up with this protocol and this protocol really changed 67 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 68 00:05:10,541 --> 00:05:14,536 about developing block ciphers but it's actually about designing algebraic 69 00:05:14,536 --> 00:05:19,293 protocols that have properties like the one we see here. So you notice that what 70 00:05:19,293 --> 00:05:24,336 makes this protocol works is basically properties of exponentiation. Namely that, 71 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? 72 00:05:29,443 --> 00:05:33,568 These are just properties of exponentiations. Now when I describe a 73 00:05:33,568 --> 00:05:38,041 protocol like the one I just showed you. The real question that should be in your 74 00:05:38,041 --> 00:05:41,941 mind is not why the protocol works. In other words, it's very easy to verify 75 00:05:41,941 --> 00:05:45,840 that, in fact, both Alice and Bob end up with the same secret key. The bigger 76 00:05:45,840 --> 00:05:49,636 question is why is this protocol secure? In other words, why is it that an 77 00:05:49,636 --> 00:05:53,847 eavesdropper cannot figure out the same shared key due to the AB that both Alice 78 00:05:53,847 --> 00:05:57,902 and Bob computed by themselves? So let's analyze this a little bit, then, like I 79 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, 80 00:06:02,114 --> 00:06:06,221 just see intuitively why this protocol is gonna be secure. Well, what does the 81 00:06:06,566 --> 00:06:11,106 eavesdropper see? Well, he sees the prime and the generator. These are just fixed 82 00:06:11,106 --> 00:06:15,876 forever and everybody knows who they are. He also sees the value that Alice sent to 83 00:06:15,876 --> 00:06:20,531 Bob, namely this capital A. And he sees the value that Bob sent to Alice, namely 84 00:06:20,531 --> 00:06:25,187 this capital B. And the question is, can the, can the eavesdropper compute g to the 85 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 86 00:06:29,899 --> 00:06:34,497 this Diffie-Hellman function. So we'll say that the Diffie-Hellman function is defined 87 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 88 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 89 00:06:44,743 --> 00:06:49,580 function module over very large prime p. Remember p was something like 600 digits. 90 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 91 00:06:53,968 --> 00:06:58,850 function? So let me show you what's known about this. So suppose the prime happens 92 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 93 00:07:04,406 --> 00:07:08,783 known algorithm for computing the Diffie–Hellman function. Is actually a 94 00:07:08,783 --> 00:07:12,853 more general algorithm that computes the discrete log function, which we're gonna 95 00:07:12,853 --> 00:07:16,822 talk about next week. But for now, let's just say that this algorithm computes a 96 00:07:16,822 --> 00:07:20,742 Diffie-Hellman function. The algorithm is called a general number field sieve. I'm 97 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 98 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 99 00:07:28,982 --> 00:07:33,002 course. But the interesting thing is that it's running time is exponential in 100 00:07:33,002 --> 00:07:36,771 roughly the cube root of n. In other words, the running time is roughly e to 101 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 102 00:07:41,028 --> 00:07:44,853 time, of this algorithm is much more complicated than this. I'm deliberately 103 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 104 00:07:49,035 --> 00:07:52,809 emphasize is that in fact, this is not quite an exponential time algorithm. 105 00:07:52,809 --> 00:07:57,093 Exponential would be e to the power of n. This is sometimes called a sub-exponential 106 00:07:57,093 --> 00:08:01,377 algorithm because the exponent is really just proportional to the cube root of n, 107 00:08:01,377 --> 00:08:05,847 as opposed to linear n. What this says is that even though this problem is quite 108 00:08:05,847 --> 00:08:10,360 difficult, it's not really an exponential time problem. The running time in the 109 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 110 00:08:15,175 --> 00:08:19,848 examples. Suppose I happen to be looking at a modulus that happens to be about a 111 00:08:19,848 --> 00:08:23,879 thousand bits long. What this algorithm says is that we can solve the 112 00:08:23,879 --> 00:08:28,436 Diffie-Hellman problem in time that's approximately e to the qube root of 1,024. 113 00:08:28,436 --> 00:08:33,285 Now this is not really correct, in fact there are more constants in the exponent. 114 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 115 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. 116 00:08:42,866 --> 00:08:47,231 So the simple example shows you that if you have a sub-exponential algorithm, 117 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 118 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 119 00:08:56,277 --> 00:09:00,849 actually lying here. General number field sieve actually have many other 120 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 121 00:09:05,420 --> 00:09:09,816 actually going to be something like 80. Because of various constants in the 122 00:09:09,816 --> 00:09:14,622 exponents. But nevertheless but you see the problem is much harder than say 2 to 123 00:09:14,622 --> 00:09:19,428 the 1000. Even though describing it takes 1,000 bits, solving it does not take time 124 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 125 00:09:23,587 --> 00:09:27,309 difficulty of breaking down the Diffie-Hellman protocol compared to the 126 00:09:27,309 --> 00:09:31,785 difficulty of breaking down a cipher with a appropriate number of bits. For example, 127 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 128 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 129 00:09:40,792 --> 00:09:45,053 which means that breaking if you have Diffie-Hellman function with a 1,000 130 00:09:45,053 --> 00:09:47,701 bit module will take time 2 to the 80. 131 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, 132 00:09:53,989 --> 00:09:58,734 even though nobody really does this. In reality people would use 2,000 bit modulus. And 133 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 134 00:10:03,083 --> 00:10:07,715 fact your modulus needs to be very, very large. Again, you, you can really see the 135 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 136 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 137 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. 138 00:10:21,327 --> 00:10:25,952 from. And again I should mention there's not exactly a factor of eight because of 139 00:10:25,952 --> 00:10:30,251 the extra constants in the exponent. So this is a nice table that shows you that 140 00:10:30,251 --> 00:10:34,481 if you're gonna be using Diffie-Hellman to exchange, a session key. And that session 141 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 142 00:10:38,608 --> 00:10:42,633 you what modular size you need to use so that the security of the key exchange 143 00:10:42,633 --> 00:10:46,709 protocol is comparable to the security of the block cipher you're gonna be using after. 144 00:10:46,709 --> 00:10:50,837 Now this last row should really be disturbing to you. I should tell 145 00:10:50,837 --> 00:10:54,913 you that working with such a large modulus is very problematic. This is actually 146 00:10:54,913 --> 00:10:59,040 gonna be quite slow, and so the question is whether there is anything better that 147 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 148 00:11:03,832 --> 00:11:08,984 function is I describe it at the way Diffie and Hellman described it in 1976 149 00:11:08,984 --> 00:11:13,516 using arithmetic module of primes. The problem with arithmetic modular primes is 150 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 151 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 152 00:11:21,611 --> 00:11:26,158 really like. And so the question is can we run the Diffie-Hellman protocol in other 153 00:11:26,158 --> 00:11:30,300 settings. And it turns out the answer is yes. In fact we can literally translate 154 00:11:30,300 --> 00:11:34,308 the Diffie-Hellman protocol from an arithmetic model of primes to a different 155 00:11:34,308 --> 00:11:38,752 type of algebraic object and solving the Diffie-Hellman problem on that other 156 00:11:38,752 --> 00:11:43,196 algebraic object is much, much harder. This other algebraic object is what's 157 00:11:43,196 --> 00:11:47,758 called an elliptic curve. And as I said, computing the Diffie-Hellman function on 158 00:11:47,758 --> 00:11:52,735 these elliptic curves is much harder than computing the Diffie-Hellman modulo primes. 159 00:11:52,735 --> 00:11:57,476 Because the problem is so much harder, now we can use much smaller objects in 160 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 161 00:12:02,453 --> 00:12:06,780 only 512 bits for 256 bit keys. So because these module don't grow as 162 00:12:06,780 --> 00:12:10,914 fast on elliptic curves, there's generally a slow transition away from using module 163 00:12:10,914 --> 00:12:14,949 arithmetic, to using elliptic curves. I'm not going to describe elliptic curves 164 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 165 00:12:18,735 --> 00:12:22,421 do that at the very last week of the course, when we discuss more advanced 166 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 167 00:12:27,149 --> 00:12:31,933 more abstractly so that it really doesn't matter which algebraic structure you use 168 00:12:31,933 --> 00:12:36,831 whether you use arithmetic model of primes or whether you use a elliptic curve we 169 00:12:36,831 --> 00:12:41,557 can kinda abstract that whole issue away and then use the Diffie-Hellman concept a for 170 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 171 00:12:46,109 --> 00:12:50,321 abstractly next week. So as usual I wanna show that this beautiful protocol that I 172 00:12:50,321 --> 00:12:54,307 just showed you, the Diffie-Hellman protocol, is as is, is actually completely insecure 173 00:12:54,307 --> 00:12:58,195 against an active attack. Namely, it's completely insecure against what's called 174 00:12:58,195 --> 00:13:02,132 the man in the middle attack. We need to do something more than this protocol to 175 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 176 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 177 00:13:10,135 --> 00:13:14,649 why the protocol that I just showed you is insecure against active attacks. Well 178 00:13:14,649 --> 00:13:18,767 suppose we have this man in the middle that's trying to eavesdrop on the 179 00:13:18,767 --> 00:13:23,393 conversation between Alice and Bob. Well so, the protocol starts with Alice sending 180 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 181 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 182 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'. 183 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 184 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 185 00:13:46,588 --> 00:13:51,356 actually did anything to this traffic, all he sees is he got the value A'. As 186 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? 187 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 188 00:14:00,723 --> 00:14:05,457 again the man in the middle is gonna intercept this B. He's gonna generate his 189 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'. 190 00:14:10,434 --> 00:14:16,807 Okay, now what happens? Well Alice is gonna compute her part of the 191 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 192 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 193 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' 194 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 195 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 196 00:14:44,215 --> 00:14:49,526 can basically play this man in the middle and when Alice sends an encrypted message 197 00:14:49,526 --> 00:14:54,711 to Bob the man in the middle can simply decrypt this message because he knows the 198 00:14:54,711 --> 00:14:59,622 secret key that Alice encrypted message with, re-encrypt it using Bob's key. And 199 00:14:59,622 --> 00:15:04,105 then send the message on over to Bob. And this way Alice sent the message, Bob 200 00:15:04,105 --> 00:15:08,239 received the message. Bob thinks the message is secure. But in fact that 201 00:15:08,239 --> 00:15:12,605 message went through the man in the middle. The man in the middle decrypted 202 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, 203 00:15:17,146 --> 00:15:21,746 modify it if he wants to, and so on. So, the protocol becomes completely insecure 204 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 205 00:15:26,531 --> 00:15:30,697 protocol somehow to defend against men in the middle but it turns out that it's 206 00:15:30,697 --> 00:15:34,915 actually not that difficult to enhance and prevent man in the middle attacks. 207 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 208 00:15:39,377 --> 00:15:43,658 do is show you an interesting property of the Diffie-Hellman protocol. In fact, I 209 00:15:43,658 --> 00:15:48,046 want to show you that this protocol can be viewed as a non-interactive protocol. So, 210 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 211 00:15:52,487 --> 00:15:56,340 of users. Let's call them Alice, Bob, Charlie, David and so on and so forth. 212 00:15:56,500 --> 00:16:00,567 Each one of them is going to choose a random, secret value, and then on their 213 00:16:00,567 --> 00:16:04,419 Facebook profiles, they're gonna write down, their contribution to the 214 00:16:04,419 --> 00:16:08,486 Diffie-Hellman protocol. Alright so everybody just writes down you know g to 215 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, 216 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 217 00:16:18,942 --> 00:16:24,360 at all. Basically Alice would go and read Charlie's public profile. Charlie would go 218 00:16:24,360 --> 00:16:29,635 and read Alice's public profile. And now, boom, they immediately have a secret key. 219 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 220 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 221 00:16:39,987 --> 00:16:44,669 posted their contributions to the Diffie-Hellman protocol to their public 222 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. 223 00:16:50,076 --> 00:16:53,919 They immediately have a shared key and now they can start communicating 224 00:16:53,919 --> 00:16:58,194 securely through Facebook or not with one another. And notice that this is true for 225 00:16:58,194 --> 00:17:02,121 any Facebook user. So as soon as I read somebody's public profile, I immediately 226 00:17:02,121 --> 00:17:06,198 have a shared key with them without ever communicating with them. This property is 227 00:17:06,198 --> 00:17:09,967 sometimes called a non-interactive property of the Diffie-Hellman. So now, let 228 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 229 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 230 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 231 00:17:24,041 --> 00:17:28,559 four parties. All of them post their values to their Facebook profiles. And now 232 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 233 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 234 00:17:38,057 --> 00:17:42,427 read the public profiles of, the three friends, Bob, Charlie and David. And 235 00:17:42,427 --> 00:17:47,650 already she can compute a shared key with them. And similarly David is just gonna 236 00:17:47,650 --> 00:17:54,187 read the public profile of Charlie. Bob and Alice. And already he has a shared key 237 00:17:54,187 --> 00:17:58,716 with all four of them. Okay, so the question is whether we can kind of setup 238 00:17:58,885 --> 00:18:03,546 non-interactively these, these shared keys for groups that are larger than just two 239 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 240 00:18:07,986 --> 00:18:12,594 other words, if just two parties want to set up a shared key without communicating 241 00:18:12,594 --> 00:18:16,696 with one another, that's just Diffie-Hellman. It turns out, for N equals 242 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 243 00:18:21,473 --> 00:18:25,688 to Joux. It already uses very, very fancy mathematics, much more complicated 244 00:18:25,688 --> 00:18:29,959 mathematics than what I just showed you. And for N equals four, or five, or 245 00:18:29,959 --> 00:18:34,455 anything above this, above four, this problem is completely open. Nearly the 246 00:18:34,455 --> 00:18:38,790 case where four people post something to the public profiles and then everybody 247 00:18:38,790 --> 00:18:42,908 else reads the public profile and then they have a joint shared key, this is 248 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 249 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 250 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 251 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.