0 00:00:00,000 --> 00:00:30,000 Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/838 Thanks! 1 00:00:14,720 --> 00:00:17,569 Oh, OK. 2 00:00:17,570 --> 00:00:19,399 And with that, I'll leave you with the 3 00:00:19,400 --> 00:00:20,419 experts, please. 4 00:00:20,420 --> 00:00:22,009 Well, it comes down, Wolf. 5 00:00:22,010 --> 00:00:23,010 A lot of applause. 6 00:00:34,000 --> 00:00:35,189 It's like my gun. Oh, there we go. 7 00:00:35,190 --> 00:00:36,239 Thank you all for being here. 8 00:00:36,240 --> 00:00:37,949 And I especially appreciate your 9 00:00:37,950 --> 00:00:40,169 fortitude in coming to a heavy duty 10 00:00:40,170 --> 00:00:43,139 mass talk at 10-15 p.m. 11 00:00:43,140 --> 00:00:44,789 on day number two. 12 00:00:44,790 --> 00:00:48,029 So we are going to 13 00:00:48,030 --> 00:00:49,979 talk about how to use lattices in 14 00:00:49,980 --> 00:00:51,119 cryptography. 15 00:00:51,120 --> 00:00:52,979 And I encourage you, because we're going 16 00:00:52,980 --> 00:00:55,319 to be doing a lot of coding in this talk. 17 00:00:55,320 --> 00:00:57,749 We have put all of the code in our slides 18 00:00:57,750 --> 00:01:00,089 online at this fine Web site. 19 00:01:00,090 --> 00:01:02,069 So if you want to pull out your laptops 20 00:01:02,070 --> 00:01:04,109 and play along with us during the talk 21 00:01:04,110 --> 00:01:05,749 and make sure that everything works, you 22 00:01:05,750 --> 00:01:07,739 are welcome to do that right now so you 23 00:01:07,740 --> 00:01:09,929 can copy paste all of our code samples 24 00:01:09,930 --> 00:01:12,119 into Sage as we're going along. 25 00:01:13,920 --> 00:01:16,619 So here's some 26 00:01:16,620 --> 00:01:17,969 headlines about cryptography. 27 00:01:17,970 --> 00:01:19,619 Cryptography appears a lot in the news 28 00:01:19,620 --> 00:01:21,299 lately. And every once in a while there's 29 00:01:21,300 --> 00:01:23,369 an article that is not about bitcoin or 30 00:01:23,370 --> 00:01:25,379 cryptocurrency or block chains. 31 00:01:25,380 --> 00:01:27,060 So here's a couple examples. 32 00:01:28,200 --> 00:01:30,449 And all of these have something 33 00:01:30,450 --> 00:01:32,939 in common. These articles, popularization 34 00:01:32,940 --> 00:01:35,009 of cryptography, research, 35 00:01:35,010 --> 00:01:37,139 and what these have in common is 36 00:01:37,140 --> 00:01:38,399 lattices. 37 00:01:38,400 --> 00:01:40,769 So this is the topic of our 38 00:01:40,770 --> 00:01:42,089 talk for you today. 39 00:01:42,090 --> 00:01:44,159 Why are people talking about lattices and 40 00:01:44,160 --> 00:01:45,539 cryptography? 41 00:01:45,540 --> 00:01:47,729 So there's kind of two things 42 00:01:47,730 --> 00:01:49,769 that you can do with lattices and crypto. 43 00:01:49,770 --> 00:01:52,199 Number one, we can break stuff 44 00:01:52,200 --> 00:01:53,369 which is super fun. 45 00:01:53,370 --> 00:01:55,469 So there's, you know, basically every 46 00:01:55,470 --> 00:01:56,849 kind of crypto that you can think of. 47 00:01:56,850 --> 00:01:58,499 There's probably some way to break it 48 00:01:58,500 --> 00:02:00,659 using lattices, including, 49 00:02:00,660 --> 00:02:03,479 you know, both like old 50 00:02:03,480 --> 00:02:05,339 public key crypto systems, long broken 51 00:02:05,340 --> 00:02:07,349 public kicker's crypto systems and crypto 52 00:02:07,350 --> 00:02:09,269 systems that we're still using today and 53 00:02:09,270 --> 00:02:10,948 tomorrow's crypto systems. 54 00:02:10,949 --> 00:02:12,239 So the other thing that you can do with 55 00:02:12,240 --> 00:02:14,669 lattices is make cryptography, 56 00:02:14,670 --> 00:02:16,529 including sort of futuristic things like 57 00:02:16,530 --> 00:02:18,419 post quantum cryptography, fully humming 58 00:02:18,420 --> 00:02:20,099 morphic encryption. 59 00:02:20,100 --> 00:02:21,789 Even people have tried to do things like 60 00:02:21,790 --> 00:02:23,729 indistinguishably obfuscation, but maybe 61 00:02:23,730 --> 00:02:24,989 that was a bad idea. 62 00:02:24,990 --> 00:02:26,579 We'll find out in 20 years. 63 00:02:26,580 --> 00:02:27,979 So, OK, 64 00:02:29,040 --> 00:02:31,529 so this talk is going to sort of 65 00:02:31,530 --> 00:02:32,639 happen in multiple parts. 66 00:02:32,640 --> 00:02:33,569 We're going to break stuff. 67 00:02:33,570 --> 00:02:34,919 We're going to make stuff. So if you get 68 00:02:34,920 --> 00:02:36,809 lost in one part, maybe you can catch up 69 00:02:36,810 --> 00:02:37,810 in another piece. 70 00:02:39,480 --> 00:02:40,919 So what does a lattice. 71 00:02:42,810 --> 00:02:43,889 This is not a lattice. 72 00:02:48,770 --> 00:02:50,049 This is a lettuce. 73 00:02:50,050 --> 00:02:51,559 OK, I apologize to all the non-native 74 00:02:51,560 --> 00:02:53,689 English speakers in the room and 75 00:02:53,690 --> 00:02:54,939 our translators. 76 00:02:54,940 --> 00:02:57,219 Let us let us not let us 77 00:02:57,220 --> 00:02:58,220 know. 78 00:02:58,610 --> 00:02:59,149 OK. 79 00:02:59,150 --> 00:03:00,889 So for the purposes of this talk, there 80 00:03:00,890 --> 00:03:02,449 actually multiple kinds of lattices in 81 00:03:02,450 --> 00:03:04,069 mathematics, the kind that we're going to 82 00:03:04,070 --> 00:03:06,229 talk about is think of it as a repeating 83 00:03:06,230 --> 00:03:08,419 grid of points in n dimensional space. 84 00:03:08,420 --> 00:03:10,069 So we have like n dimensional Euclidean 85 00:03:10,070 --> 00:03:11,929 space. Hopefully you can imagine in 86 00:03:11,930 --> 00:03:14,299 dimensions and think of a repeating grid 87 00:03:14,300 --> 00:03:15,679 of points. 88 00:03:15,680 --> 00:03:16,849 Look something like this in two 89 00:03:16,850 --> 00:03:17,850 dimensions. 90 00:03:18,470 --> 00:03:20,320 This is a lattice of lettuces. 91 00:03:23,120 --> 00:03:25,509 I just put this into a mess with 92 00:03:25,510 --> 00:03:26,719 the translators. 93 00:03:26,720 --> 00:03:29,149 So I apologize 94 00:03:29,150 --> 00:03:30,739 to our fine translators. 95 00:03:30,740 --> 00:03:33,019 But slightly more seriously, 96 00:03:33,020 --> 00:03:35,179 a you can think of I mean, we're going 97 00:03:35,180 --> 00:03:37,189 to have sort of abstract looking points, 98 00:03:37,190 --> 00:03:38,779 but you can think of the points as 99 00:03:38,780 --> 00:03:40,279 actually representing MASH met 100 00:03:40,280 --> 00:03:42,379 mathematical things like 101 00:03:42,380 --> 00:03:44,479 polynomials. So later on in the 102 00:03:44,480 --> 00:03:45,829 talk, we're going to see lattices of 103 00:03:45,830 --> 00:03:47,649 polynomials. So you can give each lattice 104 00:03:47,650 --> 00:03:49,189 point as representing some kind of 105 00:03:49,190 --> 00:03:51,379 mathematical object here, a lettuce 106 00:03:51,380 --> 00:03:53,259 or, you know, maybe something else. 107 00:03:54,910 --> 00:03:55,910 All right, 108 00:03:57,980 --> 00:03:58,869 then. 109 00:03:58,870 --> 00:04:00,189 All these points, you need to have some 110 00:04:00,190 --> 00:04:01,479 structure in place. 111 00:04:01,480 --> 00:04:03,609 So, for instance, instead of 112 00:04:03,610 --> 00:04:05,799 taking a stand which pictures let 113 00:04:05,800 --> 00:04:07,869 us all over the place, we can also 114 00:04:07,870 --> 00:04:09,819 take these two vectors. 115 00:04:09,820 --> 00:04:12,009 So imagine this over here. 116 00:04:13,240 --> 00:04:14,679 There's a zero point. 117 00:04:14,680 --> 00:04:16,509 And then from there, we have these two 118 00:04:16,510 --> 00:04:19,088 vectors going out, two lines, 119 00:04:19,089 --> 00:04:21,249 and then these are chosen 120 00:04:21,250 --> 00:04:22,779 so that every other dot 121 00:04:23,830 --> 00:04:25,779 you can be reached with one of those 122 00:04:25,780 --> 00:04:26,889 combinations. 123 00:04:26,890 --> 00:04:29,169 So just to get up here, you take a twice 124 00:04:29,170 --> 00:04:30,549 to get over here. 125 00:04:30,550 --> 00:04:33,099 You take it twice and subtract this one. 126 00:04:33,100 --> 00:04:35,289 So every dot can be, which was those 127 00:04:35,290 --> 00:04:36,789 two things. 128 00:04:36,790 --> 00:04:38,259 Now, these are not unique. 129 00:04:38,260 --> 00:04:40,809 This is also the green ones. 130 00:04:40,810 --> 00:04:42,909 Also former Baz's or the 131 00:04:42,910 --> 00:04:44,979 blue ones, like very long and 132 00:04:44,980 --> 00:04:45,999 stretch. 133 00:04:46,000 --> 00:04:48,819 But again, any combinations of be three 134 00:04:48,820 --> 00:04:50,979 and before can reach all 135 00:04:50,980 --> 00:04:51,980 the dots. 136 00:04:53,980 --> 00:04:55,209 When you think of when you learned about 137 00:04:55,210 --> 00:04:57,669 quartet systems, then you learned about, 138 00:04:57,670 --> 00:04:59,799 say, the real numbers and you had like X 139 00:04:59,800 --> 00:05:01,329 Y coordinates. 140 00:05:01,330 --> 00:05:03,099 Now here, the difference is that we only 141 00:05:03,100 --> 00:05:05,309 allow integer multiples 142 00:05:05,310 --> 00:05:08,139 only and tire copies of this. 143 00:05:08,140 --> 00:05:09,999 There is nothing between those dots. 144 00:05:10,000 --> 00:05:12,969 You can take half of B three 145 00:05:12,970 --> 00:05:14,499 if you take half of B three. 146 00:05:14,500 --> 00:05:15,419 You land here. 147 00:05:15,420 --> 00:05:16,539 There's nothingness. 148 00:05:16,540 --> 00:05:17,439 It's like a game plan. 149 00:05:17,440 --> 00:05:18,489 You can't stop somewhere. 150 00:05:18,490 --> 00:05:20,230 You can only hope to the next dot. 151 00:05:21,280 --> 00:05:22,599 And if you want to describe these was 152 00:05:22,600 --> 00:05:24,399 more math, then we go for coordinate 153 00:05:24,400 --> 00:05:26,849 systems. So, for instance, this 154 00:05:26,850 --> 00:05:29,349 be one vector is something like 155 00:05:29,350 --> 00:05:31,569 two over and 156 00:05:31,570 --> 00:05:33,459 three or four up. 157 00:05:33,460 --> 00:05:36,039 So then you would have this one is two. 158 00:05:36,040 --> 00:05:38,889 And this one is three point four. 159 00:05:38,890 --> 00:05:40,359 And then to store those. 160 00:05:40,360 --> 00:05:41,769 We put them in the top row. 161 00:05:41,770 --> 00:05:43,059 This is the first coordinate. 162 00:05:43,060 --> 00:05:44,079 There's a second coordinate. 163 00:05:45,370 --> 00:05:48,279 And for the second vector, the same thing 164 00:05:48,280 --> 00:05:49,869 now. 165 00:05:49,870 --> 00:05:52,049 Two dimensions is very small. 166 00:05:52,050 --> 00:05:54,129 But when you look at something like this. 167 00:05:58,080 --> 00:05:59,219 You get this little bit of a tunnel 168 00:05:59,220 --> 00:06:00,689 vision that is somewhere in origin and 169 00:06:00,690 --> 00:06:02,069 you can see it goes up to three 170 00:06:02,070 --> 00:06:03,149 dimensions. 171 00:06:03,150 --> 00:06:05,189 Now, incorrupt, we gonna use those with a 172 00:06:05,190 --> 00:06:07,499 few hundred up to a thousand dimensions. 173 00:06:07,500 --> 00:06:09,479 We're not going to do this with pictures. 174 00:06:11,960 --> 00:06:14,089 I think we will be totally fine with 175 00:06:14,090 --> 00:06:15,979 having coordinates for those and then 176 00:06:15,980 --> 00:06:17,899 does the top row going to have the 177 00:06:17,900 --> 00:06:19,969 thousand entries and they're gonna 178 00:06:19,970 --> 00:06:22,909 be towers and thousand such lines 179 00:06:22,910 --> 00:06:25,009 so each other vector will have its 180 00:06:25,010 --> 00:06:26,299 own line. 181 00:06:26,300 --> 00:06:28,519 So mathematically, there's no problem 182 00:06:28,520 --> 00:06:30,379 going beyond four images. 183 00:06:30,380 --> 00:06:32,490 We'll go back to dimensioned to. 184 00:06:35,520 --> 00:06:36,520 All right, I 185 00:06:37,760 --> 00:06:40,289 understand what a Latisse is. 186 00:06:40,290 --> 00:06:41,809 Why do we care about lattices? 187 00:06:41,810 --> 00:06:43,459 What are we going to do with lattices? 188 00:06:43,460 --> 00:06:45,139 So for this talk, most of what we're 189 00:06:45,140 --> 00:06:47,269 going to do with lattices is 190 00:06:47,270 --> 00:06:49,069 find short vectors in them. 191 00:06:49,070 --> 00:06:51,109 So we saw that we could have multiple 192 00:06:51,110 --> 00:06:53,149 bases for the same lattice. 193 00:06:53,150 --> 00:06:54,769 Some of them might be have super long 194 00:06:54,770 --> 00:06:56,899 vectors, but we're interested 195 00:06:56,900 --> 00:06:59,089 in finding pretty short vectors 196 00:06:59,090 --> 00:07:00,889 in some lattice, given an arbitrary 197 00:07:00,890 --> 00:07:02,509 description of the lattice. 198 00:07:02,510 --> 00:07:04,249 So this is called the shortest vector 199 00:07:04,250 --> 00:07:06,319 problem. And the problem is 200 00:07:06,320 --> 00:07:07,819 generally given some description of a 201 00:07:07,820 --> 00:07:10,459 lattice find the shortest vector. 202 00:07:10,460 --> 00:07:12,259 So there are a few ways that you can try 203 00:07:12,260 --> 00:07:13,429 to compute this. 204 00:07:13,430 --> 00:07:15,109 This problem turns out to be pretty hard 205 00:07:15,110 --> 00:07:16,669 to solve. Exactly. 206 00:07:16,670 --> 00:07:18,859 So the fastest algorithms that we have 207 00:07:18,860 --> 00:07:20,209 to compute the shortest vector. 208 00:07:20,210 --> 00:07:22,309 Exactly in a lattice run, 209 00:07:22,310 --> 00:07:24,319 an exponential time in the dimension. 210 00:07:24,320 --> 00:07:27,019 So two to the end in Dimension N. 211 00:07:27,020 --> 00:07:29,179 But you can compute an approximation 212 00:07:29,180 --> 00:07:30,589 for the shortest vector. 213 00:07:30,590 --> 00:07:32,539 So something that's kind of short but not 214 00:07:32,540 --> 00:07:34,609 exactly the shortest vector in polynomial 215 00:07:34,610 --> 00:07:36,679 time, which is fast enough for the 216 00:07:36,680 --> 00:07:38,419 purposes of computer science. 217 00:07:38,420 --> 00:07:40,489 So you have that 218 00:07:40,490 --> 00:07:42,559 option also. So hard to solve. 219 00:07:42,560 --> 00:07:44,839 Exactly. Easy to solve approximately. 220 00:07:44,840 --> 00:07:46,669 That's kind of our setup. 221 00:07:46,670 --> 00:07:49,159 And in this talk, the specific 222 00:07:49,160 --> 00:07:52,009 algorithm that we'll be using to compute 223 00:07:52,010 --> 00:07:54,109 approximate short vectors is 224 00:07:54,110 --> 00:07:55,999 called the LLN algorithm, which was named 225 00:07:56,000 --> 00:07:57,619 after its inventors, Leinster, Leinster, 226 00:07:57,620 --> 00:07:58,639 Lobos. 227 00:07:58,640 --> 00:08:00,609 So the input to this algorithm is some 228 00:08:00,610 --> 00:08:02,749 gladis basis and dimensions. 229 00:08:02,750 --> 00:08:04,249 The output is a pretty short vector in 230 00:08:04,250 --> 00:08:05,929 the lattice. We're pretty short. 231 00:08:05,930 --> 00:08:07,579 Means that the length of that vector, 232 00:08:08,930 --> 00:08:11,359 if you in sort of Euclidean length, 233 00:08:11,360 --> 00:08:14,569 is something exponential 234 00:08:14,570 --> 00:08:16,369 in the dimension times the length of the 235 00:08:16,370 --> 00:08:17,959 actual shortest vector. 236 00:08:17,960 --> 00:08:19,489 This doesn't look super impressive. 237 00:08:19,490 --> 00:08:21,469 It turns out to be non-trivial to find. 238 00:08:21,470 --> 00:08:23,569 And it is good 239 00:08:23,570 --> 00:08:25,699 enough for our purposes in breaking a lot 240 00:08:25,700 --> 00:08:27,349 of cryptography. So that's the part that 241 00:08:27,350 --> 00:08:28,759 we're excited about. 242 00:08:28,760 --> 00:08:30,200 So LLN algorithm. 243 00:08:32,340 --> 00:08:33,389 All right. 244 00:08:33,390 --> 00:08:35,489 The examples with Sage, 245 00:08:35,490 --> 00:08:37,918 which is a lot like Python, plus 246 00:08:37,919 --> 00:08:40,019 a bunch of functions that you might 247 00:08:40,020 --> 00:08:41,668 not have seen before, which is kind of 248 00:08:41,669 --> 00:08:43,739 like Python itself as Python with 249 00:08:43,740 --> 00:08:44,909 a lot of functions you might not have 250 00:08:44,910 --> 00:08:45,910 seen before. 251 00:08:46,710 --> 00:08:48,359 Some of them are pretty obvious and the 252 00:08:48,360 --> 00:08:50,429 same as in Python, like your type two 253 00:08:50,430 --> 00:08:52,769 times three, it tells you six. 254 00:08:52,770 --> 00:08:54,209 Whoops. Wrong way. 255 00:08:54,210 --> 00:08:56,549 If you do two and then a carrot 256 00:08:56,550 --> 00:08:58,649 symbol, which is like shift six for 257 00:08:58,650 --> 00:09:00,389 the Americans, or maybe it's two left to 258 00:09:00,390 --> 00:09:02,369 one for the Germans. 259 00:09:02,370 --> 00:09:04,559 That is not exclusive. 260 00:09:04,560 --> 00:09:06,029 That's exponentiation. 261 00:09:06,030 --> 00:09:08,039 Which people who type mathematics in the 262 00:09:08,040 --> 00:09:10,229 tech language or late tech, they 263 00:09:10,230 --> 00:09:11,919 use this exponentiation. 264 00:09:11,920 --> 00:09:13,350 So two to the three is eight. 265 00:09:15,210 --> 00:09:16,829 There's all sorts of functions which do 266 00:09:16,830 --> 00:09:18,539 what you might expect, like if you factor 267 00:09:18,540 --> 00:09:20,369 an integer or a polynomial than X 268 00:09:20,370 --> 00:09:22,169 squared, minus nine is X plus three times 269 00:09:22,170 --> 00:09:24,089 X minus three. Or you can ask for roots 270 00:09:24,090 --> 00:09:26,219 of a polynomial X squared minus nine 271 00:09:26,220 --> 00:09:28,169 has minus three and three. 272 00:09:28,170 --> 00:09:29,549 What are those ones doing there. 273 00:09:29,550 --> 00:09:31,769 That's the power, like 274 00:09:31,770 --> 00:09:33,959 the multiplicity, the number of times 275 00:09:33,960 --> 00:09:35,909 that a root shows up. 276 00:09:35,910 --> 00:09:38,459 So if you factored X squared, 277 00:09:38,460 --> 00:09:40,499 it would tell you that, well, that's X 278 00:09:40,500 --> 00:09:42,599 minus zero with multiplicity, too. 279 00:09:42,600 --> 00:09:43,859 And there's various other functions. 280 00:09:43,860 --> 00:09:45,419 It gets more and more complicated. 281 00:09:45,420 --> 00:09:47,129 There's some useful functions like 282 00:09:47,130 --> 00:09:48,899 generating random primes. 283 00:09:48,900 --> 00:09:50,659 And this is generating Weld's like Rand 284 00:09:50,660 --> 00:09:52,229 range, but gives you a random prime 285 00:09:52,230 --> 00:09:53,230 number. 286 00:09:53,670 --> 00:09:55,859 And it goes up to two to the 512. 287 00:09:55,860 --> 00:09:57,599 Again, that exponentiation it's two to 288 00:09:57,600 --> 00:09:58,600 the 512 power. 289 00:09:59,700 --> 00:10:01,259 And then if you have two prime numbers 290 00:10:01,260 --> 00:10:02,969 like this, P and Q, you could multiply 291 00:10:02,970 --> 00:10:04,679 them together, get a big number N and 292 00:10:04,680 --> 00:10:06,509 hey, suddenly we're doing the RSA crypto 293 00:10:06,510 --> 00:10:08,669 system and then choose some exponent for 294 00:10:08,670 --> 00:10:10,679 RSA like Exponent three. 295 00:10:10,680 --> 00:10:12,539 And then you can encrypt a message, you 296 00:10:12,540 --> 00:10:14,639 can do some message which is an 297 00:10:14,640 --> 00:10:17,519 integer modulo N and compute Powell. 298 00:10:17,520 --> 00:10:19,409 Now that actually is a python function. 299 00:10:19,410 --> 00:10:21,149 You can use Pough in Python itself, the 300 00:10:21,150 --> 00:10:22,769 random prime. You need sage or you have 301 00:10:22,770 --> 00:10:24,299 to implement that itself. 302 00:10:24,300 --> 00:10:25,679 Implement it yourself. That's all you can 303 00:10:25,680 --> 00:10:27,869 do in in straight 304 00:10:27,870 --> 00:10:29,579 up python. And that gives you message to 305 00:10:29,580 --> 00:10:31,679 the power E modulo N and 306 00:10:31,680 --> 00:10:33,539 that's your cipher text, for instance, 307 00:10:33,540 --> 00:10:35,939 the third power of a message modulo and 308 00:10:35,940 --> 00:10:37,229 and then there's some slightly more 309 00:10:37,230 --> 00:10:39,299 complicated procedure for figuring out 310 00:10:39,300 --> 00:10:41,399 the exponent that you need to decrypt 311 00:10:41,400 --> 00:10:42,929 using the same PÃ¥l function again. 312 00:10:43,980 --> 00:10:45,989 Lots of warnings that we should be giving 313 00:10:45,990 --> 00:10:48,089 about how to implement RSA don't to 314 00:10:48,090 --> 00:10:50,099 do exactly this for RSA. 315 00:10:50,100 --> 00:10:51,359 Maybe some of the warnings you'll 316 00:10:51,360 --> 00:10:53,279 actually see later from some attacks, but 317 00:10:53,280 --> 00:10:54,869 there's many, many more warnings. 318 00:10:54,870 --> 00:10:56,189 If you're actually going to do a crypto 319 00:10:56,190 --> 00:10:57,869 library, then you should do something 320 00:10:57,870 --> 00:11:00,329 which has a lot more protections 321 00:11:00,330 --> 00:11:01,369 than what we're showing you. We're just 322 00:11:01,370 --> 00:11:03,449 gonna do the kind of math details and 323 00:11:03,450 --> 00:11:05,399 not get into all sorts of other attacks 324 00:11:05,400 --> 00:11:06,400 that are out there. 325 00:11:10,130 --> 00:11:12,319 So the thing that we 326 00:11:12,320 --> 00:11:14,119 want to get from the previous slide is 327 00:11:14,120 --> 00:11:16,669 that we care somehow about factoring. 328 00:11:16,670 --> 00:11:18,829 So we want RSA to be secure so 329 00:11:18,830 --> 00:11:20,449 that we have a secure Internet, which 330 00:11:20,450 --> 00:11:21,739 means that it should be hard to factor 331 00:11:21,740 --> 00:11:23,209 those modules in. 332 00:11:23,210 --> 00:11:24,919 So how hard is factoring? 333 00:11:24,920 --> 00:11:26,299 I don't know. It seems pretty hard. 334 00:11:26,300 --> 00:11:27,469 Let's build the Internet. 335 00:11:27,470 --> 00:11:28,470 Sounds good. 336 00:11:30,020 --> 00:11:32,329 And so for this next section, 337 00:11:32,330 --> 00:11:33,859 we're going to talk about how to factor 338 00:11:33,860 --> 00:11:35,029 with lettuces. 339 00:11:35,030 --> 00:11:36,859 So we care about factoring for the 340 00:11:36,860 --> 00:11:39,379 purposes of proving the security of RSA 341 00:11:39,380 --> 00:11:41,269 or at least establishing the security of 342 00:11:41,270 --> 00:11:43,309 RSA. So how hard is factoring. 343 00:11:43,310 --> 00:11:44,569 Really? 344 00:11:44,570 --> 00:11:45,739 Some of you may have may have seen our 345 00:11:45,740 --> 00:11:47,119 talk a few years ago. 346 00:11:47,120 --> 00:11:49,039 All right. Let's explore is kind of the 347 00:11:49,040 --> 00:11:51,139 parameter space of this problem. 348 00:11:51,140 --> 00:11:53,389 Now, I have say our modules 349 00:11:53,390 --> 00:11:55,339 end which have colored purple and say two 350 00:11:55,340 --> 00:11:57,469 primes, P and Q and P times Q equals. 351 00:11:57,470 --> 00:11:58,759 And that's kind of the setup. 352 00:11:58,760 --> 00:12:01,559 So if I give you P times Q and N 353 00:12:01,560 --> 00:12:04,309 and P and Q and N, then 354 00:12:04,310 --> 00:12:05,809 you know how to factor in because I gave 355 00:12:05,810 --> 00:12:07,879 you the factors. So then the problem 356 00:12:07,880 --> 00:12:08,880 is easy. Right. Okay. 357 00:12:09,830 --> 00:12:11,109 We're good with that part. 358 00:12:11,110 --> 00:12:13,219 All right. If I give you an 359 00:12:13,220 --> 00:12:15,889 and one of the factors P then 360 00:12:15,890 --> 00:12:17,779 you can still factor N because you can 361 00:12:17,780 --> 00:12:20,259 use division to get Q then you're done. 362 00:12:20,260 --> 00:12:22,429 Right. So still we're 363 00:12:22,430 --> 00:12:23,749 in good territory. 364 00:12:23,750 --> 00:12:26,149 If I give you neither of the factors 365 00:12:26,150 --> 00:12:28,249 P and Q, but I just give you N, 366 00:12:28,250 --> 00:12:29,749 then I hope this problem is hard because 367 00:12:29,750 --> 00:12:31,039 otherwise the Internet is broken. 368 00:12:32,920 --> 00:12:34,639 It currently sort of the best algorithm 369 00:12:34,640 --> 00:12:36,709 that we have for factoring in this case 370 00:12:36,710 --> 00:12:39,559 is sub exponential time in 371 00:12:39,560 --> 00:12:42,469 the length of the modulus n 372 00:12:42,470 --> 00:12:44,599 current record. Nobody's factored the RSA 373 00:12:44,600 --> 00:12:47,119 10 24 challenge in public yet. 374 00:12:47,120 --> 00:12:49,289 Maybe the NSA is factored numbers of this 375 00:12:49,290 --> 00:12:51,499 size. I don't know if you're 376 00:12:51,500 --> 00:12:53,029 super excited about this topic. 377 00:12:53,030 --> 00:12:54,589 You can see our talk at twenty nine C 378 00:12:54,590 --> 00:12:56,299 three for more information. 379 00:12:56,300 --> 00:12:59,239 So this is somewhat hard. 380 00:12:59,240 --> 00:13:00,349 Let's do something a little bit more 381 00:13:00,350 --> 00:13:01,309 exciting. 382 00:13:01,310 --> 00:13:02,599 What if I give you something like this, 383 00:13:02,600 --> 00:13:04,399 like half the bits of P and half the bits 384 00:13:04,400 --> 00:13:06,439 of Q. If they happen to be arranged like 385 00:13:06,440 --> 00:13:08,149 this, this turns out to be really easy. 386 00:13:08,150 --> 00:13:09,859 You can sort of divide and like rearrange 387 00:13:09,860 --> 00:13:12,319 a couple of bits and then just 388 00:13:12,320 --> 00:13:14,769 recover both P and Q. 389 00:13:14,770 --> 00:13:16,399 It's a little surprising, but there's no 390 00:13:16,400 --> 00:13:18,019 like real situation in which you can 391 00:13:18,020 --> 00:13:19,819 imagine like this being relevant to your 392 00:13:19,820 --> 00:13:20,820 daily life. 393 00:13:24,400 --> 00:13:25,299 Let's make this a little bit more 394 00:13:25,300 --> 00:13:27,429 exciting. What about this? 395 00:13:27,430 --> 00:13:29,139 This easier heart like this is like 396 00:13:29,140 --> 00:13:30,759 halfway in between something that's easy 397 00:13:30,760 --> 00:13:32,079 and halfway between the something that's 398 00:13:32,080 --> 00:13:33,339 hard. 399 00:13:33,340 --> 00:13:34,340 Where do we stand? 400 00:13:35,260 --> 00:13:36,699 This is more exciting. 401 00:13:36,700 --> 00:13:37,299 All right. 402 00:13:37,300 --> 00:13:39,549 So turns out that this with 403 00:13:39,550 --> 00:13:41,049 this kind of information, if I give you 404 00:13:41,050 --> 00:13:42,999 half of the bits of pea like, say, the 405 00:13:43,000 --> 00:13:44,829 most significant half of bits of pea, 406 00:13:44,830 --> 00:13:45,789 although it doesn't really matter which 407 00:13:45,790 --> 00:13:47,709 half of it's the pea I give you, then you 408 00:13:47,710 --> 00:13:50,139 can factor. And in polynomial time, 409 00:13:50,140 --> 00:13:51,789 even though like the remaining half of 410 00:13:51,790 --> 00:13:53,739 bits of pea that you don't know is like 411 00:13:53,740 --> 00:13:55,929 gigantic, you can't brute force that. 412 00:13:55,930 --> 00:13:57,099 So we're doing something super 413 00:13:57,100 --> 00:13:58,389 interesting here. 414 00:13:58,390 --> 00:13:59,889 And it turns out that the way that you do 415 00:13:59,890 --> 00:14:01,959 this is with lattices, hence the 416 00:14:01,960 --> 00:14:02,960 subject of our talk. 417 00:14:04,760 --> 00:14:07,189 So let's see how this works. 418 00:14:07,190 --> 00:14:08,929 So this is a little cryptographic magic 419 00:14:08,930 --> 00:14:11,239 trick. This is all sage code 420 00:14:11,240 --> 00:14:12,199 that you guys can run. 421 00:14:12,200 --> 00:14:13,369 So if you don't believe me that this 422 00:14:13,370 --> 00:14:15,289 works, you can totally run this yourself 423 00:14:15,290 --> 00:14:17,179 and verify that it works. 424 00:14:17,180 --> 00:14:19,399 So I'm going to do my little magic trick 425 00:14:19,400 --> 00:14:21,709 here. So I generate 512 426 00:14:21,710 --> 00:14:24,019 bit primes, P and Q totally legitimate. 427 00:14:24,020 --> 00:14:24,919 Nothing up my sleeve. 428 00:14:24,920 --> 00:14:26,809 These are like honest jennet, like, you 429 00:14:26,810 --> 00:14:28,999 know, primes, whatever sage does 430 00:14:29,000 --> 00:14:30,359 to generate prime. 431 00:14:30,360 --> 00:14:33,479 I multiply them together to get an 432 00:14:33,480 --> 00:14:34,729 the product. 433 00:14:34,730 --> 00:14:36,829 And then I generate this value a which 434 00:14:36,830 --> 00:14:39,109 is like most of 435 00:14:39,110 --> 00:14:41,179 the bits of P except for like the least 436 00:14:41,180 --> 00:14:42,350 significant eighty bits. 437 00:14:43,420 --> 00:14:45,499 OK. So if I like look 438 00:14:45,500 --> 00:14:47,809 at this value a 439 00:14:47,810 --> 00:14:49,879 in hexadecimal, like there's a 440 00:14:49,880 --> 00:14:51,469 bunch of zeros in the least significant 441 00:14:51,470 --> 00:14:52,789 bits because I've deleted the least 442 00:14:52,790 --> 00:14:53,689 compute bits. 443 00:14:53,690 --> 00:14:55,579 So I learn most of a. 444 00:14:55,580 --> 00:14:57,049 But like not all of it. 445 00:14:57,050 --> 00:14:58,609 And eighty six bits is enough that I 446 00:14:58,610 --> 00:14:59,989 definitely shouldn't be able to brute 447 00:14:59,990 --> 00:15:02,149 force this on my laptop and I wouldn't 448 00:15:02,150 --> 00:15:04,789 even be able to run like a square root 449 00:15:04,790 --> 00:15:07,669 thing on my laptop in a 450 00:15:07,670 --> 00:15:09,619 sort of feasible time to get this done in 451 00:15:09,620 --> 00:15:11,719 time for the talk. OK, so 452 00:15:11,720 --> 00:15:14,149 what I want to do is recover 453 00:15:14,150 --> 00:15:16,519 my factorization of 454 00:15:16,520 --> 00:15:18,799 the RSA modules end here with only 455 00:15:18,800 --> 00:15:20,269 this partial information about the key, 456 00:15:20,270 --> 00:15:21,259 not the full key. 457 00:15:21,260 --> 00:15:22,669 So how do I do that? 458 00:15:23,690 --> 00:15:25,249 I construct a matrix. 459 00:15:25,250 --> 00:15:27,349 So we talked about matrices and lattices 460 00:15:27,350 --> 00:15:28,789 being somehow connected. 461 00:15:28,790 --> 00:15:30,349 And my matrix contains 462 00:15:31,850 --> 00:15:34,549 mice value A, which is like 463 00:15:34,550 --> 00:15:36,679 the bits of P that I am allowed 464 00:15:36,680 --> 00:15:38,749 to know and and and some other 465 00:15:38,750 --> 00:15:40,070 things that are also public. 466 00:15:41,210 --> 00:15:43,339 And then I run my magic L-A algorithm on 467 00:15:43,340 --> 00:15:44,329 it. 468 00:15:44,330 --> 00:15:46,429 OK. So here comes the magic 469 00:15:46,430 --> 00:15:47,299 trick. 470 00:15:47,300 --> 00:15:49,489 Now I take the output of the LLN 471 00:15:49,490 --> 00:15:50,749 algorithm. 472 00:15:50,750 --> 00:15:52,849 I construct a polynomial somehow 473 00:15:52,850 --> 00:15:54,989 from the vector that I got from l l 474 00:15:54,990 --> 00:15:57,169 l and if I compute the roots of 475 00:15:57,170 --> 00:15:59,269 that polynomial, I magically 476 00:15:59,270 --> 00:16:00,270 recovered p. 477 00:16:01,880 --> 00:16:04,039 Magic, the rabbit 478 00:16:04,040 --> 00:16:05,299 appeared again. I don't know. 479 00:16:05,300 --> 00:16:06,300 I don't know where it came from. 480 00:16:08,000 --> 00:16:09,049 What just happened? 481 00:16:09,050 --> 00:16:11,149 You guys, I hope you're confused because 482 00:16:11,150 --> 00:16:13,309 you should be confused, but 483 00:16:13,310 --> 00:16:15,439 I hope you believe this works like 484 00:16:15,440 --> 00:16:16,909 somehow magic has happened and I have 485 00:16:16,910 --> 00:16:20,179 factored very efficiently. 486 00:16:20,180 --> 00:16:20,839 OK. 487 00:16:20,840 --> 00:16:22,969 So this is an example 488 00:16:22,970 --> 00:16:24,709 of what's called coppersmiths method. 489 00:16:24,710 --> 00:16:26,449 So Coppersmith is one of the greatest 490 00:16:26,450 --> 00:16:28,219 crypto analysts of the 20th century and 491 00:16:28,220 --> 00:16:29,419 probably one of the greatest crypto 492 00:16:29,420 --> 00:16:31,099 analysts of the 21st century, except we 493 00:16:31,100 --> 00:16:32,089 don't really know because he works for 494 00:16:32,090 --> 00:16:33,199 the U.S. government now. 495 00:16:33,200 --> 00:16:35,059 But hopefully we'll find out in 50 years. 496 00:16:35,060 --> 00:16:36,060 I'm super excited. 497 00:16:38,630 --> 00:16:39,630 So. 498 00:16:43,690 --> 00:16:45,459 Anyway, I mean, like, yeah, his all of 499 00:16:45,460 --> 00:16:47,559 his work is amazing, Ellie, so what 500 00:16:47,560 --> 00:16:49,179 the stuff we know about in public. 501 00:16:49,180 --> 00:16:51,429 So and actually like 502 00:16:51,430 --> 00:16:53,379 his original paper from 1996 that 503 00:16:53,380 --> 00:16:55,269 describes sort of the generalization of 504 00:16:55,270 --> 00:16:57,579 this method is pretty hard to read. 505 00:16:57,580 --> 00:16:59,139 So what I'm going to present is kind of a 506 00:16:59,140 --> 00:17:01,019 simplification, which is due to how grave 507 00:17:01,020 --> 00:17:02,949 Grahame's several years later. 508 00:17:02,950 --> 00:17:04,479 But of course, the simplification still 509 00:17:04,480 --> 00:17:05,709 has multiple steps in. It looks very 510 00:17:05,710 --> 00:17:07,969 confusing. So that's sort of the state 511 00:17:07,970 --> 00:17:09,069 of cryptanalysis. 512 00:17:10,450 --> 00:17:12,189 So I will explain what's going on in 513 00:17:12,190 --> 00:17:14,439 English. And 514 00:17:14,440 --> 00:17:16,179 this will probably still look like magic. 515 00:17:16,180 --> 00:17:18,358 So what I just did in English, step 516 00:17:18,359 --> 00:17:20,439 by step, is I wrote down some 517 00:17:20,440 --> 00:17:21,939 polynomial. 518 00:17:21,940 --> 00:17:24,249 In this case, it's a linear polynomial. 519 00:17:24,250 --> 00:17:26,739 A plus X X is gonna be my unknown. 520 00:17:26,740 --> 00:17:28,419 That has a pretty small root mod P, I 521 00:17:28,420 --> 00:17:29,499 don't even know P. 522 00:17:29,500 --> 00:17:31,569 I know that P divides n I know n but I 523 00:17:31,570 --> 00:17:32,679 don't know P. 524 00:17:32,680 --> 00:17:35,049 But somehow this fact still helps me. 525 00:17:35,050 --> 00:17:36,879 I constructed a lattice basis from the 526 00:17:36,880 --> 00:17:38,619 coefficients of some polynomials that I 527 00:17:38,620 --> 00:17:40,419 could just write down that I knew that 528 00:17:40,420 --> 00:17:42,429 varnished mod p if I evaluated them and 529 00:17:42,430 --> 00:17:44,919 ah you know 530 00:17:44,920 --> 00:17:47,289 a plus X plus X squared. 531 00:17:47,290 --> 00:17:48,479 And sounds good. 532 00:17:48,480 --> 00:17:49,949 Throw them in a lot of spaces. 533 00:17:49,950 --> 00:17:52,119 Run L l on this lattice basis it gives me 534 00:17:52,120 --> 00:17:54,219 a short vector and then I turn that 535 00:17:54,220 --> 00:17:55,989 short vector into parliament polynomial 536 00:17:55,990 --> 00:17:57,759 again and then compute its roots. 537 00:17:57,760 --> 00:18:00,039 And magically the piece of the prime 538 00:18:00,040 --> 00:18:02,109 that I was looking for is one 539 00:18:02,110 --> 00:18:04,059 of the roots of this polynomial. 540 00:18:04,060 --> 00:18:05,709 And I can prove that this is the case. 541 00:18:05,710 --> 00:18:07,299 But this is like magic. 542 00:18:09,390 --> 00:18:10,740 The latest is doing something. 543 00:18:12,400 --> 00:18:14,649 At this point, I expect 544 00:18:14,650 --> 00:18:16,949 you're all kind of like at this point, 545 00:18:16,950 --> 00:18:17,619 you know? 546 00:18:17,620 --> 00:18:18,970 Then a miracle occurs 547 00:18:20,790 --> 00:18:22,899 where the miracle is somehow L.L. 548 00:18:22,900 --> 00:18:24,969 like you throw some crypto keys into 549 00:18:24,970 --> 00:18:28,299 El Alal and like magically 550 00:18:28,300 --> 00:18:29,410 private keys fall out. 551 00:18:31,000 --> 00:18:32,099 I don't know what happens. I mean, you 552 00:18:32,100 --> 00:18:33,669 you know, even like mathematicians who've 553 00:18:33,670 --> 00:18:35,499 been studying this stuff for years, we 554 00:18:35,500 --> 00:18:37,749 still feel like this because Lillo works 555 00:18:37,750 --> 00:18:39,309 way better than it's supposed to. 556 00:18:42,850 --> 00:18:43,850 We don't really know why. 557 00:18:45,160 --> 00:18:46,749 So there you go. 558 00:18:46,750 --> 00:18:48,999 So, yeah, you can if you 559 00:18:49,000 --> 00:18:49,989 don't believe us. 560 00:18:49,990 --> 00:18:52,119 We have fully weaponized code 561 00:18:52,120 --> 00:18:54,219 on the website. You can try it out. 562 00:18:54,220 --> 00:18:56,049 And, you know, see what you can get from 563 00:18:56,050 --> 00:18:57,050 it. 564 00:18:58,770 --> 00:19:01,149 So when I got into crypto, 565 00:19:01,150 --> 00:19:02,439 there was a lot of these studies. 566 00:19:02,440 --> 00:19:04,509 I mean, coppersmiths had published a 567 00:19:04,510 --> 00:19:06,039 paper and holograph game had made it 568 00:19:06,040 --> 00:19:07,359 comprehensible. 569 00:19:07,360 --> 00:19:08,679 And then a lots of grad students 570 00:19:08,680 --> 00:19:09,729 publishing a paper. 571 00:19:09,730 --> 00:19:11,979 What if, you know, not this piece 572 00:19:11,980 --> 00:19:14,049 of P, but that piece of P or 573 00:19:14,050 --> 00:19:16,509 this piece or some chunks or some songs? 574 00:19:16,510 --> 00:19:17,949 There were lots of theoretical papers. 575 00:19:17,950 --> 00:19:20,139 But would anybody be so 576 00:19:20,140 --> 00:19:22,119 stupid and give you a whole chunk off of 577 00:19:22,120 --> 00:19:24,489 P? I mean, Nadya was artificially cutting 578 00:19:24,490 --> 00:19:26,199 off the last eighty six bits. 579 00:19:26,200 --> 00:19:27,789 This is nothing that you would see in 580 00:19:27,790 --> 00:19:30,459 practice, not 2012. 581 00:19:30,460 --> 00:19:31,539 We had the first encounter was 582 00:19:31,540 --> 00:19:32,499 coppersmiths in the wild. 583 00:19:32,500 --> 00:19:34,659 This was just after 2093 when 584 00:19:34,660 --> 00:19:36,249 we gave our talk here that a friend of us 585 00:19:36,250 --> 00:19:38,169 said, by the way, have effected some time 586 00:19:38,170 --> 00:19:40,259 on his smart car keys and 587 00:19:40,260 --> 00:19:41,979 the look kind of funny. 588 00:19:41,980 --> 00:19:44,079 Now, fast forward until 589 00:19:44,080 --> 00:19:45,669 this year, there was a great paper at 590 00:19:45,670 --> 00:19:47,439 this year's Unix Unix conference on a 591 00:19:47,440 --> 00:19:49,629 group of Czech researchers, and they had 592 00:19:49,630 --> 00:19:52,999 noticed that some cards by Infineon. 593 00:19:53,000 --> 00:19:55,059 So it's a big German chip manufacturer. 594 00:19:55,060 --> 00:19:56,530 And if you have some of those 595 00:19:57,580 --> 00:19:59,649 external BGP drives as such, they might 596 00:19:59,650 --> 00:20:01,059 be having such a chip. 597 00:20:01,060 --> 00:20:03,129 So they turned it Roka Return 598 00:20:03,130 --> 00:20:05,079 of Coppersmiths and went the news 599 00:20:05,080 --> 00:20:07,449 sometime this fall and that noticed 600 00:20:07,450 --> 00:20:09,159 that Infineon is generating their primes 601 00:20:09,160 --> 00:20:10,239 in a very strange way. 602 00:20:12,290 --> 00:20:13,910 This is not how you generate primes. 603 00:20:16,480 --> 00:20:18,459 I mean, you can search for a whole bunch 604 00:20:18,460 --> 00:20:20,349 of those things and you you'll get a 605 00:20:20,350 --> 00:20:21,489 prime. 606 00:20:21,490 --> 00:20:22,570 But why? 607 00:20:24,320 --> 00:20:26,180 So what was known here was this M 608 00:20:27,740 --> 00:20:29,509 and was a lot of massaging and searching 609 00:20:29,510 --> 00:20:31,639 around. They had managed to get this 610 00:20:31,640 --> 00:20:34,069 a this little exponent, either 611 00:20:34,070 --> 00:20:35,629 with the GS also known that managed to 612 00:20:35,630 --> 00:20:37,639 get this aid into a sufficiently small 613 00:20:37,640 --> 00:20:39,230 set that you could search it. 614 00:20:40,490 --> 00:20:42,679 So then pick one of those 615 00:20:42,680 --> 00:20:44,779 A's computer to a 616 00:20:44,780 --> 00:20:45,780 modem. 617 00:20:47,250 --> 00:20:49,059 And use coppersmiths Mazatec to get Kay, 618 00:20:50,460 --> 00:20:52,709 you get a number, then 619 00:20:52,710 --> 00:20:55,109 probably it's a factor test. 620 00:20:55,110 --> 00:20:56,099 You don't get a number. 621 00:20:56,100 --> 00:20:57,209 Well, too bad. 622 00:20:57,210 --> 00:20:59,459 So just try this for each of those. 623 00:20:59,460 --> 00:21:01,679 These look the same like Tannadice. 624 00:21:01,680 --> 00:21:04,049 Let us and not just talk part, 625 00:21:04,050 --> 00:21:06,179 just not to mention three, but somewhat 626 00:21:06,180 --> 00:21:07,769 larger mentions in the paper that go 627 00:21:07,770 --> 00:21:09,359 through lots of variations of how we can 628 00:21:09,360 --> 00:21:11,309 trade off the number of A's. 629 00:21:11,310 --> 00:21:13,139 You have to try for the dimension of the 630 00:21:13,140 --> 00:21:15,629 letters. So there's a lot of tradeoffs. 631 00:21:15,630 --> 00:21:17,979 But this actually affected 10 632 00:21:17,980 --> 00:21:20,069 20 Forbert and 2048 bit 633 00:21:20,070 --> 00:21:22,440 hours ekis that were used in real life. 634 00:21:26,110 --> 00:21:28,489 RSA, of course, is in much more 635 00:21:28,490 --> 00:21:29,490 trouble. 636 00:21:39,040 --> 00:21:41,339 More than Shor's algorithm 637 00:21:41,340 --> 00:21:43,589 is going to factor RSA 638 00:21:43,590 --> 00:21:45,859 10, 24 hours, a two thousand forty 639 00:21:45,860 --> 00:21:47,509 eight, RSA four thousand ninety six. 640 00:21:47,510 --> 00:21:48,510 It's gonna be a nightmare. 641 00:21:50,370 --> 00:21:51,689 When is this gonna happen? 642 00:21:51,690 --> 00:21:53,879 Well, that's not entirely clear. 643 00:21:53,880 --> 00:21:54,839 There are some predictions. 644 00:21:54,840 --> 00:21:57,269 For instance, back in 2015 645 00:21:57,270 --> 00:21:59,429 when we gave the PKC hack stock. 646 00:21:59,430 --> 00:22:01,889 Mike Moscow, the deputy director 647 00:22:01,890 --> 00:22:03,959 of the Institute for Quantum Computing 648 00:22:03,960 --> 00:22:06,179 at the University of Waterloo, said half 649 00:22:06,180 --> 00:22:08,819 chance of factoring RSA 2048 650 00:22:08,820 --> 00:22:10,979 by 2031. 651 00:22:10,980 --> 00:22:13,079 And then just this 652 00:22:13,080 --> 00:22:15,209 year, Dario Gil was this is 653 00:22:15,210 --> 00:22:17,699 somebody who's the head of 654 00:22:17,700 --> 00:22:19,769 it's a vice president at IBM, the head of 655 00:22:19,770 --> 00:22:22,259 IBM. Q Now 656 00:22:22,260 --> 00:22:23,999 with a name like. Q Thinking about the 657 00:22:24,000 --> 00:22:25,829 James Bond films, this must be something 658 00:22:25,830 --> 00:22:26,759 cool. And it is. 659 00:22:26,760 --> 00:22:29,879 This is IBM's quantum computer, 660 00:22:29,880 --> 00:22:31,949 dare I say, weaponization division. 661 00:22:31,950 --> 00:22:33,809 This is their commercial quantum computer 662 00:22:33,810 --> 00:22:35,279 division. They're actually working on 663 00:22:35,280 --> 00:22:37,409 building a useful quantum computer that 664 00:22:37,410 --> 00:22:39,539 they can sell. And he says he says 665 00:22:39,540 --> 00:22:41,279 we're gonna look back in history and say 666 00:22:41,280 --> 00:22:43,439 that that five year period starting last 667 00:22:43,440 --> 00:22:45,839 year is like the real start of quantum 668 00:22:45,840 --> 00:22:47,759 technology, not just research as a 669 00:22:47,760 --> 00:22:48,839 scientific field. 670 00:22:48,840 --> 00:22:50,789 And he was advertising there, 50 Cubitt 671 00:22:50,790 --> 00:22:52,019 quantum processor. 672 00:22:52,020 --> 00:22:53,339 Now, how does this compare to what you 673 00:22:53,340 --> 00:22:54,709 need for Shor's algorithm? 674 00:22:54,710 --> 00:22:56,939 Well, the usual estimate is that 675 00:22:56,940 --> 00:22:59,369 Shor's algorithm needs two times 676 00:22:59,370 --> 00:23:01,879 the number of bits in your RSA modules 677 00:23:01,880 --> 00:23:04,269 while somebody else's RSA module is. 678 00:23:04,270 --> 00:23:05,459 That would be illegal. 679 00:23:05,460 --> 00:23:07,649 Your own test RSA modules 680 00:23:07,650 --> 00:23:08,909 that you're trying to factor, you need 681 00:23:08,910 --> 00:23:11,309 twice that number of cubits for Shor's 682 00:23:11,310 --> 00:23:12,239 algorithm to run. 683 00:23:12,240 --> 00:23:14,099 And cubits are these quantum bits inside 684 00:23:14,100 --> 00:23:14,999 a quantum computer. 685 00:23:15,000 --> 00:23:17,429 So how does that compare to maybe 686 00:23:17,430 --> 00:23:19,449 five cubits last year? 687 00:23:19,450 --> 00:23:21,839 Forty 1749 cubits this year 688 00:23:21,840 --> 00:23:23,679 to 200 cubits next year. 689 00:23:23,680 --> 00:23:25,169 It sounds like within a few years we'll 690 00:23:25,170 --> 00:23:27,359 be up to four thousand ninety six cubits. 691 00:23:27,360 --> 00:23:29,669 And that's the end for, say, 2048, 692 00:23:29,670 --> 00:23:31,919 except, well, it's actually a little 693 00:23:31,920 --> 00:23:33,599 less to panic about. 694 00:23:33,600 --> 00:23:36,449 It's gonna be a few years further because 695 00:23:36,450 --> 00:23:38,429 Shor's algorithm needs four thousand 696 00:23:38,430 --> 00:23:40,289 ninety six perfect cubits. 697 00:23:41,370 --> 00:23:43,469 And what's being built are cubits that 698 00:23:43,470 --> 00:23:44,669 only lasts a little while. 699 00:23:44,670 --> 00:23:46,259 And then they degrade and you have to do 700 00:23:46,260 --> 00:23:47,729 some sort of error correction. 701 00:23:47,730 --> 00:23:49,259 And it's not like normal error 702 00:23:49,260 --> 00:23:51,299 correction. You say the same thing three 703 00:23:51,300 --> 00:23:52,899 times, three times three times. 704 00:23:52,900 --> 00:23:54,689 And if somebody only heard it once, 705 00:23:54,690 --> 00:23:56,219 they'll figure it out. 706 00:23:56,220 --> 00:23:57,659 If they heard it twice with an error, 707 00:23:57,660 --> 00:23:59,879 they'll figure it out for four quantum 708 00:23:59,880 --> 00:24:02,039 bits. You need like a thousand 709 00:24:02,040 --> 00:24:04,289 quantum bits a thousand times your size, 710 00:24:04,290 --> 00:24:06,809 your computation to simulate 711 00:24:06,810 --> 00:24:09,179 one good cubitt. 712 00:24:09,180 --> 00:24:11,129 Assuming that you're cubits are the level 713 00:24:11,130 --> 00:24:12,809 of reliability that we think is 714 00:24:12,810 --> 00:24:15,029 reasonably achievable, which means Shaw 715 00:24:15,030 --> 00:24:17,069 needs four thousand ninety six times a 716 00:24:17,070 --> 00:24:19,139 thousand cubits and that's 717 00:24:19,140 --> 00:24:20,759 several doublings further away. 718 00:24:20,760 --> 00:24:23,549 It's gonna be some years, maybe like 2031 719 00:24:23,550 --> 00:24:25,559 before somebody in public is factoring 720 00:24:25,560 --> 00:24:27,299 RSA 2048. 721 00:24:27,300 --> 00:24:28,529 So what do we do about this? 722 00:24:28,530 --> 00:24:30,569 Well, post quantum cryptography, there's 723 00:24:30,570 --> 00:24:33,209 lots of replacements for RSA 724 00:24:33,210 --> 00:24:35,279 that we don't know how to break with. 725 00:24:35,280 --> 00:24:37,619 Quantum algorithms like Shor's algorithm 726 00:24:37,620 --> 00:24:39,419 and Nyst a year ago called for 727 00:24:39,420 --> 00:24:41,449 submissions of proposals for 728 00:24:41,450 --> 00:24:42,509 standardization. 729 00:24:42,510 --> 00:24:44,099 And they got the deadline was the end of 730 00:24:44,100 --> 00:24:46,649 last month. They got 82 submissions 731 00:24:46,650 --> 00:24:48,449 and they put up this table, which was 732 00:24:48,450 --> 00:24:51,119 classifying these submissions into 733 00:24:51,120 --> 00:24:52,129 theirs. 734 00:24:52,130 --> 00:24:53,909 Latticed based, code based, multivariate, 735 00:24:53,910 --> 00:24:55,589 hash based. You can see the numbers for 736 00:24:55,590 --> 00:24:57,449 encryption and signatures, numbers of 737 00:24:57,450 --> 00:24:59,689 submissions at peak. 738 00:24:59,690 --> 00:25:01,559 You see Hack's, we talked about code 739 00:25:01,560 --> 00:25:03,479 based and hash based because those are 740 00:25:03,480 --> 00:25:06,029 the oldest lasting 741 00:25:06,030 --> 00:25:07,409 post quantum proposals. 742 00:25:07,410 --> 00:25:09,419 There are some systems from 40 years ago 743 00:25:09,420 --> 00:25:11,519 code based on hash based proposals which 744 00:25:11,520 --> 00:25:13,839 seem to survive quantum computers. 745 00:25:13,840 --> 00:25:15,539 There are also lots of code based and 746 00:25:15,540 --> 00:25:17,909 hash based systems that are much newer, 747 00:25:17,910 --> 00:25:19,529 but at least there's some that go way 748 00:25:19,530 --> 00:25:21,329 back. And if you're willing to pay the 749 00:25:21,330 --> 00:25:23,399 expensive them, then it seems that 750 00:25:23,400 --> 00:25:25,199 you can get security. 751 00:25:25,200 --> 00:25:26,999 What that means is nobody's come up with 752 00:25:27,000 --> 00:25:28,919 a quantum algorithm that breaks them 753 00:25:28,920 --> 00:25:30,599 lattice based and multivariate. 754 00:25:30,600 --> 00:25:32,129 Those go back about 20 years. 755 00:25:32,130 --> 00:25:33,809 There's some lattice and multivariate 756 00:25:33,810 --> 00:25:35,999 proposals that we don't know how 757 00:25:36,000 --> 00:25:37,859 to break, even if somebody builds a big 758 00:25:37,860 --> 00:25:39,809 quantum computer and then other there's 759 00:25:39,810 --> 00:25:41,909 things like I Sargents published about 10 760 00:25:41,910 --> 00:25:44,099 years ago. First proposal, somebody came 761 00:25:44,100 --> 00:25:46,289 up with a pretty good quantum attack. 762 00:25:46,290 --> 00:25:47,489 Now they're super singular. 763 00:25:47,490 --> 00:25:49,289 I saw jinnies which have held up for a 764 00:25:49,290 --> 00:25:51,209 few years, but maybe they don't continue 765 00:25:51,210 --> 00:25:52,519 to hold up. 766 00:25:52,520 --> 00:25:55,169 Nyst put up a week ago. 767 00:25:55,170 --> 00:25:56,339 They list of submissions. 768 00:25:56,340 --> 00:25:57,929 So we'll be hearing quite a bit more 769 00:25:57,930 --> 00:25:59,459 about these submissions, not in this 770 00:25:59,460 --> 00:26:01,109 talk, but over the next few years as 771 00:26:01,110 --> 00:26:03,179 people study the security of these 772 00:26:03,180 --> 00:26:04,829 and figure out are these things that we 773 00:26:04,830 --> 00:26:07,109 can actually trust to protect our data 774 00:26:07,110 --> 00:26:08,789 against a big quantum computer. 775 00:26:08,790 --> 00:26:10,739 They only posted sixty nine instead of 776 00:26:10,740 --> 00:26:12,779 the 82 that they received because they 777 00:26:12,780 --> 00:26:14,489 said, well, the other 13 were not 778 00:26:14,490 --> 00:26:16,139 complete, not following the rules. 779 00:26:16,140 --> 00:26:18,209 So we're down to sixty nine submissions 780 00:26:18,210 --> 00:26:20,669 a week ago and 781 00:26:20,670 --> 00:26:24,179 now we're down to actually somewhat 782 00:26:24,180 --> 00:26:25,739 fewer submissions. 783 00:26:25,740 --> 00:26:27,689 So there's some that I put and read here 784 00:26:27,690 --> 00:26:29,819 three hours after Nyst 785 00:26:29,820 --> 00:26:32,129 posted this list of submissions, 786 00:26:32,130 --> 00:26:33,130 I. 787 00:26:34,630 --> 00:26:37,359 Guess again is in red there. 788 00:26:37,360 --> 00:26:39,519 Lawrence Penny, who might be in the 789 00:26:39,520 --> 00:26:40,989 audience. 790 00:26:40,990 --> 00:26:42,699 And in any case, he'll be able to see the 791 00:26:42,700 --> 00:26:43,719 videotape later. 792 00:26:43,720 --> 00:26:46,299 He posted a script which retrieves 793 00:26:46,300 --> 00:26:48,509 a guess again, plain text from a cipher 794 00:26:48,510 --> 00:26:50,829 text without the secret key. 795 00:26:50,830 --> 00:26:52,359 So that's the end of guess again. 796 00:26:52,360 --> 00:26:54,249 And that was it. OK. Three hours and 10 797 00:26:54,250 --> 00:26:56,119 minutes. That's good work. 798 00:26:56,120 --> 00:26:57,430 Yeah. All right, Lawrence. 799 00:27:03,310 --> 00:27:05,689 Are VB and other one, they're 800 00:27:05,690 --> 00:27:07,699 also broken by somebody named Lawrence 801 00:27:07,700 --> 00:27:09,079 Penney. 802 00:27:09,080 --> 00:27:10,729 And then let's see, OK. 803 00:27:10,730 --> 00:27:13,069 HK 17, that's one that Tonya and I 804 00:27:13,070 --> 00:27:14,329 put up the script that breaks 805 00:27:15,470 --> 00:27:16,619 rack costs. 806 00:27:16,620 --> 00:27:19,129 That's one where that's actually, 807 00:27:19,130 --> 00:27:20,629 I should say, the three that I mentioned 808 00:27:20,630 --> 00:27:22,429 before, HK 17 RGV. 809 00:27:22,430 --> 00:27:24,559 Guess again, those are other submissions 810 00:27:24,560 --> 00:27:25,879 and they're maybe not. Things have been 811 00:27:25,880 --> 00:27:27,019 studied so much. 812 00:27:27,020 --> 00:27:28,819 What about a code based submission like 813 00:27:28,820 --> 00:27:30,979 Rack Costs, random code based signature 814 00:27:30,980 --> 00:27:33,159 scheme. Well, 815 00:27:33,160 --> 00:27:35,689 Tonya and I and 816 00:27:35,690 --> 00:27:37,639 also Andre is hosting and also somebody 817 00:27:37,640 --> 00:27:38,720 named Lawrence Penney 818 00:27:40,040 --> 00:27:41,390 posted a script which 819 00:27:42,830 --> 00:27:44,089 well, completely breaks. 820 00:27:44,090 --> 00:27:45,589 Right. Cos actually we came up with three 821 00:27:45,590 --> 00:27:47,929 different attacks and it's maybe 822 00:27:47,930 --> 00:27:50,629 it's OK with bigger parameters, but 823 00:27:50,630 --> 00:27:51,829 not something you should use with the 824 00:27:51,830 --> 00:27:53,179 parameters they submitted. 825 00:27:53,180 --> 00:27:55,549 And then another example, Heela five 826 00:27:55,550 --> 00:27:56,779 or what. 827 00:27:56,780 --> 00:27:57,979 Dutch people in the audience. 828 00:27:57,980 --> 00:27:59,869 This is called Helus. 829 00:27:59,870 --> 00:28:02,269 This proposal is well 830 00:28:02,270 --> 00:28:05,179 it's OK if you use it with signatures 831 00:28:05,180 --> 00:28:07,039 that stopped chosen ciphertext attacks. 832 00:28:07,040 --> 00:28:08,239 If you have somebody else giving you a 833 00:28:08,240 --> 00:28:09,499 signature scheme like A.l. 834 00:28:09,500 --> 00:28:11,569 S. But the submission claimed 835 00:28:11,570 --> 00:28:13,639 chosen cipher text attack 836 00:28:13,640 --> 00:28:14,719 security. 837 00:28:14,720 --> 00:28:16,969 And we posted a script. 838 00:28:16,970 --> 00:28:18,149 We. 839 00:28:18,150 --> 00:28:19,639 Well, Tanya. Me again. 840 00:28:19,640 --> 00:28:22,039 And then who wrote but I don't drink. 841 00:28:22,040 --> 00:28:24,649 And also somebody named Lawrence Penny. 842 00:28:24,650 --> 00:28:26,479 He got to watch out for this guy. 843 00:28:26,480 --> 00:28:26,809 All right. 844 00:28:26,810 --> 00:28:28,549 So at this point, there's still some 845 00:28:28,550 --> 00:28:29,969 submissions left and 846 00:28:31,100 --> 00:28:32,659 we'll be hearing more about what gets 847 00:28:32,660 --> 00:28:34,339 broken by Lawrence and maybe some other 848 00:28:34,340 --> 00:28:35,450 people in the future. 849 00:28:44,310 --> 00:28:46,409 OK, so since we heard so 850 00:28:46,410 --> 00:28:47,699 much about breaking stuff, let's break 851 00:28:47,700 --> 00:28:49,649 some more RSA. Just for fun. 852 00:28:51,650 --> 00:28:54,199 So I want to show you another variation 853 00:28:54,200 --> 00:28:56,169 of how to break RSA with lattices, which 854 00:28:56,170 --> 00:28:58,249 is the coppersmiths small public 855 00:28:58,250 --> 00:28:59,569 exponent attack. 856 00:28:59,570 --> 00:29:00,499 So. 857 00:29:00,500 --> 00:29:02,029 All right. This is audience participation 858 00:29:02,030 --> 00:29:03,289 time. 859 00:29:03,290 --> 00:29:04,219 Here's some code. 860 00:29:04,220 --> 00:29:06,679 All right. So I take a message which is 861 00:29:06,680 --> 00:29:08,389 squeamish. Orsa Farraj. 862 00:29:08,390 --> 00:29:09,619 How do you pronounce that? 863 00:29:09,620 --> 00:29:11,719 I turn it into an integer by making 864 00:29:11,720 --> 00:29:12,769 it base 35. 865 00:29:12,770 --> 00:29:13,999 This is just so I can, like, print it out 866 00:29:14,000 --> 00:29:15,439 nicely on the screen. 867 00:29:15,440 --> 00:29:16,879 There's nothing really complicated going 868 00:29:16,880 --> 00:29:18,709 on here. I generate a perfectly 869 00:29:18,710 --> 00:29:21,079 legitimate RSA modulus and 870 00:29:21,080 --> 00:29:23,929 it has 10, 24 bits. 871 00:29:23,930 --> 00:29:26,119 And I encrypt my 872 00:29:26,120 --> 00:29:28,309 message with RSA by cuming it 873 00:29:28,310 --> 00:29:29,479 mod and. 874 00:29:29,480 --> 00:29:31,489 All right. There's a problem here. 875 00:29:31,490 --> 00:29:32,490 What's the problem? 876 00:29:34,780 --> 00:29:36,069 It's too small. 877 00:29:36,070 --> 00:29:37,269 Thank you. Good. 878 00:29:37,270 --> 00:29:38,319 Some people in the audience are still 879 00:29:38,320 --> 00:29:39,319 following. 880 00:29:39,320 --> 00:29:41,529 OK, we've got a problem, which 881 00:29:41,530 --> 00:29:44,439 is that the ciphertext 882 00:29:44,440 --> 00:29:46,449 is smaller than N. 883 00:29:46,450 --> 00:29:48,729 And in fact, slike the message cubed 884 00:29:48,730 --> 00:29:50,529 is going to be smaller than N. 885 00:29:50,530 --> 00:29:52,449 So this like modular reduction mod end 886 00:29:52,450 --> 00:29:53,919 doesn't do anything. 887 00:29:53,920 --> 00:29:55,779 And we can just compute cube roots over 888 00:29:55,780 --> 00:29:58,689 the integers, like easily. 889 00:29:58,690 --> 00:30:01,089 So this is not secure RSA 890 00:30:01,090 --> 00:30:03,089 encryption problem. 891 00:30:03,090 --> 00:30:04,689 This is this is why you use padding 892 00:30:04,690 --> 00:30:05,770 schemes for RSA. 893 00:30:06,910 --> 00:30:08,409 One of the many reasons. 894 00:30:08,410 --> 00:30:10,809 OK. So messages to small 895 00:30:10,810 --> 00:30:12,669 message, cube lesson and module reduction 896 00:30:12,670 --> 00:30:14,229 does nothing. That means you're not 897 00:30:14,230 --> 00:30:15,230 actually doing RSA. 898 00:30:16,500 --> 00:30:18,599 OK, here's a variant 899 00:30:18,600 --> 00:30:20,159 of this problem, but it's a little bit 900 00:30:20,160 --> 00:30:22,649 more complicated. So I made my module's 901 00:30:22,650 --> 00:30:23,969 and a little bit smaller just so the 902 00:30:23,970 --> 00:30:26,039 example could fit on the screen. 903 00:30:26,040 --> 00:30:27,989 But, like, that's not going to be the 904 00:30:27,990 --> 00:30:29,519 issue here. So I generate a perfectly 905 00:30:29,520 --> 00:30:31,979 legitimate RSA modulus n 906 00:30:31,980 --> 00:30:32,969 300 bits. 907 00:30:32,970 --> 00:30:34,199 I'm not going to try to factor it, even 908 00:30:34,200 --> 00:30:36,149 though it's probably possible. 909 00:30:36,150 --> 00:30:38,219 So now I have a message, which 910 00:30:38,220 --> 00:30:41,129 is the password for today is swordfish. 911 00:30:41,130 --> 00:30:42,539 Turn it into an integer in the same way 912 00:30:42,540 --> 00:30:43,889 as before. Not trying to do anything 913 00:30:43,890 --> 00:30:45,059 super complicated. 914 00:30:45,060 --> 00:30:47,309 I do textbook RSA encryption by cubing 915 00:30:47,310 --> 00:30:49,209 the message mod n. 916 00:30:49,210 --> 00:30:50,009 OK. 917 00:30:50,010 --> 00:30:52,229 So since I, 918 00:30:52,230 --> 00:30:53,939 since my message is logger and my my 919 00:30:53,940 --> 00:30:55,769 module is smaller, I don't have the same 920 00:30:55,770 --> 00:30:57,389 issue as before. Or if I just try to 921 00:30:57,390 --> 00:30:59,519 compute the cube root of the cipher text. 922 00:30:59,520 --> 00:31:01,139 It is not equal to the message. 923 00:31:01,140 --> 00:31:03,060 So I've, I've not broken that way 924 00:31:04,230 --> 00:31:06,449 but through might still be an issue. 925 00:31:06,450 --> 00:31:08,669 So maybe like since this 926 00:31:08,670 --> 00:31:10,409 message has a particular format, you 927 00:31:10,410 --> 00:31:11,969 could imagine that attacker could guess 928 00:31:11,970 --> 00:31:13,979 like the message is the password for 929 00:31:13,980 --> 00:31:16,319 today is something and maybe 930 00:31:16,320 --> 00:31:18,089 there's like whatever password it is. 931 00:31:18,090 --> 00:31:19,319 And maybe they know that it has nine 932 00:31:19,320 --> 00:31:20,609 characters, but they don't know what it 933 00:31:20,610 --> 00:31:21,329 is. 934 00:31:21,330 --> 00:31:23,919 So can they compute that? 935 00:31:23,920 --> 00:31:26,489 So maybe the attacker has guessed 936 00:31:26,490 --> 00:31:28,379 that the message looks like this where 937 00:31:28,380 --> 00:31:31,109 they don't know some chunk of 938 00:31:31,110 --> 00:31:33,329 the message, but they know the rest of it 939 00:31:33,330 --> 00:31:34,330 through some attack. 940 00:31:35,070 --> 00:31:36,699 So I have my secret value or by it my 941 00:31:36,700 --> 00:31:38,250 evaluation that the attacker has guessed. 942 00:31:39,660 --> 00:31:40,890 Here comes the magic trick again. 943 00:31:42,030 --> 00:31:44,159 So I construct 944 00:31:44,160 --> 00:31:45,209 a matrix. 945 00:31:45,210 --> 00:31:47,519 This is gonna be a lot of spaces from 946 00:31:47,520 --> 00:31:50,459 my guess is what the message looks like 947 00:31:50,460 --> 00:31:52,769 and the cipher text 948 00:31:52,770 --> 00:31:54,119 and the modulus. 949 00:31:55,200 --> 00:31:56,549 And then I've just like filled in some 950 00:31:56,550 --> 00:31:58,349 zeros for for the part of the message 951 00:31:58,350 --> 00:32:00,459 that I, I don't know yet. 952 00:32:00,460 --> 00:32:02,639 OK, so I have a lot of spaces. 953 00:32:02,640 --> 00:32:04,859 What do I do is that I run LML on it as 954 00:32:04,860 --> 00:32:08,009 before I get some vector. 955 00:32:08,010 --> 00:32:10,589 I construct a polynomial from 956 00:32:10,590 --> 00:32:12,210 the coefficients of this vector. 957 00:32:13,470 --> 00:32:16,309 I'm, you know, magic. 958 00:32:16,310 --> 00:32:17,389 And when I look at the roots of the 959 00:32:17,390 --> 00:32:19,669 polynomial, I got the piece 960 00:32:19,670 --> 00:32:21,019 of the message that I didn't know. 961 00:32:21,020 --> 00:32:22,609 Back out again. 962 00:32:22,610 --> 00:32:23,610 Magic trick. 963 00:32:29,880 --> 00:32:31,139 I hope you guys have been scared into 964 00:32:31,140 --> 00:32:33,299 never trying to implement RSA on your own 965 00:32:33,300 --> 00:32:34,300 at this point. 966 00:32:36,130 --> 00:32:38,499 So, OK, what's going on? 967 00:32:38,500 --> 00:32:40,569 It looks very much like before, so I'm 968 00:32:40,570 --> 00:32:41,709 going to write this in English. 969 00:32:41,710 --> 00:32:43,509 I don't expect you to necessarily be able 970 00:32:43,510 --> 00:32:45,129 to, like, prove that this works, but just 971 00:32:45,130 --> 00:32:46,179 to, like, verify that. 972 00:32:46,180 --> 00:32:48,219 I don't know, like we're doing something. 973 00:32:48,220 --> 00:32:49,839 I wrote down some polynomial that has 974 00:32:49,840 --> 00:32:50,769 this pretty small root. 975 00:32:50,770 --> 00:32:52,539 So in this case, I do. 976 00:32:52,540 --> 00:32:53,919 I don't know what swordfishing is, but I 977 00:32:53,920 --> 00:32:56,349 know that swordfish plus the thing that I 978 00:32:56,350 --> 00:32:58,539 guessed for the message 979 00:32:58,540 --> 00:32:59,869 is, is my message. 980 00:32:59,870 --> 00:33:01,989 And I know if I cube that mod and then 981 00:33:01,990 --> 00:33:03,129 I get the cipher text. 982 00:33:03,130 --> 00:33:05,529 So, you know, 983 00:33:05,530 --> 00:33:07,659 swordfish plus A cubed minus 984 00:33:07,660 --> 00:33:09,330 C should be zero mod and. 985 00:33:10,460 --> 00:33:12,829 Some polynomial magic. 986 00:33:12,830 --> 00:33:14,959 I construct a lattice of the coefficient 987 00:33:14,960 --> 00:33:17,119 vectors of polynomials that vanishment 988 00:33:17,120 --> 00:33:19,219 n one of them is the thing that I wrote 989 00:33:19,220 --> 00:33:20,569 down there and I don't know, like end 990 00:33:20,570 --> 00:33:22,340 times X squared seems good. 991 00:33:23,600 --> 00:33:25,759 I called El L magic 992 00:33:25,760 --> 00:33:28,249 happens and I wave my hands 993 00:33:28,250 --> 00:33:30,799 and then somehow I got a polynomial 994 00:33:30,800 --> 00:33:33,259 out of El Alal and my solution, 995 00:33:33,260 --> 00:33:35,929 swordfish was a root of the corresponding 996 00:33:35,930 --> 00:33:37,069 Spaull polynomial. 997 00:33:38,090 --> 00:33:40,549 So this is coppersmiths small 998 00:33:42,200 --> 00:33:43,909 RSA exponent attack. 999 00:33:43,910 --> 00:33:45,769 And there's a bunch of variance of it. 1000 00:33:45,770 --> 00:33:46,770 It's super cool. 1001 00:33:47,870 --> 00:33:49,369 So if I have just freaked you out, 1002 00:33:50,690 --> 00:33:52,129 here's some countermeasures against 1003 00:33:52,130 --> 00:33:54,479 Coppersmith sort of padding, attack, 1004 00:33:54,480 --> 00:33:57,529 small exponent, etc.. 1005 00:33:57,530 --> 00:33:59,119 You could if you're if you're worried 1006 00:33:59,120 --> 00:34:01,669 about this donees RSA, it's one option. 1007 00:34:01,670 --> 00:34:03,409 If you must use RSA, use a proper padding 1008 00:34:03,410 --> 00:34:06,169 scheme, RSA, OEP, that kind of thing. 1009 00:34:06,170 --> 00:34:08,089 If you must use RSA, don't use small 1010 00:34:08,090 --> 00:34:09,019 exponent ee. 1011 00:34:09,020 --> 00:34:11,149 Like use exponent eyerly six five five 1012 00:34:11,150 --> 00:34:12,439 three seven. Then this definitely doesn't 1013 00:34:12,440 --> 00:34:13,440 work. 1014 00:34:18,170 --> 00:34:19,849 So we actually didn't come into it. 1015 00:34:21,080 --> 00:34:22,638 We didn't want me to talk about RSA the 1016 00:34:22,639 --> 00:34:23,809 whole time. 1017 00:34:23,810 --> 00:34:25,399 We also talk. Wanted to talk about 1018 00:34:25,400 --> 00:34:27,888 constructive uses of lettuces 1019 00:34:27,889 --> 00:34:29,419 and sort of talked about one of the 1020 00:34:29,420 --> 00:34:31,369 oldest of the let space criticisms called 1021 00:34:31,370 --> 00:34:32,269 entra. 1022 00:34:32,270 --> 00:34:34,879 It's due to hefting Pyfrom Souleyman. 1023 00:34:34,880 --> 00:34:36,379 The publication is eight. 1024 00:34:36,380 --> 00:34:38,079 There's even some preprint which are know 1025 00:34:38,080 --> 00:34:39,948 online from Ninety-Six. 1026 00:34:39,949 --> 00:34:42,049 And they were looking for just some 1027 00:34:42,050 --> 00:34:43,189 alternatives for hours. 1028 00:34:43,190 --> 00:34:45,379 ATCC, they're pretty 1029 00:34:45,380 --> 00:34:46,759 aggressive in their advertisements and 1030 00:34:46,760 --> 00:34:48,408 they did manage to get speeds that were 1031 00:34:48,409 --> 00:34:50,479 faster. They looked at curves and 1032 00:34:50,480 --> 00:34:51,480 ah, as a 1033 00:34:52,810 --> 00:34:54,678 competitor, as you see, they still had 1034 00:34:54,679 --> 00:34:56,899 larger key sizes and larger ciphertext. 1035 00:34:56,900 --> 00:34:59,149 But they were kind of going forward 1036 00:34:59,150 --> 00:35:00,479 just as an all competition. 1037 00:35:00,480 --> 00:35:02,449 They were not so much running the oh, we 1038 00:35:02,450 --> 00:35:04,489 might be secure against C1 computers. 1039 00:35:04,490 --> 00:35:06,409 Even though Shor's paper had appeared, 1040 00:35:06,410 --> 00:35:07,999 this was not so much on the mind of 1041 00:35:08,000 --> 00:35:09,000 people. 1042 00:35:09,620 --> 00:35:12,109 Now they did a signature system 1043 00:35:12,110 --> 00:35:13,699 and an encryption system. 1044 00:35:13,700 --> 00:35:16,039 And these signature system 1045 00:35:16,040 --> 00:35:18,499 is multiple signature 1046 00:35:18,500 --> 00:35:19,459 systems. 1047 00:35:19,460 --> 00:35:20,630 Had a bit of a bumpy ride. 1048 00:35:21,830 --> 00:35:24,009 I remember being a trip to 2006 when 1049 00:35:24,010 --> 00:35:26,359 phone again was giving yet another talk, 1050 00:35:26,360 --> 00:35:27,899 breaking some of the interestingly just 1051 00:35:27,900 --> 00:35:30,080 systems. And he was like, so 1052 00:35:31,130 --> 00:35:33,919 who in the audience has not yet broken 1053 00:35:33,920 --> 00:35:35,270 an interesting control system? 1054 00:35:37,250 --> 00:35:38,889 Well, for the designers, they look limit 1055 00:35:38,890 --> 00:35:40,249 board, I like that 1056 00:35:42,270 --> 00:35:44,359 description system has held up 1057 00:35:44,360 --> 00:35:45,709 better that at the beginning a little bit 1058 00:35:45,710 --> 00:35:47,809 too small parameters, but 1059 00:35:47,810 --> 00:35:48,920 in principle this was fine. 1060 00:35:49,940 --> 00:35:51,529 And so there was a bunch of cryptanalysis 1061 00:35:51,530 --> 00:35:52,789 during the last 20 years, but there 1062 00:35:52,790 --> 00:35:54,919 wasn't all that much research 1063 00:35:54,920 --> 00:35:57,169 into how to use it efficiently. 1064 00:35:57,170 --> 00:35:59,389 And then just because you have a nice 1065 00:35:59,390 --> 00:36:01,489 math system like 1066 00:36:01,490 --> 00:36:03,829 ours, a you take em to the three, 1067 00:36:03,830 --> 00:36:06,379 all the things you've just seen are 1068 00:36:06,380 --> 00:36:08,779 proper are it's a but improperly 1069 00:36:08,780 --> 00:36:09,679 used. 1070 00:36:09,680 --> 00:36:11,419 So secure use, which is usually big 1071 00:36:11,420 --> 00:36:13,759 issue, but not much 1072 00:36:13,760 --> 00:36:15,049 happened on that. 1073 00:36:15,050 --> 00:36:17,089 I think partially because ah the entry 1074 00:36:17,090 --> 00:36:19,159 company had decided to patent this 1075 00:36:19,160 --> 00:36:21,379 thing and we are all like, 1076 00:36:21,380 --> 00:36:23,839 why should I spend my time investigating 1077 00:36:23,840 --> 00:36:25,549 a system which I can't actually freely 1078 00:36:25,550 --> 00:36:26,719 use afterwards. 1079 00:36:26,720 --> 00:36:28,279 By now the patent has expired. 1080 00:36:28,280 --> 00:36:30,019 So I'm happy to talk about it and say, 1081 00:36:30,020 --> 00:36:32,179 well, let's look at how it works 1082 00:36:32,180 --> 00:36:33,539 and maybe we can break some stuff. 1083 00:36:36,330 --> 00:36:37,739 First of all, you have to understand how 1084 00:36:37,740 --> 00:36:39,839 entra works, so ways 1085 00:36:39,840 --> 00:36:41,969 are as AFC and you need pretty large 1086 00:36:41,970 --> 00:36:44,189 integers with entra, we 1087 00:36:44,190 --> 00:36:45,270 need polynomials. 1088 00:36:46,620 --> 00:36:49,019 And there is one system, PROMETA, 1089 00:36:49,020 --> 00:36:51,359 which is N, which is the D 1090 00:36:51,360 --> 00:36:53,400 limit on the degree of these polynomials. 1091 00:36:54,640 --> 00:36:56,269 These are just integer polynomials, so 1092 00:36:56,270 --> 00:36:58,459 you have coefficient zero one two minus 1093 00:36:58,460 --> 00:36:59,460 five and whatever. 1094 00:37:00,500 --> 00:37:02,049 And then for the examples, we're gonna 1095 00:37:02,050 --> 00:37:04,429 choose slightly less than 250, like 1096 00:37:04,430 --> 00:37:06,349 seven or something. 1097 00:37:06,350 --> 00:37:08,119 If you have two such elements and you 1098 00:37:08,120 --> 00:37:10,219 want to add them, you can 1099 00:37:10,220 --> 00:37:11,989 just do this coefficient wise. 1100 00:37:11,990 --> 00:37:14,089 So the Azera plus B zero is 1101 00:37:14,090 --> 00:37:16,339 a coefficient of one, 1102 00:37:16,340 --> 00:37:19,009 A one plus B one is the coefficient of X. 1103 00:37:19,010 --> 00:37:21,259 And so until all the way till extra 1104 00:37:21,260 --> 00:37:23,329 the N minus one, which has 1105 00:37:23,330 --> 00:37:25,399 a minus a sub N minus one 1106 00:37:25,400 --> 00:37:26,449 and D up Amara's one. 1107 00:37:28,100 --> 00:37:29,569 We also want to multiply those. 1108 00:37:29,570 --> 00:37:31,169 Now if you multiply polynomial degree 1109 00:37:31,170 --> 00:37:32,849 three was one of degree four. 1110 00:37:32,850 --> 00:37:34,400 You getting something of degree seven. 1111 00:37:36,350 --> 00:37:38,239 But we won't like to have something of 1112 00:37:38,240 --> 00:37:40,339 small degrees, so we need some way of 1113 00:37:40,340 --> 00:37:41,809 wrapping around. 1114 00:37:41,810 --> 00:37:43,219 And so they define a thing called a 1115 00:37:43,220 --> 00:37:45,979 sickly convolution where you basically 1116 00:37:45,980 --> 00:37:48,109 wrap everything around after and 1117 00:37:48,110 --> 00:37:49,249 minus three. 1118 00:37:49,250 --> 00:37:50,509 Minus one. 1119 00:37:50,510 --> 00:37:52,309 And the rule for this is. 1120 00:37:54,230 --> 00:37:56,719 The coefficient of extra 1121 00:37:56,720 --> 00:37:57,720 one, for instance, 1122 00:37:58,880 --> 00:38:01,149 the aye ay I. 1123 00:38:01,150 --> 00:38:04,339 B.J., these two indices, 1124 00:38:04,340 --> 00:38:06,439 they will sum up to one 1125 00:38:06,440 --> 00:38:07,440 or end plus one. 1126 00:38:08,630 --> 00:38:10,669 And for the X to the end minus one, they 1127 00:38:10,670 --> 00:38:12,519 will sum up to the. 1128 00:38:12,520 --> 00:38:14,780 And minus one. So and minus one bloops. 1129 00:38:16,730 --> 00:38:18,649 There will some up to X months to end, 1130 00:38:18,650 --> 00:38:19,639 minus one. 1131 00:38:19,640 --> 00:38:21,799 OK. So this is her explanation with which 1132 00:38:21,800 --> 00:38:22,789 we can compute. 1133 00:38:22,790 --> 00:38:24,079 We can work with it. 1134 00:38:24,080 --> 00:38:25,789 We can teach it to a computer. 1135 00:38:25,790 --> 00:38:27,109 If you want to know where it comes from 1136 00:38:27,110 --> 00:38:28,789 is the same slide with a little bit more 1137 00:38:28,790 --> 00:38:30,079 math notation. 1138 00:38:30,080 --> 00:38:31,549 So what we're actually doing is we work 1139 00:38:31,550 --> 00:38:33,229 in the polynomial ring. 1140 00:38:33,230 --> 00:38:34,759 That's just a fancy way of saying Polearm 1141 00:38:34,760 --> 00:38:36,439 is an integer coefficients. 1142 00:38:36,440 --> 00:38:39,209 And then we reduce modulo 1143 00:38:39,210 --> 00:38:40,309 X to the end minus one. 1144 00:38:40,310 --> 00:38:42,349 This is the same kind of function where 1145 00:38:42,350 --> 00:38:44,579 we say we would use, what, seven, 1146 00:38:44,580 --> 00:38:46,759 but we take every model of seven 1147 00:38:46,760 --> 00:38:48,679 and replace it by zero. 1148 00:38:48,680 --> 00:38:50,929 Here, replace every multiple of X 1149 00:38:50,930 --> 00:38:53,209 to the N minus one by zero. 1150 00:38:53,210 --> 00:38:55,909 Or you take extra the N 1151 00:38:55,910 --> 00:38:56,910 and replace it by one. 1152 00:38:58,580 --> 00:39:00,649 And then all the operations 1153 00:39:00,650 --> 00:39:01,759 just work the same way. 1154 00:39:01,760 --> 00:39:02,929 Except that we have to. Right. 1155 00:39:02,930 --> 00:39:03,930 And minus one there. 1156 00:39:05,000 --> 00:39:07,040 Well let's see some numerical examples. 1157 00:39:08,260 --> 00:39:09,260 All right, 1158 00:39:11,230 --> 00:39:12,819 starting with a little bit of 1159 00:39:12,820 --> 00:39:14,829 incomprehensible sage notation for 1160 00:39:14,830 --> 00:39:17,049 creating a type of Class Z, 1161 00:39:17,050 --> 00:39:19,149 X, which is going to have our polynomial 1162 00:39:19,150 --> 00:39:21,519 objects and looking at an example that 1163 00:39:21,520 --> 00:39:23,799 this F here is a polynomial four 1164 00:39:23,800 --> 00:39:25,889 times X squared, plus X plus three. 1165 00:39:25,890 --> 00:39:27,009 So two, three terms in that. 1166 00:39:27,010 --> 00:39:28,059 Three things being added up. 1167 00:39:28,060 --> 00:39:30,039 The coefficients are the integers four 1168 00:39:30,040 --> 00:39:32,049 and one and three that are multiplied by 1169 00:39:32,050 --> 00:39:34,109 X squared and X and one. 1170 00:39:34,110 --> 00:39:35,199 This is degree two. 1171 00:39:35,200 --> 00:39:36,849 That's the biggest power of X that you 1172 00:39:36,850 --> 00:39:37,749 see there. 1173 00:39:37,750 --> 00:39:40,179 The exponent that if you multiply, 1174 00:39:40,180 --> 00:39:41,979 then the distributive law says you're 1175 00:39:41,980 --> 00:39:44,079 supposed to multiply each term that 1176 00:39:44,080 --> 00:39:45,669 you're adding up by every other term 1177 00:39:45,670 --> 00:39:47,229 you're adding up like if you multiply F 1178 00:39:47,230 --> 00:39:49,239 times X, you you multiply the three times 1179 00:39:49,240 --> 00:39:51,369 X, get three X, multiply X times X, 1180 00:39:51,370 --> 00:39:52,809 get X squared and so on. 1181 00:39:52,810 --> 00:39:54,189 And all the times here, it's just built 1182 00:39:54,190 --> 00:39:55,419 into it. 1183 00:39:55,420 --> 00:39:57,069 Another example, multiplying by this 1184 00:39:57,070 --> 00:39:59,169 other polynomial g OK is a bunch 1185 00:39:59,170 --> 00:40:00,339 of things. I won't go through all of 1186 00:40:00,340 --> 00:40:02,289 them, but looking at the last coefficient 1187 00:40:02,290 --> 00:40:04,389 of f that three it gets multiplied. 1188 00:40:04,390 --> 00:40:06,459 Maybe I'll point with the males here, the 1189 00:40:06,460 --> 00:40:09,099 three and F gets multiplied by the two 1190 00:40:09,100 --> 00:40:11,519 in G and that gives the six and 1191 00:40:11,520 --> 00:40:13,509 the three and F gets multiplied by seven 1192 00:40:13,510 --> 00:40:15,489 times X giving twenty one times X.. 1193 00:40:15,490 --> 00:40:17,019 Wait a minute, twenty three times X while 1194 00:40:17,020 --> 00:40:19,269 there's also a two times X 1195 00:40:19,270 --> 00:40:20,769 which adds to the twenty one times X 1196 00:40:20,770 --> 00:40:22,619 giving twenty three times X etc.. 1197 00:40:22,620 --> 00:40:24,369 And you can multiply all these or just 1198 00:40:24,370 --> 00:40:26,529 tell Sage do the work for you. 1199 00:40:26,530 --> 00:40:29,079 All right. What about that multiplication 1200 00:40:29,080 --> 00:40:31,169 operation with the end coefficient 1201 00:40:31,170 --> 00:40:33,279 things. Well this is how you say that 1202 00:40:33,280 --> 00:40:35,829 and say you take two inputs 1203 00:40:35,830 --> 00:40:37,809 and coefficient polynomials F and G and 1204 00:40:37,810 --> 00:40:38,709 multiply them. 1205 00:40:38,710 --> 00:40:40,959 The percent is mollet just like in C mod 1206 00:40:40,960 --> 00:40:42,399 X to the N minus one. 1207 00:40:42,400 --> 00:40:44,619 For instance, if and is three then 1208 00:40:44,620 --> 00:40:47,109 same polynomial F if you 1209 00:40:47,110 --> 00:40:49,179 multiply F by X 1210 00:40:49,180 --> 00:40:50,919 then you get the same three X and X 1211 00:40:50,920 --> 00:40:52,539 squared and for X cubed. 1212 00:40:52,540 --> 00:40:54,219 And what happened to the four excuse that 1213 00:40:54,220 --> 00:40:55,299 turned into four. 1214 00:40:55,300 --> 00:40:57,519 If you see X to the end it turns into one 1215 00:40:57,520 --> 00:40:58,809 and if you see X in the end plus one 1216 00:40:58,810 --> 00:41:00,279 turns into X and so on. 1217 00:41:00,280 --> 00:41:02,529 And if you multiply F by X squared 1218 00:41:02,530 --> 00:41:04,479 then well it rotates the coefficients 1219 00:41:04,480 --> 00:41:06,789 again. And another example, 1220 00:41:06,790 --> 00:41:08,829 the same F Angie from before. 1221 00:41:08,830 --> 00:41:10,989 If you do the convolution, you 1222 00:41:10,990 --> 00:41:13,119 multiply f Angie and then replace 1223 00:41:13,120 --> 00:41:15,189 X cubed with one, which means 1224 00:41:15,190 --> 00:41:16,989 you add the twenty nine into the six 1225 00:41:16,990 --> 00:41:19,119 producing thirty five and so on, leaving 1226 00:41:19,120 --> 00:41:20,909 you with only N coefficients. 1227 00:41:22,310 --> 00:41:24,369 All right, back to the description. 1228 00:41:24,370 --> 00:41:26,229 You've gotten a little more comfortable 1229 00:41:26,230 --> 00:41:27,879 with our elements here. 1230 00:41:27,880 --> 00:41:29,199 So we are going to continue working with 1231 00:41:29,200 --> 00:41:30,349 polynomials. 1232 00:41:30,350 --> 00:41:31,569 But if you saw the last examples. 1233 00:41:31,570 --> 00:41:34,119 But then if you imagine 1234 00:41:34,120 --> 00:41:36,459 multiplying, multiplying or explanation, 1235 00:41:36,460 --> 00:41:38,289 you see that the coefficients get larger 1236 00:41:38,290 --> 00:41:39,290 and larger. 1237 00:41:39,850 --> 00:41:41,309 So similar to how our is a. 1238 00:41:41,310 --> 00:41:43,359 We also need to it use what n else we 1239 00:41:43,360 --> 00:41:45,309 gonna see these same scrimmaged also 1240 00:41:45,310 --> 00:41:46,659 projects before. 1241 00:41:46,660 --> 00:41:47,829 We will need to have some well. 1242 00:41:47,830 --> 00:41:49,599 Reduction here. So there will be another 1243 00:41:49,600 --> 00:41:51,100 system. Prometa called Q. 1244 00:41:52,910 --> 00:41:54,319 Doesn't have to be prime, it's typically 1245 00:41:54,320 --> 00:41:56,279 extra power of two. 1246 00:41:56,280 --> 00:41:58,489 And it just means we will have 1247 00:41:58,490 --> 00:42:00,679 our coefficients bounded by it 1248 00:42:00,680 --> 00:42:01,999 most. Q. So when you wish. 1249 00:42:02,000 --> 00:42:03,309 Q We would use MOTD. 1250 00:42:04,490 --> 00:42:06,019 There is one condition that Q is not 1251 00:42:06,020 --> 00:42:07,549 three, because we will also have three 1252 00:42:07,550 --> 00:42:09,679 running around as another thing where 1253 00:42:09,680 --> 00:42:10,680 we reduce. 1254 00:42:11,600 --> 00:42:13,159 So we'll have two things to reduce by 1255 00:42:13,160 --> 00:42:15,799 will have this extra the end minus one. 1256 00:42:15,800 --> 00:42:17,599 So we will reduce the degree 1257 00:42:18,890 --> 00:42:21,049 and we will reduce the coefficients. 1258 00:42:21,050 --> 00:42:22,999 So every single coefficient, each of 1259 00:42:23,000 --> 00:42:25,879 those N coefficients, we will apply 1260 00:42:25,880 --> 00:42:27,979 reduction or Q or reduction what three 1261 00:42:27,980 --> 00:42:28,980 to them. 1262 00:42:29,900 --> 00:42:32,329 Good. We're now ready to get 1263 00:42:32,330 --> 00:42:35,359 entra public keys and private keys. 1264 00:42:35,360 --> 00:42:38,749 What we do is we pick two 1265 00:42:38,750 --> 00:42:40,589 such polynomials. 1266 00:42:40,590 --> 00:42:41,959 We're gonna be even more restrictive 1267 00:42:41,960 --> 00:42:44,149 because we to have them small. 1268 00:42:44,150 --> 00:42:46,039 So this f Anji will only be allowed to 1269 00:42:46,040 --> 00:42:48,709 have zeros and then in a few 1270 00:42:48,710 --> 00:42:49,849 plus and minus ones. 1271 00:42:52,740 --> 00:42:54,729 So this is much, much smaller than Que 1272 00:42:54,730 --> 00:42:56,789 will just allow a few ones 1273 00:42:56,790 --> 00:42:58,049 and a few minus ones. That's going to be 1274 00:42:58,050 --> 00:43:00,119 fixed. Number of those four F and A 1275 00:43:00,120 --> 00:43:02,189 fixed some of those four G. 1276 00:43:02,190 --> 00:43:04,359 And then while an hour is a 1277 00:43:04,360 --> 00:43:06,449 you multiply our two things here, 1278 00:43:06,450 --> 00:43:07,919 we have a different operations. 1279 00:43:07,920 --> 00:43:10,409 We will search for an H 1280 00:43:10,410 --> 00:43:12,779 such that H times F was this second 1281 00:43:12,780 --> 00:43:13,859 convolution. 1282 00:43:13,860 --> 00:43:14,939 We'll give three times G. 1283 00:43:18,000 --> 00:43:19,289 Sometimes it doesn't work. 1284 00:43:19,290 --> 00:43:20,669 So if to try again. 1285 00:43:20,670 --> 00:43:22,169 So if it doesn't work, we have to try 1286 00:43:22,170 --> 00:43:23,170 with a different F. 1287 00:43:24,250 --> 00:43:26,259 When you think of the notation we 1288 00:43:26,260 --> 00:43:27,669 actually dividing by this F 1289 00:43:28,690 --> 00:43:31,419 and not all F's are inevitable. 1290 00:43:31,420 --> 00:43:33,039 We can't divide by zero. 1291 00:43:33,040 --> 00:43:34,959 So some of the FSB to throw away and try 1292 00:43:34,960 --> 00:43:35,960 again. 1293 00:43:36,880 --> 00:43:39,309 So our public key is gonna be this H 1294 00:43:40,390 --> 00:43:42,489 and the private key is going to be the 1295 00:43:42,490 --> 00:43:43,490 F. 1296 00:43:46,080 --> 00:43:48,269 H and F for that, 1297 00:43:48,270 --> 00:43:49,859 we can't get G, so G is we don't we don't 1298 00:43:49,860 --> 00:43:52,119 need to remembered some. 1299 00:43:52,120 --> 00:43:54,059 Are we done information we only computed 1300 00:43:54,060 --> 00:43:56,189 once because well take some time. 1301 00:43:56,190 --> 00:43:58,289 It's gonna be called F three because it 1302 00:43:58,290 --> 00:44:00,419 runs around with a reduction or three. 1303 00:44:00,420 --> 00:44:02,579 And it's such that if I take F times 1304 00:44:02,580 --> 00:44:04,290 F three, I'm getting one. 1305 00:44:06,080 --> 00:44:07,639 So there's a polynomial where all the 1306 00:44:07,640 --> 00:44:09,799 coefficients for all the powers 1307 00:44:09,800 --> 00:44:12,039 of X are zero except for the constant 1308 00:44:12,040 --> 00:44:13,040 term. 1309 00:44:14,240 --> 00:44:16,669 Can I come to the full slide 1310 00:44:16,670 --> 00:44:17,670 and the talk? 1311 00:44:19,050 --> 00:44:21,629 So this is explaining how to encrypt 1312 00:44:21,630 --> 00:44:22,630 and how to decrypt, 1313 00:44:23,730 --> 00:44:25,559 except for. Don't do it this way. 1314 00:44:25,560 --> 00:44:27,089 I mean this way. You get all the pending 1315 00:44:27,090 --> 00:44:28,319 attacks and whatever. 1316 00:44:28,320 --> 00:44:30,449 But this is giving the the heart math 1317 00:44:30,450 --> 00:44:31,739 problem. 1318 00:44:31,740 --> 00:44:34,049 So this boils down to something similar 1319 00:44:34,050 --> 00:44:36,419 to ours. Avey say we have to factor 1320 00:44:36,420 --> 00:44:38,249 similarly here because it is still the 1321 00:44:38,250 --> 00:44:39,250 entry problem. 1322 00:44:41,040 --> 00:44:42,809 If you want to use this in practice, you 1323 00:44:42,810 --> 00:44:44,219 have to be a bit careful how you should 1324 00:44:44,220 --> 00:44:46,469 see em. You have to put in some headings. 1325 00:44:46,470 --> 00:44:47,669 You should really. 1326 00:44:47,670 --> 00:44:49,269 Well, don't do that this way. 1327 00:44:49,270 --> 00:44:51,149 So we'll have some more slides of how to 1328 00:44:51,150 --> 00:44:52,150 use it. 1329 00:44:52,800 --> 00:44:54,929 But let's get a wait for your plug 1330 00:44:54,930 --> 00:44:56,260 in a message. 1331 00:44:57,480 --> 00:44:59,179 Do some stuff. Get a ciphertext. 1332 00:44:59,180 --> 00:45:01,510 Do some more stuff and get em back. 1333 00:45:03,080 --> 00:45:04,859 CipherText is gonna be put a simple V 1334 00:45:04,860 --> 00:45:06,869 pick. Another of those polynomials was 1335 00:45:06,870 --> 00:45:08,819 very few non-zero coefficients. 1336 00:45:08,820 --> 00:45:11,309 Again, limited to plus and minus one. 1337 00:45:11,310 --> 00:45:12,809 Let's call this thing. Ah. 1338 00:45:12,810 --> 00:45:15,119 And then the ciphertext simply 1339 00:45:15,120 --> 00:45:17,399 our times this h which was a public 1340 00:45:17,400 --> 00:45:18,400 key. 1341 00:45:18,930 --> 00:45:20,729 Again, this modification which limits 1342 00:45:20,730 --> 00:45:22,239 everything to degree less than N 1343 00:45:24,030 --> 00:45:26,099 and then we add 1344 00:45:26,100 --> 00:45:27,100 O message. 1345 00:45:28,380 --> 00:45:30,089 So we need to somehow get our message 1346 00:45:30,090 --> 00:45:32,249 into a polynomial which has coefficients 1347 00:45:32,250 --> 00:45:35,309 in the set plus minus one and zero. 1348 00:45:35,310 --> 00:45:36,839 But there is no restriction on the 1349 00:45:36,840 --> 00:45:37,799 density. 1350 00:45:37,800 --> 00:45:39,509 This can be totally everything. 1351 00:45:39,510 --> 00:45:40,679 Plus one. It can be everything. 1352 00:45:40,680 --> 00:45:41,699 Minus one. 1353 00:45:41,700 --> 00:45:42,700 No restriction. 1354 00:45:43,610 --> 00:45:45,649 So, for instance, you take your message 1355 00:45:45,650 --> 00:45:46,650 in ternary. 1356 00:45:47,720 --> 00:45:49,249 And then replace powers of three with 1357 00:45:49,250 --> 00:45:50,419 powers of X. 1358 00:45:50,420 --> 00:45:52,519 So getting em in there is no 1359 00:45:52,520 --> 00:45:54,619 big deal. And then encryption was easy. 1360 00:45:56,480 --> 00:45:58,069 Then you have encrypted. 1361 00:45:58,070 --> 00:45:59,329 You send the ciphertext over. 1362 00:46:00,510 --> 00:46:02,809 And now it's a question how we can get 1363 00:46:02,810 --> 00:46:03,810 this MBK. 1364 00:46:04,490 --> 00:46:06,889 So we basically would like to 1365 00:46:06,890 --> 00:46:08,019 divide by H. 1366 00:46:09,260 --> 00:46:10,369 But dividing by H. 1367 00:46:10,370 --> 00:46:12,499 Compiz as loose because just public, 1368 00:46:12,500 --> 00:46:14,119 anybody could do that. 1369 00:46:14,120 --> 00:46:15,439 And there's all this em sitting around. 1370 00:46:15,440 --> 00:46:17,719 So it would be an inexact division. 1371 00:46:19,460 --> 00:46:20,989 So if we wouldn't have any of the 1372 00:46:20,990 --> 00:46:22,909 reductions smalls extra, the N minus one 1373 00:46:22,910 --> 00:46:25,079 would just be divide page and take 1374 00:46:25,080 --> 00:46:27,170 the leftover, take the remainder 1375 00:46:28,310 --> 00:46:29,829 because we have this reduction to the end 1376 00:46:29,830 --> 00:46:31,699 minus extra N minus one. 1377 00:46:31,700 --> 00:46:33,290 This one is not possible. 1378 00:46:34,840 --> 00:46:37,779 Now, here's the way that we decrypt, 1379 00:46:37,780 --> 00:46:38,979 if we have the secret key, 1380 00:46:39,980 --> 00:46:42,109 we take our ciphertext, we multiply by. 1381 00:46:42,110 --> 00:46:44,379 If this was our first 1382 00:46:44,380 --> 00:46:45,380 secret key. 1383 00:46:46,690 --> 00:46:47,949 And remember the relation between the 1384 00:46:47,950 --> 00:46:50,069 public and the secret key that was eight 1385 00:46:50,070 --> 00:46:51,580 times F is 3G. 1386 00:46:54,500 --> 00:46:56,449 Came, I'll put in everything so we are 1387 00:46:56,450 --> 00:46:58,739 brave. We plug in, see the ciphertext 1388 00:46:58,740 --> 00:47:00,739 that was our times H plus M 1389 00:47:02,150 --> 00:47:04,129 and then we move things around. 1390 00:47:04,130 --> 00:47:05,929 I should have said these modifications 1391 00:47:05,930 --> 00:47:08,119 are fully so that you can move things 1392 00:47:08,120 --> 00:47:09,289 around. It's distributive. 1393 00:47:09,290 --> 00:47:11,149 It's commutative. Everything you want. 1394 00:47:11,150 --> 00:47:13,219 OK. So we can move this F next 1395 00:47:13,220 --> 00:47:15,379 to the H and F times H 1396 00:47:15,380 --> 00:47:16,380 gives you three G. 1397 00:47:17,210 --> 00:47:19,219 So then the first term simplifies to our 1398 00:47:19,220 --> 00:47:21,319 times three G and 1399 00:47:21,320 --> 00:47:22,630 then second term. OK, 1400 00:47:23,720 --> 00:47:24,829 now we have F times M. 1401 00:47:24,830 --> 00:47:25,819 We all had M. 1402 00:47:25,820 --> 00:47:27,079 There still is F running around 1403 00:47:29,120 --> 00:47:30,859 but there is now a three, the first in 1404 00:47:30,860 --> 00:47:31,860 the first term. 1405 00:47:32,810 --> 00:47:35,599 So if we can I would use my three. 1406 00:47:35,600 --> 00:47:36,770 We don't have to worry about the. 1407 00:47:37,960 --> 00:47:39,129 Our Times 3G term 1408 00:47:40,300 --> 00:47:41,619 and then we have this EF three running 1409 00:47:41,620 --> 00:47:43,899 around, which, if I multiply 1410 00:47:43,900 --> 00:47:45,070 by it gives me one. 1411 00:47:46,240 --> 00:47:48,339 So if I have the second part F 1412 00:47:48,340 --> 00:47:50,439 times M because I got rid of 1413 00:47:50,440 --> 00:47:51,440 the three by reduction. 1414 00:47:52,880 --> 00:47:55,819 Then I have this times F three. 1415 00:47:55,820 --> 00:47:58,009 Gives me F times F 1416 00:47:58,010 --> 00:48:00,469 three, which is one times M. 1417 00:48:00,470 --> 00:48:01,470 So it gives me M. 1418 00:48:03,420 --> 00:48:04,809 There are few technicalities. 1419 00:48:04,810 --> 00:48:06,819 I've been kind of glancing over that I 1420 00:48:06,820 --> 00:48:08,469 need to reduce more m every once in a 1421 00:48:08,470 --> 00:48:10,589 while also, partially because 1422 00:48:10,590 --> 00:48:12,159 else you would see some growth. 1423 00:48:12,160 --> 00:48:13,959 So that's the important part in the 1424 00:48:13,960 --> 00:48:15,759 encryption function. 1425 00:48:15,760 --> 00:48:17,859 And then down here in the decryption 1426 00:48:17,860 --> 00:48:19,939 function, I need to first would use 1427 00:48:19,940 --> 00:48:21,109 we do smart cubicles. 1428 00:48:21,110 --> 00:48:23,439 Else this relation, this HMS F 1429 00:48:23,440 --> 00:48:24,809 3G only works what. 1430 00:48:26,710 --> 00:48:29,169 And I also have to move my representation 1431 00:48:29,170 --> 00:48:30,339 to something specific. 1432 00:48:30,340 --> 00:48:31,389 Normally if I tell you more. 1433 00:48:31,390 --> 00:48:33,579 Q You would want to have zero till Q 1434 00:48:33,580 --> 00:48:34,580 minus one. 1435 00:48:35,620 --> 00:48:37,569 And I now shift this to be symmetric to 1436 00:48:37,570 --> 00:48:39,879 zero. So now going from minus 1437 00:48:39,880 --> 00:48:41,800 Q over to Tokyo, over to. 1438 00:48:43,720 --> 00:48:44,720 Let's see how this works. 1439 00:48:47,540 --> 00:48:49,789 So this is that moment in 1440 00:48:49,790 --> 00:48:52,249 Waterfall Software Engineering, where 1441 00:48:52,250 --> 00:48:53,509 they've just dropped the one hundred 1442 00:48:53,510 --> 00:48:55,549 pages of documentation on your desk and 1443 00:48:55,550 --> 00:48:57,259 said, implement this. 1444 00:48:57,260 --> 00:48:59,229 This is what the designers have done. 1445 00:48:59,230 --> 00:49:00,289 All right. All right. Let's see if it 1446 00:49:00,290 --> 00:49:01,699 actually works. Let's see if we can get 1447 00:49:01,700 --> 00:49:02,629 the computer doing it. 1448 00:49:02,630 --> 00:49:05,149 So this will be with smaller ends 1449 00:49:05,150 --> 00:49:06,799 and Qs and D then. 1450 00:49:06,800 --> 00:49:08,569 Well, there's a number of coefficients in 1451 00:49:08,570 --> 00:49:09,919 F and so on. 1452 00:49:09,920 --> 00:49:11,539 Smaller parameters than you can use. 1453 00:49:11,540 --> 00:49:13,309 But at least will fit on the slide. 1454 00:49:13,310 --> 00:49:15,499 So there's one of the functions 1455 00:49:15,500 --> 00:49:17,749 you can find online is 1456 00:49:17,750 --> 00:49:18,919 random Deepali. 1457 00:49:18,920 --> 00:49:20,359 This is not a stage function. 1458 00:49:20,360 --> 00:49:21,949 This is something which takes its global 1459 00:49:21,950 --> 00:49:23,689 variable D and gives you and also N and 1460 00:49:23,690 --> 00:49:26,089 gives you a polynomial that has 1461 00:49:26,090 --> 00:49:28,939 well D in this case five 1462 00:49:28,940 --> 00:49:31,189 plus and minus one coefficients out 1463 00:49:31,190 --> 00:49:33,259 of well a maximum of it goes up 1464 00:49:33,260 --> 00:49:34,789 to X to the end minus one. 1465 00:49:34,790 --> 00:49:36,889 So in most X to the six and there's 1466 00:49:36,890 --> 00:49:38,059 some random polynomial. 1467 00:49:38,060 --> 00:49:40,099 And then there's another function that we 1468 00:49:40,100 --> 00:49:42,109 put up called invert mod prime. 1469 00:49:42,110 --> 00:49:44,359 And that is doing this come up with 1470 00:49:44,360 --> 00:49:46,339 three F sub three which. 1471 00:49:46,340 --> 00:49:47,929 Well what is is have three supposed to 1472 00:49:47,930 --> 00:49:48,949 do. Let's check this. 1473 00:49:48,950 --> 00:49:50,719 What it's supposed to do is that if you 1474 00:49:50,720 --> 00:49:52,789 multiply F by EF three, when I 1475 00:49:52,790 --> 00:49:54,139 say multiply, it's always this is 1476 00:49:54,140 --> 00:49:55,369 convolution operation. 1477 00:49:56,510 --> 00:49:58,039 When you multiply F by a three, it's 1478 00:49:58,040 --> 00:49:59,869 supposed to be something that's one mod 1479 00:49:59,870 --> 00:50:00,829 three. 1480 00:50:00,830 --> 00:50:02,899 And if you look at this and 1481 00:50:02,900 --> 00:50:04,879 ignore all the multiples of three, like 1482 00:50:04,880 --> 00:50:06,709 three and minus three, then all you're 1483 00:50:06,710 --> 00:50:08,029 left with is one. 1484 00:50:08,030 --> 00:50:09,259 So think of this as F times. 1485 00:50:09,260 --> 00:50:10,260 F three is one. 1486 00:50:11,360 --> 00:50:12,709 All right. 1487 00:50:12,710 --> 00:50:14,989 There's also some inversion 1488 00:50:14,990 --> 00:50:17,329 mod. Q that was for computing 1489 00:50:17,330 --> 00:50:19,849 h h the public, he was 1490 00:50:19,850 --> 00:50:21,979 well some formula with some GS 1491 00:50:21,980 --> 00:50:24,229 and threes and divide by F at some 1492 00:50:24,230 --> 00:50:24,739 point. 1493 00:50:24,740 --> 00:50:27,229 Well F Q is something that if you 1494 00:50:27,230 --> 00:50:29,629 multiply it by f convolve it with F 1495 00:50:29,630 --> 00:50:31,699 then you get one mod cute. 1496 00:50:31,700 --> 00:50:33,799 Q is 256 in this example. 1497 00:50:33,800 --> 00:50:36,079 And yeah, 257 mod 256 1498 00:50:36,080 --> 00:50:38,449 is one and these multiples of 256 1499 00:50:38,450 --> 00:50:39,919 all go away. 1500 00:50:39,920 --> 00:50:42,169 All right. And then G is another secret. 1501 00:50:42,170 --> 00:50:45,019 And the public key is three times 1502 00:50:45,020 --> 00:50:47,329 the one over F times G 1503 00:50:47,330 --> 00:50:49,429 modulo Q And there's a weird 1504 00:50:49,430 --> 00:50:51,049 thing that happens here which is this 1505 00:50:51,050 --> 00:50:52,339 minus sign. 1506 00:50:52,340 --> 00:50:54,529 Now if you're accustomed to 1507 00:50:54,530 --> 00:50:56,719 mod in C or lower level 1508 00:50:56,720 --> 00:50:59,479 languages, then it'll give you 1509 00:50:59,480 --> 00:51:00,859 negative outputs. 1510 00:51:00,860 --> 00:51:02,779 If you give it a negative input mod 1511 00:51:02,780 --> 00:51:04,579 something, unless it gives you zero, if 1512 00:51:04,580 --> 00:51:05,959 you have a multiple of Q you'll get 1513 00:51:05,960 --> 00:51:06,769 you'll get zero. 1514 00:51:06,770 --> 00:51:08,599 When you say mod Q if you have a negative 1515 00:51:08,600 --> 00:51:10,159 number you'll get something between minus 1516 00:51:10,160 --> 00:51:12,499 one and minus of Q minus one. 1517 00:51:12,500 --> 00:51:13,819 If you have a positive number, you get a 1518 00:51:13,820 --> 00:51:15,649 positive result, which can actually be a 1519 00:51:15,650 --> 00:51:17,449 real problem for crypto leaking. 1520 00:51:17,450 --> 00:51:19,519 Whether that input was was positive 1521 00:51:19,520 --> 00:51:21,499 or negative in the math description of 1522 00:51:21,500 --> 00:51:23,479 entier, there was some footnote in some 1523 00:51:23,480 --> 00:51:25,459 part of the design document going, yeah, 1524 00:51:25,460 --> 00:51:27,769 I make sure you only release a range 1525 00:51:27,770 --> 00:51:30,079 of exactly. Q numbers between zero 1526 00:51:30,080 --> 00:51:31,519 and Q minus one or. 1527 00:51:31,520 --> 00:51:33,139 Well, OK. She said between something like 1528 00:51:33,140 --> 00:51:35,449 minus Q over two and Q over to minus 1529 00:51:35,450 --> 00:51:35,929 one. 1530 00:51:35,930 --> 00:51:38,119 And then if you leak well whether 1531 00:51:38,120 --> 00:51:39,679 the input was positive or negative, 1532 00:51:39,680 --> 00:51:42,169 that's actually maybe a security problem. 1533 00:51:42,170 --> 00:51:44,569 So instead of that, we have a function 1534 00:51:44,570 --> 00:51:46,789 online which is balanced mod, which 1535 00:51:46,790 --> 00:51:48,709 always gives a result, which is well, 1536 00:51:48,710 --> 00:51:50,929 it's like a normal sized character 1537 00:51:50,930 --> 00:51:52,849 assigned by it. It's between minus 128 1538 00:51:52,850 --> 00:51:55,959 and and 127 if Q is 256. 1539 00:51:55,960 --> 00:51:57,259 All right. That's the public key. 1540 00:51:57,260 --> 00:51:59,569 No more leakage of whether the original 1541 00:51:59,570 --> 00:52:02,209 input was positive or negative. 1542 00:52:02,210 --> 00:52:04,489 And to check what this 1543 00:52:04,490 --> 00:52:06,529 F. Q was supposed to do, the whole point 1544 00:52:06,530 --> 00:52:08,779 of H. Is that if you multiply 1545 00:52:08,780 --> 00:52:10,849 H by F, multiply the 1546 00:52:10,850 --> 00:52:12,799 public key by this important part of the 1547 00:52:12,800 --> 00:52:15,109 secret key modulo Q 1548 00:52:15,110 --> 00:52:16,639 then you get the same thing as three 1549 00:52:16,640 --> 00:52:18,559 times the random G. 1550 00:52:18,560 --> 00:52:20,119 That was come up with as another secret. 1551 00:52:21,440 --> 00:52:23,839 All right. Let's see if we can encrypt. 1552 00:52:23,840 --> 00:52:25,639 Here's a message. Just a bunch of random 1553 00:52:25,640 --> 00:52:26,900 ones, zeros minus ones. 1554 00:52:28,100 --> 00:52:30,169 And then another random R 1555 00:52:30,170 --> 00:52:32,239 that was showing up in the encryption and 1556 00:52:32,240 --> 00:52:34,939 then the cipher text C is you take 1557 00:52:34,940 --> 00:52:37,429 H times the public key 1558 00:52:37,430 --> 00:52:39,079 and then add em to it. 1559 00:52:39,080 --> 00:52:41,599 That's this convolution of H in are add M 1560 00:52:41,600 --> 00:52:42,949 and then reduce Mond. 1561 00:52:42,950 --> 00:52:44,929 Q and that gives Sugandh some random 1562 00:52:44,930 --> 00:52:46,369 looking bytes. Seven random looking 1563 00:52:46,370 --> 00:52:47,359 bytes. 1564 00:52:47,360 --> 00:52:49,849 And now decryption was multiply 1565 00:52:49,850 --> 00:52:52,479 the cipher text by the secret F 1566 00:52:52,480 --> 00:52:55,159 reduce mod. Q And then 1567 00:52:55,160 --> 00:52:56,329 Tonya mentioned that. 1568 00:52:56,330 --> 00:52:57,919 Well this is gonna be the same as three 1569 00:52:57,920 --> 00:53:00,319 times G. Times are plus F times M 1570 00:53:00,320 --> 00:53:02,749 and then well multiplying 1571 00:53:02,750 --> 00:53:04,849 that by the F three and 1572 00:53:04,850 --> 00:53:07,129 reducing Mod three finally 1573 00:53:07,130 --> 00:53:09,649 gives exactly the same as the original 1574 00:53:09,650 --> 00:53:10,909 input message. 1575 00:53:10,910 --> 00:53:12,439 So this system actually works. 1576 00:53:12,440 --> 00:53:14,719 It has successfully decrypted a message 1577 00:53:14,720 --> 00:53:16,639 from the ciphertext. 1578 00:53:18,800 --> 00:53:19,889 This shouldn't actually work. 1579 00:53:22,300 --> 00:53:23,559 Didn't somebody tell you that he can't 1580 00:53:23,560 --> 00:53:25,789 just reduce, what, three and what? 1581 00:53:25,790 --> 00:53:28,149 Q I mean, if you take something 1582 00:53:28,150 --> 00:53:30,249 like this expression and you hope 1583 00:53:30,250 --> 00:53:32,019 that there is a three that is running 1584 00:53:32,020 --> 00:53:34,419 around there, let's assume molecule's 1585 00:53:34,420 --> 00:53:35,420 five. 1586 00:53:36,580 --> 00:53:37,689 And we have six. 1587 00:53:37,690 --> 00:53:38,589 Six is beautiful. 1588 00:53:38,590 --> 00:53:40,419 We divisible by by three. 1589 00:53:41,980 --> 00:53:43,509 But then we reduced, what, five? 1590 00:53:43,510 --> 00:53:44,649 And we left with one, which is not a 1591 00:53:44,650 --> 00:53:45,650 multiple of three. 1592 00:53:46,840 --> 00:53:49,149 So in principle, this shouldn't 1593 00:53:49,150 --> 00:53:50,150 work. 1594 00:53:51,020 --> 00:53:53,389 Now, the reason that it still works 1595 00:53:53,390 --> 00:53:54,589 or depending on the product is how you 1596 00:53:54,590 --> 00:53:57,319 choose them works most of the time. 1597 00:53:57,320 --> 00:53:59,379 Is that the parameters it 1598 00:53:59,380 --> 00:54:01,759 shows in such that 1599 00:54:01,760 --> 00:54:02,989 the numbers are small enough? 1600 00:54:04,100 --> 00:54:05,789 So this only works if there's more. 1601 00:54:05,790 --> 00:54:08,089 Q On the right hand side doesn't 1602 00:54:08,090 --> 00:54:10,399 actually take away the three. 1603 00:54:10,400 --> 00:54:12,109 So if there is actually no need to 1604 00:54:12,110 --> 00:54:14,209 compute more. Q So if this thing on 1605 00:54:14,210 --> 00:54:16,849 the right hand side is by itself 1606 00:54:16,850 --> 00:54:17,850 smaller than Q. 1607 00:54:19,740 --> 00:54:21,359 So this is where everything comes in the 1608 00:54:21,360 --> 00:54:23,219 reset at the beginning. Oh, you're only 1609 00:54:23,220 --> 00:54:24,599 allowed to choose a few of the 1610 00:54:24,600 --> 00:54:26,309 coefficients to be non-zero. 1611 00:54:26,310 --> 00:54:28,169 You're only allowed to choose plus and 1612 00:54:28,170 --> 00:54:31,049 minus once because 1613 00:54:31,050 --> 00:54:32,729 this our times 3G. 1614 00:54:33,840 --> 00:54:35,419 Our has only small provisions. 1615 00:54:35,420 --> 00:54:37,219 G.S. only small provisions and OK, then, 1616 00:54:37,220 --> 00:54:39,329 if the three running around, so 1617 00:54:39,330 --> 00:54:41,339 the maximum coefficient we get at every 1618 00:54:41,340 --> 00:54:43,469 moment is if a plus one of 1619 00:54:43,470 --> 00:54:45,959 our hits, A plus one of G 1620 00:54:45,960 --> 00:54:46,960 and the multiply. 1621 00:54:47,820 --> 00:54:49,889 And then we sum this up in 1622 00:54:49,890 --> 00:54:50,890 times. 1623 00:54:51,750 --> 00:54:54,009 But there can't be any such things. 1624 00:54:54,010 --> 00:54:56,099 There's only deep coefficients that are 1625 00:54:56,100 --> 00:54:57,539 non-zero. 1626 00:54:57,540 --> 00:55:00,269 So the worst coefficient of this product 1627 00:55:00,270 --> 00:55:02,789 will be D times 1628 00:55:02,790 --> 00:55:04,979 a perfect match of plus one plus one 1629 00:55:04,980 --> 00:55:06,599 and perfect match of minus one, minus 1630 00:55:06,600 --> 00:55:07,829 one. 1631 00:55:07,830 --> 00:55:10,259 So if they really conspire to always 1632 00:55:10,260 --> 00:55:12,059 add up to the maximum, we can see 1633 00:55:12,060 --> 00:55:14,399 something like 3-D for the first part. 1634 00:55:14,400 --> 00:55:16,469 And then similarly, while there was no 1635 00:55:16,470 --> 00:55:18,779 weight restriction on M, but there was 1636 00:55:18,780 --> 00:55:20,639 a weight restriction on F. 1637 00:55:20,640 --> 00:55:22,709 So when a coefficient of F of which we 1638 00:55:22,710 --> 00:55:24,809 own have D hits 1639 00:55:24,810 --> 00:55:28,019 a non-zero coefficient of M, we get 1640 00:55:28,020 --> 00:55:29,519 a summit. 1641 00:55:29,520 --> 00:55:30,839 So the maximum we can see in any 1642 00:55:30,840 --> 00:55:32,969 coefficient is gonna be four times T. 1643 00:55:35,090 --> 00:55:37,129 Now, our choice will be that we want to 1644 00:55:37,130 --> 00:55:40,159 have that cue over to is larger 1645 00:55:40,160 --> 00:55:41,160 than 40. 1646 00:55:42,520 --> 00:55:44,349 So let's choose our cue large enough. 1647 00:55:45,460 --> 00:55:47,799 Say large part to 1648 00:55:47,800 --> 00:55:49,359 then this reduction will not make any 1649 00:55:49,360 --> 00:55:50,360 problems. 1650 00:55:51,720 --> 00:55:53,849 OK, now what 1651 00:55:53,850 --> 00:55:56,159 does actually have to do with lettuces? 1652 00:55:56,160 --> 00:55:57,629 I promise at the beginning that this is a 1653 00:55:57,630 --> 00:55:59,119 letters based Krypto system and then I 1654 00:55:59,120 --> 00:56:01,619 start talking about polynomials. 1655 00:56:01,620 --> 00:56:03,269 Now, yes, we have seen and not just part 1656 00:56:03,270 --> 00:56:04,559 of the talk that you can take your 1657 00:56:04,560 --> 00:56:07,679 coppersmiths thing and put polynomials 1658 00:56:07,680 --> 00:56:09,989 in as basis vectors. 1659 00:56:09,990 --> 00:56:12,479 But I first have to still explain how 1660 00:56:12,480 --> 00:56:14,309 to translate that into a problem. 1661 00:56:14,310 --> 00:56:15,599 The problem of finding F. 1662 00:56:16,830 --> 00:56:18,599 Into a problem of finding a short vector 1663 00:56:18,600 --> 00:56:19,600 in a lattice. 1664 00:56:21,900 --> 00:56:24,359 So first of all, here's how I set up 1665 00:56:24,360 --> 00:56:25,440 the same matrix. 1666 00:56:26,760 --> 00:56:28,319 So for setting up the Matrix, I'm only 1667 00:56:28,320 --> 00:56:30,689 allowed to use public information. 1668 00:56:30,690 --> 00:56:31,739 I don't know the F. 1669 00:56:31,740 --> 00:56:33,339 I don't know the G, but I do know this. 1670 00:56:33,340 --> 00:56:34,340 H. 1671 00:56:35,310 --> 00:56:37,399 And this matrix, this capital H 1672 00:56:37,400 --> 00:56:39,559 block there, that is going 1673 00:56:39,560 --> 00:56:41,510 to be a block, which is in 1674 00:56:42,830 --> 00:56:44,630 columns and end rows 1675 00:56:46,430 --> 00:56:48,269 and then above it there is a identity 1676 00:56:48,270 --> 00:56:50,689 matrix. So that has Q entries 1677 00:56:50,690 --> 00:56:51,889 that are all equal to one on the 1678 00:56:51,890 --> 00:56:52,909 diagonal. 1679 00:56:52,910 --> 00:56:54,729 Then there's another matrix which has 1680 00:56:54,730 --> 00:56:56,569 those once on the diagonal. 1681 00:56:56,570 --> 00:56:57,890 Everything is zero up here. 1682 00:56:59,120 --> 00:57:00,599 But this H is the interesting part 1683 00:57:02,300 --> 00:57:05,029 H. I've been putting in each row 1684 00:57:05,030 --> 00:57:07,369 all the coefficients of little H. 1685 00:57:07,370 --> 00:57:10,219 Well actually divide by three, but keep 1686 00:57:10,220 --> 00:57:11,959 such that if I take any vector. 1687 00:57:13,830 --> 00:57:15,569 Taken as a polynomial, say this first 1688 00:57:15,570 --> 00:57:17,939 vector there, this one zero zero 1689 00:57:17,940 --> 00:57:19,769 would be the constant one. 1690 00:57:19,770 --> 00:57:20,819 The other one would be the constant 1691 00:57:20,820 --> 00:57:23,279 three, such that it corresponds 1692 00:57:23,280 --> 00:57:25,849 to modification by the polynomial 1693 00:57:25,850 --> 00:57:26,850 H. 1694 00:57:30,420 --> 00:57:32,009 So let's show an example. 1695 00:57:32,010 --> 00:57:33,329 I have this long. 1696 00:57:34,360 --> 00:57:35,379 Links to any rector. 1697 00:57:35,380 --> 00:57:37,659 I have to end by to 1698 00:57:37,660 --> 00:57:40,029 end Matrixx sitting here 1699 00:57:40,030 --> 00:57:42,279 and I now take the first 1700 00:57:42,280 --> 00:57:43,299 part. That's nice. 1701 00:57:43,300 --> 00:57:44,320 It's just a unit vector. 1702 00:57:45,650 --> 00:57:47,899 So that will take from the top part 1703 00:57:47,900 --> 00:57:50,919 of The Matrix, just the Q Times identity, 1704 00:57:50,920 --> 00:57:52,489 so that just gets me a Q They're 1705 00:57:53,590 --> 00:57:55,399 aggressive zeros. 1706 00:57:55,400 --> 00:57:57,469 Then the second part is this 1707 00:57:57,470 --> 00:57:58,879 three zero zero zero. 1708 00:57:58,880 --> 00:58:01,099 And I said it should be such 1709 00:58:01,100 --> 00:58:03,319 that if I multiply by anything, 1710 00:58:03,320 --> 00:58:04,639 it's like multiplication by the 1711 00:58:04,640 --> 00:58:05,719 polynomial. 1712 00:58:05,720 --> 00:58:08,179 So this will grab exactly 1713 00:58:08,180 --> 00:58:10,189 one times this polynomial H. 1714 00:58:10,190 --> 00:58:11,779 So that tells you how you write this 1715 00:58:11,780 --> 00:58:13,339 polynomial h there. 1716 00:58:13,340 --> 00:58:14,689 And then you would have say the next 1717 00:58:14,690 --> 00:58:16,879 coefficient would get this one but 1718 00:58:16,880 --> 00:58:19,129 rotated this one rotated times 1719 00:58:19,130 --> 00:58:20,119 two. 1720 00:58:20,120 --> 00:58:21,770 So this is how you write a matrix. 1721 00:58:24,190 --> 00:58:26,289 And now what is a short vector and this 1722 00:58:26,290 --> 00:58:27,290 let us. 1723 00:58:28,640 --> 00:58:30,259 To get any victor in the lettuce, that 1724 00:58:30,260 --> 00:58:33,019 means to take integer multiples 1725 00:58:33,020 --> 00:58:34,039 of these vectors. 1726 00:58:34,040 --> 00:58:36,169 That means we're taking some polynomial 1727 00:58:36,170 --> 00:58:38,299 combinations or integer polynomial 1728 00:58:38,300 --> 00:58:39,300 combinations of this. 1729 00:58:40,970 --> 00:58:42,769 The reason why I'm getting G times F out 1730 00:58:42,770 --> 00:58:45,499 of G, comma, F out of this is, 1731 00:58:45,500 --> 00:58:47,899 well, I don't know what it looks like, 1732 00:58:47,900 --> 00:58:49,459 but there is a polynomial K. 1733 00:58:50,970 --> 00:58:52,199 And there is a part of my life that I 1734 00:58:52,200 --> 00:58:54,419 knew, such as Kate 1735 00:58:54,420 --> 00:58:56,789 Holmes, f kick him out f times 1736 00:58:56,790 --> 00:58:59,069 his matrix is give me G, come 1737 00:58:59,070 --> 00:59:01,649 F and G and F 1738 00:59:01,650 --> 00:59:03,449 are small. 1739 00:59:03,450 --> 00:59:05,519 That means they have very few non-zero 1740 00:59:05,520 --> 00:59:07,589 entries and the entries are very 1741 00:59:07,590 --> 00:59:09,779 small. They only plus or minus one. 1742 00:59:09,780 --> 00:59:12,119 So if I'm right about this 1743 00:59:12,120 --> 00:59:14,669 and I'll walk through steps in a moment, 1744 00:59:14,670 --> 00:59:16,679 then this vector in the letters is very 1745 00:59:16,680 --> 00:59:19,439 likely to be the shortest vector at all. 1746 00:59:19,440 --> 00:59:21,719 So then I can use l l or something 1747 00:59:21,720 --> 00:59:22,739 to actually get this vector. 1748 00:59:24,360 --> 00:59:26,689 So if you run through this, well, this 1749 00:59:26,690 --> 00:59:28,559 molecule just means there is some certain 1750 00:59:28,560 --> 00:59:30,749 multiple of Q so that H 1751 00:59:30,750 --> 00:59:33,019 times F is three G. 1752 00:59:33,020 --> 00:59:35,519 That's more. Q So there's times 1753 00:59:35,520 --> 00:59:37,679 K times. Q and that's 1754 00:59:37,680 --> 00:59:39,270 the K. I'm stuffing it there 1755 00:59:40,320 --> 00:59:41,320 again. 1756 00:59:41,920 --> 00:59:44,459 Don't trust me, just implement this. 1757 00:59:44,460 --> 00:59:46,149 See how it works. 1758 00:59:46,150 --> 00:59:48,339 Just implement, just implement, 1759 00:59:48,340 --> 00:59:48,819 she says. 1760 00:59:48,820 --> 00:59:51,419 Doesn't she realize how hard this is? 1761 00:59:51,420 --> 00:59:52,839 All right, so we pull out Sage. 1762 00:59:52,840 --> 00:59:55,389 And first thing is just a little 1763 00:59:55,390 --> 00:59:57,609 conversion of H into H divided by 1764 00:59:57,610 --> 00:59:59,799 three mod. Q I think since we're a little 1765 00:59:59,800 --> 01:00:01,929 low on time, I'll skip that part 1766 01:00:01,930 --> 01:00:03,939 and just say what happens when you 1767 01:00:03,940 --> 01:00:05,679 multiply. 1768 01:00:05,680 --> 01:00:07,229 Yeah, a lot of big polynomials. 1769 01:00:07,230 --> 01:00:09,499 What's happening here is that H 1770 01:00:09,500 --> 01:00:11,619 three which has H divided by three, 1771 01:00:11,620 --> 01:00:13,719 that's being multiplied by X and X 1772 01:00:13,720 --> 01:00:15,669 squared next cubed and so on as 1773 01:00:15,670 --> 01:00:17,409 convolution, which means it's rotating 1774 01:00:17,410 --> 01:00:18,369 the coefficients around. 1775 01:00:18,370 --> 01:00:20,109 If you look at each line of numbers, 1776 01:00:20,110 --> 01:00:21,639 fifty eight to ten, fifty four. 1777 01:00:21,640 --> 01:00:23,169 You see that on the next line. 1778 01:00:23,170 --> 01:00:24,309 Rotated round 1779 01:00:25,450 --> 01:00:26,609 one position to the left. 1780 01:00:26,610 --> 01:00:28,569 Fifty eight has gone to the to the end 1781 01:00:28,570 --> 01:00:29,949 and so on. And. 1782 01:00:29,950 --> 01:00:32,799 OK. So here's a bunch of polynomials. 1783 01:00:32,800 --> 01:00:35,499 And what matters about these polynomials 1784 01:00:35,500 --> 01:00:37,689 is that some 1785 01:00:37,690 --> 01:00:39,759 combination of these if you add up some 1786 01:00:39,760 --> 01:00:41,289 of these and subtract some of these, 1787 01:00:41,290 --> 01:00:43,689 you're gonna get G modulo 1788 01:00:43,690 --> 01:00:45,939 Q because remember, F is 1789 01:00:45,940 --> 01:00:48,429 a bunch of one 1790 01:00:48,430 --> 01:00:50,169 X, X squared and so on, added and 1791 01:00:50,170 --> 01:00:51,759 subtracted in some way. 1792 01:00:51,760 --> 01:00:53,589 And if you multiply that by H, you get 1793 01:00:53,590 --> 01:00:55,839 three G and this H three is while 1794 01:00:55,840 --> 01:00:57,969 you multiply by H over three. 1795 01:00:57,970 --> 01:00:59,229 That's gonna give you G. 1796 01:00:59,230 --> 01:01:01,479 So G is gonna be add and subtract 1797 01:01:01,480 --> 01:01:04,209 whichever of these polynomials you get 1798 01:01:04,210 --> 01:01:06,579 for corresponding to you 1799 01:01:06,580 --> 01:01:07,899 wrote F in the first place. 1800 01:01:07,900 --> 01:01:10,129 The secret F was some indifference 1801 01:01:10,130 --> 01:01:11,530 and some of these X squared. 1802 01:01:12,640 --> 01:01:14,709 All right. I'm going to just show you 1803 01:01:14,710 --> 01:01:16,779 the matrix that comes up at 1804 01:01:16,780 --> 01:01:18,999 the end of this. Here's this 1805 01:01:19,000 --> 01:01:20,919 to end by two and matrix, where on the 1806 01:01:20,920 --> 01:01:22,779 bottom left are the same numbers that we 1807 01:01:22,780 --> 01:01:25,159 were just looking at with some 58 1808 01:01:25,160 --> 01:01:26,259 suns on. 1809 01:01:26,260 --> 01:01:28,479 And then down 1810 01:01:28,480 --> 01:01:30,790 the diagonal, there's some cues and ones. 1811 01:01:31,870 --> 01:01:34,339 All right. And then we pull out the 1812 01:01:34,340 --> 01:01:35,949 nordia to give us our 1813 01:01:37,300 --> 01:01:38,919 short vectors in the lattice and. 1814 01:01:38,920 --> 01:01:39,849 OK. There's l. 1815 01:01:39,850 --> 01:01:41,979 L results and suddenly there's much 1816 01:01:41,980 --> 01:01:43,029 shorter results. 1817 01:01:43,030 --> 01:01:45,159 These are all l ls giving you not 1818 01:01:45,160 --> 01:01:47,319 just one short vector, but a bunch 1819 01:01:47,320 --> 01:01:49,299 of short vectors, a short kind of short 1820 01:01:49,300 --> 01:01:51,809 basis. And this KCC super short 1821 01:01:51,810 --> 01:01:52,799 vectors up at the top. 1822 01:01:52,800 --> 01:01:55,179 The first row is a very short combination 1823 01:01:55,180 --> 01:01:58,149 of the original vectors. 1824 01:01:58,150 --> 01:02:00,999 All right. If you extract the second half 1825 01:02:01,000 --> 01:02:03,159 m dot l l bracket zeros taking 1826 01:02:03,160 --> 01:02:04,779 the first row and then the bracket and 1827 01:02:04,780 --> 01:02:06,959 colon is taking from positions and two 1828 01:02:06,960 --> 01:02:09,039 to end through two and minus one of 1829 01:02:09,040 --> 01:02:10,119 that first row. 1830 01:02:10,120 --> 01:02:12,219 And that gives you five non-zero 1831 01:02:12,220 --> 01:02:14,289 coefficients, two more zero 1832 01:02:14,290 --> 01:02:15,309 coefficients. 1833 01:02:15,310 --> 01:02:18,309 Converting those into a polynomial 1834 01:02:18,310 --> 01:02:20,389 is exactly the secret 1835 01:02:20,390 --> 01:02:21,909 F well with a minus sign. 1836 01:02:21,910 --> 01:02:23,799 But that doesn't affect the decryption. 1837 01:02:23,800 --> 01:02:25,689 So if you run for this f that the 1838 01:02:25,690 --> 01:02:27,729 attacker found just from the public key, 1839 01:02:27,730 --> 01:02:30,039 setting up a matrix running l l l 1840 01:02:30,040 --> 01:02:32,109 on this polynomial lattice. 1841 01:02:32,110 --> 01:02:33,459 Then you break enter. 1842 01:02:33,460 --> 01:02:34,900 You can decrypt any message you want. 1843 01:02:36,310 --> 01:02:38,409 Now you have to scale this up to 1844 01:02:38,410 --> 01:02:39,549 get real security. 1845 01:02:39,550 --> 01:02:41,289 Of course, seven dimensions is not 1846 01:02:41,290 --> 01:02:42,399 enough. 1847 01:02:42,400 --> 01:02:44,739 If you go up to, say, 150 dimensions 1848 01:02:44,740 --> 01:02:46,899 and hundred one non zero 1849 01:02:46,900 --> 01:02:49,059 terms in F and so on and Q 1850 01:02:49,060 --> 01:02:51,129 scale that up to a two to the thirty two, 1851 01:02:51,130 --> 01:02:52,729 then there's gonna be more than two to 1852 01:02:52,730 --> 01:02:55,179 the 200 choices of the secret f 1853 01:02:55,180 --> 01:02:57,549 you try the attack again and 1854 01:02:57,550 --> 01:02:59,649 the attack does not find plus and 1855 01:02:59,650 --> 01:03:00,789 minus ones. 1856 01:03:00,790 --> 01:03:02,769 It still finds a kind of short 1857 01:03:02,770 --> 01:03:04,149 polynomial. 1858 01:03:04,150 --> 01:03:06,189 It's not necessarily the shortest, but 1859 01:03:06,190 --> 01:03:08,469 it's sorta short and it still breaks 1860 01:03:08,470 --> 01:03:11,559 the system, which is kind of scary. 1861 01:03:11,560 --> 01:03:13,089 What you need to do, the reason this 1862 01:03:13,090 --> 01:03:14,859 still breaks the system is that Q is 1863 01:03:14,860 --> 01:03:16,959 actually too big. 1864 01:03:16,960 --> 01:03:18,789 You don't always have crypto parameters 1865 01:03:18,790 --> 01:03:20,709 being more secure if they're bigger when 1866 01:03:20,710 --> 01:03:22,779 Q is really big, that allows 1867 01:03:22,780 --> 01:03:25,149 this kind of big F to decrypt 1868 01:03:25,150 --> 01:03:26,979 because the whole decryption procedure 1869 01:03:26,980 --> 01:03:29,379 needed that there wasn't some wrap around 1870 01:03:29,380 --> 01:03:31,629 modulo. Q If Q is smaller, 1871 01:03:31,630 --> 01:03:33,219 it actually gets more secure and then 1872 01:03:33,220 --> 01:03:35,259 this F does not break the system anymore 1873 01:03:35,260 --> 01:03:37,479 and then well for good security also need 1874 01:03:37,480 --> 01:03:38,980 end to be somewhat bigger. 1875 01:03:40,050 --> 01:03:40,499 All right. 1876 01:03:40,500 --> 01:03:42,419 So what do you do this? 1877 01:03:42,420 --> 01:03:43,709 There's a whole bunch of text to take 1878 01:03:43,710 --> 01:03:45,739 into account. Choose smaller and smooth 1879 01:03:45,740 --> 01:03:47,849 shoes. Logic, 1880 01:03:47,850 --> 01:03:49,449 shoes, smaller, cute shoes larger. 1881 01:03:49,450 --> 01:03:51,329 And they are all the corporate tax I 1882 01:03:51,330 --> 01:03:52,679 mentioned at the beginning. 1883 01:03:52,680 --> 01:03:55,020 But to close on a positive note, 1884 01:03:56,330 --> 01:03:58,439 if you take this and 1885 01:03:58,440 --> 01:03:59,609 try this at home. 1886 01:03:59,610 --> 01:04:01,379 Am I on. Okay. If you want to try this at 1887 01:04:01,380 --> 01:04:03,839 home. Everything that we talked about. 1888 01:04:03,840 --> 01:04:05,729 So there are plenty of things that you 1889 01:04:05,730 --> 01:04:06,869 can do. 1890 01:04:06,870 --> 01:04:08,309 You probably don't want to use lattices 1891 01:04:08,310 --> 01:04:09,929 yourself right now. 1892 01:04:09,930 --> 01:04:11,999 So every Naess submission to the 1893 01:04:12,000 --> 01:04:13,979 post Quantum Crypto Competition has a 1894 01:04:13,980 --> 01:04:15,269 reference implementation which is 1895 01:04:15,270 --> 01:04:16,619 available online. 1896 01:04:16,620 --> 01:04:18,059 More than 90 percent of them have 1897 01:04:18,060 --> 01:04:19,589 survived to survived a week of 1898 01:04:19,590 --> 01:04:20,969 cryptanalysis. 1899 01:04:20,970 --> 01:04:23,309 So you two can go 1900 01:04:23,310 --> 01:04:25,379 and analyze these implementations, 1901 01:04:25,380 --> 01:04:27,179 break them, prove their security, 1902 01:04:27,180 --> 01:04:29,129 whatever you like. So this is what the 1903 01:04:29,130 --> 01:04:30,329 world needs. 1904 01:04:30,330 --> 01:04:32,459 If you're interested in integration of 1905 01:04:32,460 --> 01:04:34,739 quantum safe computing or quantum 1906 01:04:34,740 --> 01:04:37,709 safe crypto into actual protocols, 1907 01:04:37,710 --> 01:04:39,659 there is a project called the Open 1908 01:04:39,660 --> 01:04:41,759 Quantum Safe Project, which 1909 01:04:41,760 --> 01:04:44,189 has a bunch of implementations of schemes 1910 01:04:44,190 --> 01:04:46,259 and integrations into things like open 1911 01:04:46,260 --> 01:04:47,260 SSL. 1912 01:04:47,790 --> 01:04:49,229 You may not want to use this right now 1913 01:04:49,230 --> 01:04:50,909 because schemes may become obsolete due 1914 01:04:50,910 --> 01:04:52,529 to crypto analytic advances like the ones 1915 01:04:52,530 --> 01:04:53,999 we've seen. 1916 01:04:54,000 --> 01:04:55,919 There's a lot of work at every level to 1917 01:04:55,920 --> 01:04:58,169 break stuff, analyze proposals, 1918 01:04:58,170 --> 01:04:59,999 look at implementations, all sorts of 1919 01:05:00,000 --> 01:05:02,219 things needed. And if you really 1920 01:05:02,220 --> 01:05:04,109 feel inspired to turn on post quantum 1921 01:05:04,110 --> 01:05:06,419 cryptography and your own projects, 1922 01:05:06,420 --> 01:05:07,949 we would recommend using a hybrid 1923 01:05:07,950 --> 01:05:09,749 approach with elliptic curve cryptography 1924 01:05:09,750 --> 01:05:11,879 and not using bare 1925 01:05:11,880 --> 01:05:13,979 quantum post quantum schemes right 1926 01:05:13,980 --> 01:05:16,589 now. So Google did this, for example, 1927 01:05:16,590 --> 01:05:18,270 this past year with 1928 01:05:19,290 --> 01:05:21,509 a post quantum key exchange and 1929 01:05:21,510 --> 01:05:22,919 it did a hybrid approach with elliptic 1930 01:05:22,920 --> 01:05:25,109 curves. So that is all we have. 1931 01:05:25,110 --> 01:05:26,579 So thank you very much. 1932 01:05:26,580 --> 01:05:28,799 And we hope to see more broken 1933 01:05:28,800 --> 01:05:29,800 schemes.