1 00:00:00,000 --> 00:00:25,280 *36C3 preroll music* *Applause* 2 00:00:25,280 --> 00:00:30,369 naehrwert: Yeah. Thank you for the audience and thanks that you came. Thanks 3 00:00:30,369 --> 00:00:34,530 for the Congress for giving me the opportunity to be here tonight, to be able 4 00:00:34,530 --> 00:00:39,880 to tell you a bit about post quantum cryptography, a bit about as isogenies. I 5 00:00:39,880 --> 00:00:44,390 mean, just educate the people a bit about what that means, even, because I'm not too 6 00:00:44,390 --> 00:00:52,500 sure how many of you heard about that before. Yeah, let's just jump right in. So 7 00:00:52,500 --> 00:00:57,410 my day job is being a mathematics PhD student at an undisclosed university. You 8 00:00:57,410 --> 00:01:03,320 can ask me in private if you're interested. So previously I did physics. I 9 00:01:03,320 --> 00:01:07,450 was also or maybe I'm still a bit active in the console hacking scene. And if 10 00:01:07,450 --> 00:01:12,320 you're interested about that shameless plug, you can find us at Nintenbros 11 00:01:12,320 --> 00:01:17,220 Assembly later. You can ask us all about our somehow console hacking endeavors. But 12 00:01:17,220 --> 00:01:24,220 enough about that. So I brought you some pictures, screenshots of websites. So I 13 00:01:24,220 --> 00:01:28,670 don't know if you have seen the chatter on social media and the blogs here recently 14 00:01:28,670 --> 00:01:36,210 about that Google paper on quantum supremacy. So there is a Nature article 15 00:01:36,210 --> 00:01:42,280 about that beyond quantum supremacy. And there is a Verge article that Google 16 00:01:42,280 --> 00:01:47,701 confirms quantum supremacy and breakthrough, whatever that means. There 17 00:01:47,701 --> 00:01:52,020 is Google's own blog post about it. Notice there are always these shiny pictures of 18 00:01:52,020 --> 00:01:57,909 these huge tubs filled with helium where they house these quantum computers. So 19 00:01:57,909 --> 00:02:04,079 supremacy means the state or condition of being superior to all others in authority, 20 00:02:04,079 --> 00:02:11,129 power, or status. So calling something quantum supremacy, I mean, that screams 21 00:02:11,129 --> 00:02:16,420 something being pretty amazing. But what actually does this mean for us? What does 22 00:02:16,420 --> 00:02:22,980 it mean for cryptography? And I think I can relieve you all about from from maybe 23 00:02:22,980 --> 00:02:29,290 some fears that you had for us in practice. Maybe today it doesn't really 24 00:02:29,290 --> 00:02:36,230 mean anything yet. So for cryptography none of our underlying assumptions, 25 00:02:36,230 --> 00:02:40,601 whatever it means for now, are being actively broken yet as we know or that we 26 00:02:40,601 --> 00:02:46,910 know of. But in theory, they are broken. Okay. And because they're only broken in 27 00:02:46,910 --> 00:02:50,349 theory, that's pretty good. So we can still blame the designers and implementers 28 00:02:50,349 --> 00:02:57,080 of whatever we cook up for when things go wrong. So that's nice, too. But as I 29 00:02:57,080 --> 00:03:01,970 already wrote in the abstract a bit for this talk, we should be, somehow, better 30 00:03:01,970 --> 00:03:06,980 be safe than sorry. So instead of somehow waiting until the point of where quantum 31 00:03:06,980 --> 00:03:11,060 computers somehow become feasible to break our cryptography, we should probably 32 00:03:11,060 --> 00:03:16,069 research it today. It's a bit with the climate change, right? Suppose it's right 33 00:03:16,069 --> 00:03:19,500 to save our climate today instead of waiting until it's too late. So if we're 34 00:03:19,500 --> 00:03:24,900 going to be reborn to do the same for cryptography. There are also three 35 00:03:24,900 --> 00:03:30,920 upcoming talks I want to advertise here a bit. I think I don't remember the days, 36 00:03:30,920 --> 00:03:34,519 but descriptions look pretty interesting. So I'm going to leave that up for a few 37 00:03:34,519 --> 00:03:38,870 seconds. There is one called Provable Insecurity, one called Cryptography 38 00:03:38,870 --> 00:03:42,819 Demystified and one about high assurance cryptography software. I'm sure this is 39 00:03:42,819 --> 00:03:48,590 gonna be interesting. Okay, let's return back to what I want to talk about. So 40 00:03:48,590 --> 00:03:53,810 there's something I chucklingly call the Post-Quantum Cryptography Zoo. There are a 41 00:03:53,810 --> 00:03:57,780 few buzzwords up there. You don't really have to know what they mean. I'm just 42 00:03:57,780 --> 00:04:01,600 going to say them out loud. Lattices, codes, multivariate polynomial systems. 43 00:04:01,600 --> 00:04:07,310 That's also a bit of a mouthful. And hash based cryptography. And there is the one 44 00:04:07,310 --> 00:04:11,760 that I want to briefly talk about tonight called supersingular elliptic curve 45 00:04:11,760 --> 00:04:16,199 isogenies. OK, so this is the stuff that I really like. Isogenies, they are great. 46 00:04:16,199 --> 00:04:21,970 And now I'm going to tell you why they're so great. All right. So I don't know how 47 00:04:21,970 --> 00:04:26,369 many of you have a mathematics background. Maybe I can do a test. Can people raise 48 00:04:26,369 --> 00:04:32,879 their hands where if they have some formal training in, say, algebra? Yeah. Okay. So 49 00:04:32,879 --> 00:04:37,759 that's pretty good. So I'm just gonna tell you some something about it. There are 50 00:04:37,759 --> 00:04:42,580 decimal numbers. This is Pi. Then there are rational numbers somehow the are, one 51 00:04:42,580 --> 00:04:46,339 half, one third and so on and so forth. Then there are integers from minus 52 00:04:46,339 --> 00:04:52,889 infinity to plus infinity and they follow nice whole steps. But for working with 53 00:04:52,889 --> 00:04:56,619 those numbers and for cryptography, we want something that's nicer behaved. We 54 00:04:56,619 --> 00:05:01,499 want somehow a finite set. OK. So this is just important for implementation. And the 55 00:05:01,499 --> 00:05:05,350 ones that we want to work with, I'm just going to remind you, are the integers 56 00:05:05,350 --> 00:05:11,620 modulo N, so we take some positive integer N, big N, and then we consider the set 57 00:05:11,620 --> 00:05:16,599 from zero to N minus one. Okay. And these numbers do follow certain addition and 58 00:05:16,599 --> 00:05:20,249 multiplication rules and it pretty much works like a clock face. OK. I chose N is 59 00:05:20,249 --> 00:05:24,569 12 here and, just bear with me, imagine my clock face goes from zero to eleven 60 00:05:24,569 --> 00:05:28,930 instead of from one to twelve. But it's really the same. For example, if I tried 61 00:05:28,930 --> 00:05:35,240 to add ten to five. OK, I start from ten. I go two steps and then I arrive at zero. 62 00:05:35,240 --> 00:05:38,789 This is where my clock ticks over. Right. Like on a real clock. And then you go 63 00:05:38,789 --> 00:05:44,129 three more steps. And so ten plus five mod twelve is three. So it's numbers that kind 64 00:05:44,129 --> 00:05:49,550 of behave this way. Think of addition on on a clock face. And for the computer 65 00:05:49,550 --> 00:05:54,530 scientists out there or, I mean, everyone probably knows about that, for a computer 66 00:05:54,530 --> 00:05:58,930 they're like the 8 bit integers where N is 2 to the 8. And then these are the numbers 67 00:05:58,930 --> 00:06:03,669 from 0 to 255, and so on and so forth. So these are the numbers that we want to work 68 00:06:03,669 --> 00:06:12,719 with. Just to set the stage a bit. And these isogenies. We will live in a world 69 00:06:12,719 --> 00:06:18,020 where we we work with somehow related numbers to these integers mod N. And now 70 00:06:18,020 --> 00:06:25,249 for big N, we choose a prime P and then these integers mod P, they represent what 71 00:06:25,249 --> 00:06:30,689 we call the finite field with P elements. Okay. And you can think of this as a set 72 00:06:30,689 --> 00:06:35,929 that has exactly P elements and really kind of behaves like the real numbers. 73 00:06:35,929 --> 00:06:39,020 Okay. You can add numbers, you can subtract numbers. You can divide by 74 00:06:39,020 --> 00:06:42,919 everything but zero. Okay. And this finite field with P elements works really the 75 00:06:42,919 --> 00:06:46,839 same. It's just a finite set, but everything is invertable except zero. 76 00:06:46,839 --> 00:06:50,199 Okay. And these are the numbers that we want to work with and computers can do 77 00:06:50,199 --> 00:06:56,509 that. So that's fine. And just for the sake of telling you, there are also fields 78 00:06:56,509 --> 00:07:02,999 that have somehow P to the R elements, but they are not the same as what people are. 79 00:07:02,999 --> 00:07:06,479 Okay. But there is a way to construct it. But that's all you need to know about. So 80 00:07:06,479 --> 00:07:09,930 this is really the set of numbers that we're going to work over and that that's 81 00:07:09,930 --> 00:07:15,580 all you need to know. Okay. So the cryptographic problem that I want to focus 82 00:07:15,580 --> 00:07:20,149 on this talk is simple key exchange. I'm not gonna talk about signatures, I'm not 83 00:07:20,149 --> 00:07:23,639 going to talk about encryption, nothing. Let's just focus on this one simple 84 00:07:23,639 --> 00:07:29,529 problem of how do Alice and Bob exchange a key without anyone else somehow getting 85 00:07:29,529 --> 00:07:33,319 access to that key? And I mean, there are somehow classical solutions to that. I 86 00:07:33,319 --> 00:07:37,050 could put my key in a suitcase and I could bring it to Alice or I could somehow pay 87 00:07:37,050 --> 00:07:41,380 someone to bring the suitcase to Alice. Or maybe people heard about the thing where I 88 00:07:41,380 --> 00:07:44,830 put my lock on the box and I ship it to Alice and she puts her lock on the box and 89 00:07:44,830 --> 00:07:49,009 she ships ships it back now I remove my lock and I ship it to Alice again. OK, so 90 00:07:49,009 --> 00:07:53,610 there are countless ways, but we want to somehow do this in a nice, instantaneous 91 00:07:53,610 --> 00:07:59,979 kind of way using mathematics. Okay. So this simple problem is what we're going to 92 00:07:59,979 --> 00:08:05,949 focus on. And classically (whatever that means for now) this has been set off by 93 00:08:05,949 --> 00:08:09,780 Diffie-Hellman. And this is this nice paper from 1979 the title is New 94 00:08:09,780 --> 00:08:13,849 Directions in Cryptography. So this already tells you that something important 95 00:08:13,849 --> 00:08:20,259 must be going on and what you somehow invented there was a way to exchange keys 96 00:08:20,259 --> 00:08:27,179 between two parties using a nice, well- defined problem. Okay. And how does it 97 00:08:27,179 --> 00:08:31,539 work? Okay. I'm just gonna tell you how it works. So there are two parties, Alice and 98 00:08:31,539 --> 00:08:39,250 Bob. A and B. They agree on a safe prime modulus, N. Okay. So this is the integers 99 00:08:39,250 --> 00:08:45,029 mod N, which I saw, and a generator G. So what does that mean? Basically in my set, 100 00:08:45,029 --> 00:08:50,160 from zero to N, I want to single out one element such that every element can be 101 00:08:50,160 --> 00:08:54,569 written as a power of that element. And somehow this means it generates it. Right. 102 00:08:54,569 --> 00:09:00,110 So every Y can be written as G to the X mod N. Okay, this is my setup. And then 103 00:09:00,110 --> 00:09:06,250 there is Alice and Bob and they agree on these two parameters. Okay. And now how do 104 00:09:06,250 --> 00:09:12,199 we do the key exchange? So it's very symmetrical. So Alice chooses a random A 105 00:09:12,199 --> 00:09:17,199 in the set from one to N minus one. And she sends big A is G to the small a mod N 106 00:09:17,199 --> 00:09:21,589 to Bob. And as you might have guessed it, because I said it's symmetrical, Bob does 107 00:09:21,589 --> 00:09:26,819 the same. Okay. So how does the picture go? So Alice on the left, she chooses a 108 00:09:26,819 --> 00:09:33,290 random small A. And she sends that big A to Bob. Bob chooses a random small B. He 109 00:09:33,290 --> 00:09:38,120 sends the big B to Alice. And then somehow, you know, you have to combine 110 00:09:38,120 --> 00:09:45,080 them somehow. Right. How do you do this? So this is nice to compute the shared k, 111 00:09:45,080 --> 00:09:50,550 the shared key. So Alice takes the B, she got from Bob and raises it to the power of 112 00:09:50,550 --> 00:09:56,379 her own random secret value. And Bob does the same. And magically from mathematics, 113 00:09:56,379 --> 00:10:04,269 they both get the same small k. And now I'm going to tell you why, somehow, this 114 00:10:04,269 --> 00:10:11,750 is hard for anyone else to get the same small k. So now bear with me. I'm gonna 115 00:10:11,750 --> 00:10:16,120 write it down mathematically, first of all, why not teach you a bit about that as 116 00:10:16,120 --> 00:10:21,290 well? So this is this diagram, this commutative diagram that somehow 117 00:10:21,290 --> 00:10:24,931 represents this key exchange that just happened. Okay. So Bob and Alice, they 118 00:10:24,931 --> 00:10:30,779 both started in the left upper corner with the G and they both end up in the lower 119 00:10:30,779 --> 00:10:35,269 right corner, the G the AB. So they both are able to somehow compute G to the AB 120 00:10:35,269 --> 00:10:39,089 and no one else is. And how does that work? Well, Alice will only compute the 121 00:10:39,089 --> 00:10:43,990 horizontal arrows, so she only raises to the power of small A because that's her 122 00:10:43,990 --> 00:10:48,540 random secret that only she knows. And Bob only computes the vertical arrows, so he 123 00:10:48,540 --> 00:10:51,800 only raises to the power of small B, because that's the secret to he knows and 124 00:10:51,800 --> 00:10:57,490 no one else does. And I mean by the commutativity and the associativity of 125 00:10:57,490 --> 00:11:02,819 exponentiation, they just agree on the same G to the AB which is which is cool. 126 00:11:02,819 --> 00:11:08,519 And somewhere in there there hides a problem that we like to call the discrete 127 00:11:08,519 --> 00:11:13,549 logarithm problem and it just happens for integers mod N if I choose my N 128 00:11:13,549 --> 00:11:17,410 appropriately, I'm not gonna tell you how, but just believe me if I choose it 129 00:11:17,410 --> 00:11:25,670 appropriately. If I give you Y and G, for you it's hard to find the small X. Somehow 130 00:11:25,670 --> 00:11:30,040 like taking a logarithm, and we call it the discrete logarithm because it's a 131 00:11:30,040 --> 00:11:33,720 discrete set of numbers instead of the continuous decimal numbers, what we 132 00:11:33,720 --> 00:11:37,720 started with was this discrete finite set of numbers and this DLP is hard. Okay. 133 00:11:37,720 --> 00:11:44,780 This is a hard problem for classical computers. And the best classical generic 134 00:11:44,780 --> 00:11:49,720 algorithm - I'm not gonna talk about somehow algorithms that specifically 135 00:11:49,720 --> 00:11:54,889 target integers mod N, I'm just going to talk about generic algorithms for for this 136 00:11:54,889 --> 00:11:59,600 DLP problem. The best algorithm somehow has run time square root of big N the 137 00:11:59,600 --> 00:12:06,709 number of elements and say I chose my N about the size of 2 to the small n, or n 138 00:12:06,709 --> 00:12:13,230 bits. Then solving this takes exponential time in n, right, because the square root 139 00:12:13,230 --> 00:12:17,769 of 2 to the n is still pretty big. Okay, this is about 2 to the n half, and if I 140 00:12:17,769 --> 00:12:24,980 make n a thousand is still 512 bits. So this is a hard problem. But recently there 141 00:12:24,980 --> 00:12:33,540 has been a record for factoring and DLPing over a seven hundred ninety five bit 142 00:12:33,540 --> 00:12:39,040 modulus and they use a bit of a better algorithm, but still, I mean it still took 143 00:12:39,040 --> 00:12:46,019 them a long time. Okay, so if I remember correctly, this feed took them 4000 core 144 00:12:46,019 --> 00:12:51,120 years on a two point one gigahertz computer. I mean, that's still 4000 core 145 00:12:51,120 --> 00:12:55,089 years. So this is a long time. Okay. But as you can see, it's possible to solve 146 00:12:55,089 --> 00:13:00,410 this. I mean, just put enough, if I have a big enough hammer, I can solve this. Okay. 147 00:13:00,410 --> 00:13:05,399 But again, you can make N pretty big, bigger than anything being able to solve 148 00:13:05,399 --> 00:13:10,629 this anymore. But. Okay, so there is a quantum algorithm for this and this is 149 00:13:10,629 --> 00:13:16,279 this other paper from 95. Peter Shor. So he thought of this algorithm that solves 150 00:13:16,279 --> 00:13:21,930 the DLP in polynomial time. Okay, now remember our big N we took about two to 151 00:13:21,930 --> 00:13:26,770 the small n. And this Shor's algorithm only takes small n to the cube? And I 152 00:13:26,770 --> 00:13:32,730 mean, if N is a hundred hundred cube, it's not that big. And I can make a thousand by 153 00:13:32,730 --> 00:13:37,749 a thousand cube is still not that big. Okay. So there is a good algorithm that 154 00:13:37,749 --> 00:13:41,519 assumes the existence of a quantum computer. I mean as outlandish that might 155 00:13:41,519 --> 00:13:47,600 sound, but still this algorithm in theory breaks the DLP. Okay. So I don't know, 156 00:13:47,600 --> 00:13:52,319 maybe in 20 years or 30 years, 100 years. I don't know personally, but if there is a 157 00:13:52,319 --> 00:13:56,910 quantum computer eventually that somehow runs this thing, okay, DLP's broken, 158 00:13:56,910 --> 00:14:05,350 classically. So. Well, what to do? As I said, let's just try to come up with 159 00:14:05,350 --> 00:14:10,899 cryptography for which we don't know a quantum algorithm. Okay. Or for which we 160 00:14:10,899 --> 00:14:15,170 expect there won't be a quantum algorithm ever. There are a few candidates. Again, 161 00:14:15,170 --> 00:14:21,930 there's this zoo. Lattices, codes, this long word, and isogenies. Okay. Now what I 162 00:14:21,930 --> 00:14:26,319 want to tell you about is what is an isogeny, and how do I do key exchange with 163 00:14:26,319 --> 00:14:33,970 an isogeny? Okay. Because I know, it's a fancy word, but what does it mean? Okay. 164 00:14:33,970 --> 00:14:37,300 There was this other word that started with elliptic curve isogenies, so probably 165 00:14:37,300 --> 00:14:40,860 I should tell you about what is an elliptic curve or give you a reminder if 166 00:14:40,860 --> 00:14:46,379 you've seen this before. So I look at this equation in two variables and two 167 00:14:46,379 --> 00:14:51,529 constants, the variables X and Y, my constants are A and B. And the equation is 168 00:14:51,529 --> 00:14:58,160 Y squared is X cubed plus AX plus B. And now what I want to look at is all the 169 00:14:58,160 --> 00:15:02,920 solutions to this equation, all the possible pairs Y and X or X and Y. And of 170 00:15:02,920 --> 00:15:06,990 course, they're going to look different somehow for the different possible numbers 171 00:15:06,990 --> 00:15:11,370 that I can plug in for X and Y. And again, you might have guessed it, first of all, 172 00:15:11,370 --> 00:15:14,760 we're going to look at it over the decimal numbers and then later we want to consider 173 00:15:14,760 --> 00:15:20,730 this again over our finite field, okay, because we like we like this discreteness. 174 00:15:20,730 --> 00:15:25,649 And over R, a simple equation, I just chose some values for A and B, B I set to 175 00:15:25,649 --> 00:15:30,790 zero, A I set to 1, uh, A I set to zero, B I set to one. The solution set looks like 176 00:15:30,790 --> 00:15:36,519 this. And actually it extends infinitely far on the right side, up and down. Okay. 177 00:15:36,519 --> 00:15:41,470 So this is just somehow a snapshot of what the solution set looks like. But over my 178 00:15:41,470 --> 00:15:45,540 finite field, and I chose one with one hundred and one elements, it looks like 179 00:15:45,540 --> 00:15:50,850 the set of points. Okay. So elliptical curves look differently over different 180 00:15:50,850 --> 00:15:57,510 fields. But that's fine. That's fine. Okay. Now, quick reminder of why people 181 00:15:57,510 --> 00:16:01,550 like elliptic curves. So there is something called the point addition law. 182 00:16:01,550 --> 00:16:05,490 So I can take two points on this curve and I can somehow add them. Okay, but this is 183 00:16:05,490 --> 00:16:10,350 not really addition in the sense of numbers. There is somehow a law that I have 184 00:16:10,350 --> 00:16:16,499 to apply. And let me quickly show off how this is done. So how do I add two points 185 00:16:16,499 --> 00:16:21,220 on this curve? Well, you take these two points, you put a line through it, and 186 00:16:21,220 --> 00:16:27,430 then there is a law that says that if I put a line through two points, then it 187 00:16:27,430 --> 00:16:32,060 has, the line has to cut the curve from the third point. Okay. So I put the line 188 00:16:32,060 --> 00:16:36,779 through these two points. It cut the curve in the third point all the way up on the 189 00:16:36,779 --> 00:16:41,069 right. You know, what I'm going to do is I'm going to reflect the point down on the 190 00:16:41,069 --> 00:16:46,379 X axis. Okay. So I draw this other line, I reflect it down. And then what I define is 191 00:16:46,379 --> 00:16:56,110 that other, that I cut, this I define to be the sum of these two points. Okay. So. 192 00:16:56,110 --> 00:17:00,649 And that works. Okay. I can add points, I can subtract points. There will be the 193 00:17:00,649 --> 00:17:05,370 inverse. So this kind of like X like integers mod N when you only consider 194 00:17:05,370 --> 00:17:09,559 addition, kind of, kind of, it's not really the same, but you can also single 195 00:17:09,559 --> 00:17:16,770 out the special point O like beautiful O we call the origin, whatever that is. And 196 00:17:16,770 --> 00:17:20,860 this origin kind of acts like a zero. So if I add the origin to the point where I 197 00:17:20,860 --> 00:17:25,120 get the point again, or if I add the point and its inverse I get that point, I get 198 00:17:25,120 --> 00:17:30,630 zero. Okay. So there's something like a zero. And you can also multiply points, 199 00:17:30,630 --> 00:17:34,809 right. I mean what is multiplication, it's just repeated addition. So in brackets n, 200 00:17:34,809 --> 00:17:38,919 this is what I write for point multiplication, just add the point n times 201 00:17:38,919 --> 00:17:43,440 to itself. Okay. So there's nothing fancy going on here. So you can somehow add 202 00:17:43,440 --> 00:17:49,510 points. You can multiply points. That's pretty cool. And if you look closer, you 203 00:17:49,510 --> 00:17:55,780 can look at the special set here that I denoted E brackets, big N. And these are 204 00:17:55,780 --> 00:18:00,600 all the points on the curve such that if I multiplied this point for N it gives me 205 00:18:00,600 --> 00:18:08,130 zero. Okay. And this set for the mathematically inclined people among us I 206 00:18:08,130 --> 00:18:12,500 know say this is somehow the N-torsion of an elliptic curve, whatever that means. 207 00:18:12,500 --> 00:18:16,370 But if you're interested, you can look it up. And this set kind of acts like 208 00:18:16,370 --> 00:18:23,520 additive integers mod n - like two copies of it. Okay. And now this is where the 209 00:18:23,520 --> 00:18:26,980 term super singular comes from. One of the definitions. This is not the only 210 00:18:26,980 --> 00:18:30,530 definition, but this is one of them. If you look at the elliptic curve, not over 211 00:18:30,530 --> 00:18:36,029 the reals, okay, or whichever numbers, but over this finite fields. And if you look 212 00:18:36,029 --> 00:18:41,980 at the torsion, the P-torsion, then this behaves differently for different types of 213 00:18:41,980 --> 00:18:45,279 curves. Okay. The P-torsion is either empty, then we call the curve super 214 00:18:45,279 --> 00:18:50,400 singular; or it's just one copy of of integers mod P and then we call it 215 00:18:50,400 --> 00:18:55,149 ordinary. Okay. It's not really important to know what that means. It just means 216 00:18:55,149 --> 00:18:59,980 that there is a distinction for curves somehow that's somehow ingrained 217 00:18:59,980 --> 00:19:07,730 mathematically deep down there. And because this E N torsion is somehow two 218 00:19:07,730 --> 00:19:13,809 copies of of integers mod N, additive integers mod N, I can generate it by 219 00:19:13,809 --> 00:19:17,539 taking linear combinations of two points, say P and Q, and these are like the 220 00:19:17,539 --> 00:19:21,679 generators we saw earlier. Right. But these are not additive generators instead 221 00:19:21,679 --> 00:19:26,831 of somehow exponential generators. But it, everything behaves kind of similar. And 222 00:19:26,831 --> 00:19:30,240 now you can really use this to do cryptography already. If you wanted to 223 00:19:30,240 --> 00:19:35,899 write it. You can. You can somehow look at the DLP in that group, but there is the 224 00:19:35,899 --> 00:19:40,510 problem again that the DLP in there, there's Shor's algorithm again. Right. So 225 00:19:40,510 --> 00:19:46,970 even if you do cryptography in this group, you run into the same problem. OK, so we 226 00:19:46,970 --> 00:19:51,481 have to do a bit better. We have to search further. And this is where isogenies come 227 00:19:51,481 --> 00:20:03,860 on. Come into the play. So one way you can think of an isogeny is, remember how we 228 00:20:03,860 --> 00:20:10,710 found integers mod N by somehow dividing Z by all the N multiples. And you can do 229 00:20:10,710 --> 00:20:16,919 something similar with an elliptic curve. if you can somehow take part of this 230 00:20:16,919 --> 00:20:24,029 N-torsion and you can divide an elliptic curve by this. You can mod it out and it 231 00:20:24,029 --> 00:20:28,609 turns out this is mathematically well- defined and it gives you another elliptic 232 00:20:28,609 --> 00:20:37,559 curve. Okay. So I take a curve, E1, I take a part of my N-torsion. I divide elliptic 233 00:20:37,559 --> 00:20:42,840 curve E1 by G and I get another elliptic curve E2. And there's something else that 234 00:20:42,840 --> 00:20:46,500 comes along with this construction. And this is what we call the isogeny. This is 235 00:20:46,500 --> 00:20:53,380 a map. OK. Along with this construction comes a map from E1 to E2. And this map is 236 00:20:53,380 --> 00:21:00,769 what we call an isogeny. An isogeny is the map that takes us from one curve to 237 00:21:00,769 --> 00:21:07,140 another curve. And this map is kind of special because it behaves in a nice way 238 00:21:07,140 --> 00:21:12,200 and it plays nicely with the structure that's already ingrained in our curve. 239 00:21:12,200 --> 00:21:17,840 Namely, I can either add two points on my starting curve and send it through that 240 00:21:17,840 --> 00:21:25,240 map to the other curve. Or it can take two points on my starting curve. I can send it 241 00:21:25,240 --> 00:21:31,600 through the map and edit over there and it gives me the same thing. So this map 242 00:21:31,600 --> 00:21:35,539 behaves nicely with point addition. That's pretty nice, just as a side note. So this 243 00:21:35,539 --> 00:21:42,140 map is special. So this is just the remainder of what I said: Adding points on 244 00:21:42,140 --> 00:21:47,250 E1 and sending the result to E2 is the same as sending points to E2 and adding 245 00:21:47,250 --> 00:21:53,890 them there. So this map somehow plays nicely with my laws on my elliptic curve. Now I 246 00:21:53,890 --> 00:22:01,820 have to make a definition: In mathematics, the kernel of a map is the set of all the 247 00:22:01,820 --> 00:22:08,240 inputs to the map that are sent to zero. And we saw this origin O here that acted 248 00:22:08,240 --> 00:22:12,470 like zero. So the kernel of my isogeny, I'm just going to define as all the inputs 249 00:22:12,470 --> 00:22:18,240 to the isogeny that are sent to the zero on the other curve. And in written 250 00:22:18,240 --> 00:22:25,230 notation, it's the set of all P in E1 such that the map of P is 0. It turns out that 251 00:22:25,230 --> 00:22:34,512 this kernel for my isogeny, that I started out with somehow recovers this part of the 252 00:22:34,512 --> 00:22:40,559 end portion that I used to construct. So there's two ways now to think of an 253 00:22:40,559 --> 00:22:47,890 isogeny. So this is what we start with. We reconsidered E1 mod G and it gave us this 254 00:22:47,890 --> 00:22:54,270 map from E1 to E2. But if I start with this map from E1 to E2, we also find the G 255 00:22:54,270 --> 00:22:59,320 again. So there are two ways to represent this map. We can think of a subgroup - 256 00:22:59,320 --> 00:23:06,630 this G - or we can think of the map. And ultimately somehow there is a correspondence 257 00:23:06,630 --> 00:23:12,000 between the various subgroups for different N and isogenies that are somehow 258 00:23:12,000 --> 00:23:15,900 emanating from a curve. We can think of this link or the hairs on my head, they 259 00:23:15,900 --> 00:23:20,760 are going out and then they're going to reach other electric curves maybe. And 260 00:23:20,760 --> 00:23:27,020 these notions can be used interchangeably. So somehow there is a correspondence. And 261 00:23:27,020 --> 00:23:32,659 again, I can choose different ends. So some- how from one curve, I can have many outgoing 262 00:23:32,659 --> 00:23:40,210 isogenies that are different in a sense. And now the thing is in practice, we actually want to 263 00:23:40,210 --> 00:23:43,899 compute these maps. So right now, this is just general abstract nonsense. I didn't 264 00:23:43,899 --> 00:23:47,470 tell you anything of how to compute these things. I just told you there are some 265 00:23:47,470 --> 00:23:50,600 more correspondences. But I mean, what does that even mean? Right. It's useless 266 00:23:50,600 --> 00:23:57,250 if I can't use it in practice. And then there is another thing: You can compute 267 00:23:57,250 --> 00:24:00,409 these things, there are formulas, people have worked on this. But somehow the cost 268 00:24:00,409 --> 00:24:08,000 grows if I enlarge N. So really, in practice, for applications, I want to choose 269 00:24:08,000 --> 00:24:13,670 a small N. Maybe two or three - that would be pretty good. And now the thing is, it's 270 00:24:13,670 --> 00:24:19,250 the supersingular curves for which I can some- how control or choose the possible ends very 271 00:24:19,250 --> 00:24:27,091 very easily. So this is the reason why we reconsider supersingular curves. Now I can 272 00:24:27,091 --> 00:24:33,699 choose my prime to be of this form and then magically this is going to force 2 273 00:24:33,699 --> 00:24:39,559 and 3 being possible. So this is the reason why we choose supersingular ones. 274 00:24:39,559 --> 00:24:45,080 There's some theory which is not interesting for you, but it's important 275 00:24:45,080 --> 00:24:52,350 for implementation. And there's a way basically for us to force the curve to have those 276 00:24:52,350 --> 00:24:57,490 isogenies that we like. But there is another important reason and this is the 277 00:24:57,490 --> 00:25:01,450 reason that actually makes it interesting for cryptography. So what I 278 00:25:01,450 --> 00:25:07,919 can do is: I start with an arbitrary curve, and this just might not be a 279 00:25:07,919 --> 00:25:12,730 supersingular one, just any curve and say I consider all the outgoing two isogenies if 280 00:25:12,730 --> 00:25:19,299 these are possible, 4 and 2. So there's going to be 1, 2 and 3. And then again, 281 00:25:19,299 --> 00:25:24,930 from E1, I can again consider all the outgoing isogenies, and so on and so 282 00:25:24,930 --> 00:25:28,970 forth. So what's going to happen here is: This is going to generate a graph, where 283 00:25:28,970 --> 00:25:36,860 the vertices of my graph are elliptic curves and the edges are isogenies. So somehow 284 00:25:36,860 --> 00:25:44,260 behind the scenes there is this graph hidden. Now, it turns out that if you do 285 00:25:44,260 --> 00:25:48,580 this for a supersingular elliptic curve - and I generated this yesterday for you, 286 00:25:48,580 --> 00:25:52,970 so this is one possible graph - I can remember which prime I took. But here you 287 00:25:52,970 --> 00:25:57,350 can see all the ellipses are ellipitic curves and all the edges between them are 288 00:25:57,350 --> 00:26:03,330 2 isogenies. So this is an example of a supersingular 2-isogeny graph - okay, this 289 00:26:03,330 --> 00:26:11,169 looks pretty wild. I can do the same for N = 3 if it's possible, or is 5 and so on 290 00:26:11,169 --> 00:26:17,020 and so forth. There are many many graphs hidden. But why is the supersingular graph 291 00:26:17,020 --> 00:26:20,900 specific and important? Well, it turns out that somehow the supersingular one is 292 00:26:20,900 --> 00:26:27,440 connected, and it's what we call a Ramanujan graph. I'm going to explain 293 00:26:27,440 --> 00:26:33,740 this in a second. And as a bonus, for implementation purposes, it turns out that 294 00:26:33,740 --> 00:26:39,559 you can do all your implementation in arithmetics in the finite field with p^2 295 00:26:39,559 --> 00:26:45,409 elements. This is nice. So I'm just gonna say that if you don't consider 296 00:26:45,409 --> 00:26:49,200 supersingular curves and you go along these graphs, then what's going to happen 297 00:26:49,200 --> 00:26:54,330 is that somehow this "field of definition", what we call it, could grow 298 00:26:54,330 --> 00:26:59,320 for you to be able to go further, but that would suck for implementation. But 299 00:26:59,320 --> 00:27:04,279 supersingular ones is nice so, F_p^2 is enough. So this is again, is good for 300 00:27:04,279 --> 00:27:10,300 implementation. So somehow magically many many things happen here that are benefiting us. 301 00:27:10,300 --> 00:27:15,460 And again, why is it nice that this is a Ramanujan graph? A Ramanujan graph has 302 00:27:15,460 --> 00:27:21,090 certain optimal expansion properties. This means that if I start from a random point 303 00:27:21,090 --> 00:27:28,539 in my fraph, and I take a random walk with some- how logarithmic steps of the total amount of 304 00:27:28,539 --> 00:27:38,130 vertices, then this will put me in a very uniform place in that graph. And this is 305 00:27:38,130 --> 00:27:43,580 is good for cryptography. Because you only need to take log many steps to somehow 306 00:27:43,580 --> 00:27:50,120 randomize yourself in that graph. And this is what this could look like. I started at 307 00:27:50,120 --> 00:27:55,669 that red ellipses over there. This was my starting point. And then I generated a few 308 00:27:55,669 --> 00:28:01,919 random walks, and the blue points are where I got placed. This might not prove 309 00:28:01,919 --> 00:28:09,099 anything, but it gives you an idea of how, some- how uniformly, it places me around that graph. 310 00:28:09,099 --> 00:28:17,080 So, it's good for cryptography, but there are other reasons, so supersingular elliptic 311 00:28:17,080 --> 00:28:22,400 curves somehow I can actually compute how many of these curves I will have in my 312 00:28:22,400 --> 00:28:26,540 graph. This is another reason to be looking at these things. Because if I 313 00:28:26,540 --> 00:28:30,740 don't even know how many curves are in my graph - well I can't really say anything 314 00:28:30,740 --> 00:28:35,179 about the security - but at least for supersingular ones, I can see they're 315 00:28:35,179 --> 00:28:42,169 roughly p/ 12 many. Okay, and then again, if I'd choose my p about n bits, well then 316 00:28:42,169 --> 00:28:47,660 I really know that my graph has about 2^n elements. And at least there I can see 317 00:28:47,660 --> 00:28:51,830 something about the cryptographic strength, right? I can make M big and then 318 00:28:51,830 --> 00:28:54,620 you can say: Oh yeah, you have this random graph, you take some n-length walks and 319 00:28:54,620 --> 00:28:58,669 n-length walks and then it places you randomly in there and the whole graph is 320 00:28:58,669 --> 00:29:04,320 about 2^n elements. And then I can say something about the expected runtime of 321 00:29:04,320 --> 00:29:09,779 algorithms. So this is another reason why we want to consider supersingular curves: 322 00:29:09,779 --> 00:29:16,139 Because I can tell you how many elements are in this graph. So a quick summary of 323 00:29:16,139 --> 00:29:21,490 what we saw, why this is nice. So what you get is a compact representation of an 324 00:29:21,490 --> 00:29:27,549 (l+1)-regular graph. And we saw examples, e.g. l = 2, l = 3. Bigger values are 325 00:29:27,549 --> 00:29:30,700 possible, but we don't even care about those because this is what gives us the 326 00:29:30,700 --> 00:29:38,510 fastest arithmetic such that we can work with F_p^2. This is nice, this keeps our 327 00:29:38,510 --> 00:29:43,759 implementation fast. I can tell you how many vertices are in the graph: about 328 00:29:43,759 --> 00:29:48,840 p/12. And again, such that the graph for mixing properties that are useful for 329 00:29:48,840 --> 00:29:52,369 cryptographic applications. So because I want to use this ultimately for 330 00:29:52,369 --> 00:29:59,850 cryptography. And again, that's what we said: If I choose an n-bit prime p, then 331 00:29:59,850 --> 00:30:07,159 the graph has about 2^n vertices - so exponentially many vertices. And it turns 332 00:30:07,159 --> 00:30:16,240 out that there are some hard problems that I can ask you to solve in this graph that 333 00:30:16,240 --> 00:30:23,130 don't have good quantum algorithms. So one hard problem is this: I take two super 334 00:30:23,130 --> 00:30:28,630 singular elliptic curves, so I just give you two random curves in this graph and ask 335 00:30:28,630 --> 00:30:33,120 you to find a nice arch in the path between those isognies, or three 336 00:30:33,120 --> 00:30:37,880 isogenies. And it turns out that this just doesn't have a good quantum algorithm. So 337 00:30:37,880 --> 00:30:42,750 classically, I mean the numbers are super important here, but classically the 338 00:30:42,750 --> 00:30:47,700 complexity is p, over the fourth root of p, and the best quantum algorithm is a bit 339 00:30:47,700 --> 00:30:52,679 better at it. I mean again, it's not super important what's there. What's important 340 00:30:52,679 --> 00:30:58,000 is that there is no polynomial time algorithm compare to ideal p that we 341 00:30:58,000 --> 00:31:03,060 started with. So if I make this p very large and your quantum computer, your 342 00:31:03,060 --> 00:31:07,910 hypothetical quantum computer, will probably not solve this. Okay, so that's 343 00:31:07,910 --> 00:31:14,960 cool. So how do we do key exchange? I start with a supersingular elliptic curve E, 344 00:31:14,960 --> 00:31:21,350 where I chose my prime p such that two and three isogenies are possible. And then 345 00:31:21,350 --> 00:31:26,019 Alice - earlier I remember she chose a random number a - but now Alice will 346 00:31:26,019 --> 00:31:35,539 choose a random subgroup A, and she will send E mod A to Bob. This amounts to Alice 347 00:31:35,539 --> 00:31:40,940 for computing the nice isogeny. And again, this is a very symmetrical key exchange, 348 00:31:40,940 --> 00:31:45,459 except that now Bob won't use the same generator but Bob will use the 3 349 00:31:45,459 --> 00:31:50,830 isogenies. So Bob will choose a random subgroup B, and then he will compute E mod 350 00:31:50,830 --> 00:31:58,190 B and send this to Alice. And this is the picture: There's Alice, there's Bob. Alice 351 00:31:58,190 --> 00:32:04,520 chose A, Bob chooses B. Alice sends E mod A to Bob, Bob sends E mod B to Alice. And 352 00:32:04,520 --> 00:32:12,129 then how do they agree on a shared key? They will just mod out by their respective 353 00:32:12,129 --> 00:32:16,419 subgroups again. And it turns out that the elliptic curve that they find is going to 354 00:32:16,419 --> 00:32:23,090 be the same for both of them. Okay, so how does that work? Again, let's return to our 355 00:32:23,090 --> 00:32:32,610 graph: Say Alice and Bob agree on a black curve - the black curve on the left side. 356 00:32:32,610 --> 00:32:36,929 And then Alice will compute these red steps, which correspond to taking a 357 00:32:36,929 --> 00:32:42,030 subgroup. So Alice will compute these red steps for her secret subgroup and she will 358 00:32:42,030 --> 00:32:48,669 end up at the red curve in the upper right corner. And Bob will do the same. But now 359 00:32:48,669 --> 00:32:53,370 Bob is not in the 2-graph, but in the 3-graph - so this is the three graph. And 360 00:32:53,370 --> 00:32:57,600 the black curve that he started from in the 3-graph is down there. He will also 361 00:32:57,600 --> 00:33:02,039 select a random subgroup, compute the secret path and Bob will end up in the 362 00:33:02,039 --> 00:33:06,549 blue curve. Now Alice will send her red curve to Bob. And Bob, will send his blue 363 00:33:06,549 --> 00:33:12,039 curve to Alice. And then Alice will consider the blue curve in the 2-graph. So 364 00:33:12,039 --> 00:33:17,320 Alice starts from the blue curve that she got from Bob - and this is the position in 365 00:33:17,320 --> 00:33:23,260 the 2-graph. And again, she computes that same secret path and ends up in the green 366 00:33:23,260 --> 00:33:30,390 curve, which is up there. Bob got the red curve from Alice. So Bob has the red curve 367 00:33:30,390 --> 00:33:34,335 there. Again, he computes the path and then ends up at the green curve. And it 368 00:33:34,335 --> 00:33:38,440 turns out that the green curves here and there are the same. And this is going to 369 00:33:38,440 --> 00:33:45,960 be the shared key for them. This is SIDH. Okay. This is how you exchange a secret 370 00:33:45,960 --> 00:33:54,101 key using the supersingular isogeny graph. That's the whole magic. And again, let's 371 00:33:54,101 --> 00:34:01,370 compare these two things a bit: the DLP- based one and the SIDH one. So we had the 372 00:34:01,370 --> 00:34:07,730 square, Alice and Bob started in the upper left corner and again ended up in the lower 373 00:34:07,730 --> 00:34:14,760 right corner. And SIDH looks very similar: Alice and Bob start with this common curve 374 00:34:14,760 --> 00:34:22,720 E in the upper left corner. Again, Alice computes only horizontal arrows because 375 00:34:22,720 --> 00:34:27,750 she knows her secret group A, and Bob only computes the vertical arrows because only 376 00:34:27,750 --> 00:34:34,490 he knows his secret group B. And again, they both end up in the lower right 377 00:34:34,490 --> 00:34:40,110 corner, where they define the shared key. But now in this case, the shared key is 378 00:34:40,110 --> 00:34:44,860 not an element to the a^(ab), but elliptic curve. But again, there's a mathematical 379 00:34:44,860 --> 00:34:51,881 way to attach a unique number to it. So it's a solved problem to actually make 380 00:34:51,881 --> 00:34:59,660 some bytes out of this. And yeah, that's SIDH. That's everything. This is a nice 381 00:34:59,660 --> 00:35:06,520 example of a post-quantum cryptography scheme that we have today. And now 382 00:35:06,520 --> 00:35:13,290 let me finish with a quick conclusion. I showed you this "zoo": There are several 383 00:35:13,290 --> 00:35:18,840 candidates somehow for post-quantum cryptography. And among them are some 384 00:35:18,840 --> 00:35:26,090 schemes based on supersingular elliptic curve isogenies, and we've seen that we 385 00:35:26,090 --> 00:35:30,460 know some hard problems involving these isogenies that are hard for quantum 386 00:35:30,460 --> 00:35:40,511 computers, which makes this one possible scheme for a quantum computer world. And 387 00:35:40,511 --> 00:35:44,950 probably I should say that we don't envision a world here where we users like 388 00:35:44,950 --> 00:35:49,960 me or you are in possession of quantum computers. Probably, what we think about 389 00:35:49,960 --> 00:35:55,210 is that state actors are in positions of quantum computers. So this is even more 390 00:35:55,210 --> 00:36:01,500 important for us to be looking into these things. And what we saw was to perform a 391 00:36:01,500 --> 00:36:05,290 Diffie-Hellman-like key exchange using these isogenies. But - this is what I 392 00:36:05,290 --> 00:36:10,410 didn't tell you about in his talk - there are also schemes for signature-based 393 00:36:10,410 --> 00:36:15,950 isogenies, there is this scheme for key- encapsulation-based isogenies. So 394 00:36:15,950 --> 00:36:22,680 there are other possible candidates for other cryptographic building blocks based 395 00:36:22,680 --> 00:36:29,110 on isogenies and these hard problems. And if you're super interested about this, you 396 00:36:29,110 --> 00:36:36,660 can either ask me or come to our assembly and if you like reading scientific papers, 397 00:36:36,660 --> 00:36:39,900 papers about such isogenies and cryptography in general, you can find this 398 00:36:39,900 --> 00:36:45,240 on the eprint archive. So this is a web page where people post pre-prints about 399 00:36:45,240 --> 00:36:50,370 their papers and there's a huge collection about, among of them, isogeny papers. So 400 00:36:50,370 --> 00:36:58,380 if you're interested in this, this is the place to research. And with that, I would 401 00:36:58,380 --> 00:37:01,440 like to thank you all for your attention. 402 00:37:01,440 --> 00:37:14,870 *applause* 403 00:37:14,870 --> 00:37:22,600 Herald Angel: Is there any question? OK, I got the Signal Angel there, doing some 404 00:37:22,600 --> 00:37:27,640 Morse code? Microphone 1: Yes. Can you recommend any 405 00:37:27,640 --> 00:37:33,280 literature for the theoretical background? naehrwert: The theoretical background? 406 00:37:33,280 --> 00:37:41,510 There are a few papers that are nice. Okay. The question again was literature 407 00:37:41,510 --> 00:37:46,050 about theoretical background. And yes, there are a few papers that are giving 408 00:37:46,050 --> 00:37:53,180 some nice, even theoretically involved summaries about the background. And your 409 00:37:53,180 --> 00:38:00,940 best bet is to go to eprint and you enter 'isogenies' in the mask of search terms, 410 00:38:00,940 --> 00:38:07,400 or 'SIDH', and look at the papers that say, maybe, 'A Short Introduction to 411 00:38:07,400 --> 00:38:11,380 Isogenies' or something like that. I mean, you will find them if you search for them. 412 00:38:11,380 --> 00:38:17,500 I don't know them from the top of my head, but they're out there for sure. Yeah, and 413 00:38:17,500 --> 00:38:22,590 thanks for him - So there is a very recent paper by Craig Costello, also somewhat 414 00:38:22,590 --> 00:38:26,670 titled 'A Short Introduction', something like that. So this is also maybe a good 415 00:38:26,670 --> 00:38:30,830 source for you to look at. Herald Angel: Um, yeah, 'Isogenies for 416 00:38:30,830 --> 00:38:32,730 Beginners'. naehrwert: 'Isogenies for Beginners'. 417 00:38:32,730 --> 00:38:35,790 Thank you. *audience laughing* 418 00:38:35,790 --> 00:38:44,500 Microphone 2: Hello. Yeah. So you've used elleptic curve as an algebraic group, 419 00:38:44,500 --> 00:38:54,700 right, to compute these isogeny graphs. Why do you use elliptic curves - what's 420 00:38:54,700 --> 00:39:02,770 the properties of elliptical curves as a group? So, could you use any group to 421 00:39:02,770 --> 00:39:10,980 compute these graphs and could you use these as the basis for your scheme or your 422 00:39:10,980 --> 00:39:14,890 key exchange scheme? naehrwert: Okay, so the question was why 423 00:39:14,890 --> 00:39:21,280 use elliptical curves and the group structure that the impose to look at 424 00:39:21,280 --> 00:39:26,220 isogeny graphs involving elliptical curves and whether I could use other groups. And 425 00:39:26,220 --> 00:39:34,001 actually, there's a two-fold answer maybe. So if I go back - or actually let me go to 426 00:39:34,001 --> 00:39:40,650 my backup slide, which gives you SIDH in its full glory - you consider some extra 427 00:39:40,650 --> 00:39:46,170 information being sent, namely these generators from my group and actually the 428 00:39:46,170 --> 00:39:51,700 same commutative diagram for SIDH. You could, in theory, compute using another 429 00:39:51,700 --> 00:39:57,670 group as well, that has the proper subgroup structure, but the graph that you 430 00:39:57,670 --> 00:40:03,910 will find is probably not going to be interesting. I mean it's really somehow 431 00:40:03,910 --> 00:40:09,100 that Righello property that makes the graph interesting for cryptography. But 432 00:40:09,100 --> 00:40:15,020 yes, in theory, the SIDH commutative diagram you could also compute for other 433 00:40:15,020 --> 00:40:20,720 groups, yes. Microphone 2: OK. 434 00:40:20,720 --> 00:40:28,910 Microphone 3: Uh... How good are classical algorithms that tried to reverse that SIDH 435 00:40:28,910 --> 00:40:37,010 problem, because that will be the bound for how large your keys have to be, to be 436 00:40:37,010 --> 00:40:39,931 secure. naehrwert: Yes. So the question was: How 437 00:40:39,931 --> 00:40:46,980 good are classical algorithms? And again, I said, I think the runtime for those is 438 00:40:46,980 --> 00:40:52,950 squared of p. And this tells you how big you have to choose B. 439 00:40:52,950 --> 00:40:59,160 Microphone 3: And how confident are you that this really is hard for quantum 440 00:40:59,160 --> 00:41:03,510 computers as well? naehwert: Well, how confident am I that 441 00:41:03,510 --> 00:41:07,020 this is really hard for quantum computers? So first of all, cryptography 442 00:41:07,020 --> 00:41:10,740 is all about confidence, right? So someone proposes a problem, this problem gets 443 00:41:10,740 --> 00:41:15,350 crypto-analyzed. And if it's not broken after 40 years, then people will say, I'm 444 00:41:15,350 --> 00:41:19,810 pretty, pretty confident this is good. And maybe if the NSA doesn't tell you anything 445 00:41:19,810 --> 00:41:26,200 about it, or maybe if they don't have, you know, anything on it, then you can also 446 00:41:26,200 --> 00:41:35,240 see that you're confident in it. But I think this is really a question that only 447 00:41:35,240 --> 00:41:40,980 time can answer, right? Microphone 4: Yeah. Is it possible to 448 00:41:40,980 --> 00:41:47,321 prove that no polynomial-time algorithms for the isogenies problems can exist 449 00:41:47,321 --> 00:41:51,810 for a quantum computer? naehrwert: Yeah, that's a good question. 450 00:41:51,810 --> 00:41:59,610 How do you prove that no algorithm exists? This brings us into territories, like ... 451 00:41:59,610 --> 00:42:06,380 Yeah. I don't know. Yeah. No. Let's not do that. 452 00:42:06,380 --> 00:42:16,500 Microphone 1: Yeah. Good talk by the way. At the last slide you say that this is hard 453 00:42:16,500 --> 00:42:20,850 for a quantum [computer]. But that can't be true because we don't even know if any 454 00:42:20,850 --> 00:42:25,600 algorithm is hard for classic computers. Right? So, I'm guessing you're saying that 455 00:42:25,600 --> 00:42:31,340 intuitively it feels hard, which, you know, is the same intuition I have about 456 00:42:31,340 --> 00:42:37,650 e.g. factoring in. So, you mention there's multiple candidates for post-quantum 457 00:42:37,650 --> 00:42:44,120 cryptography, and they all intuitively feel hard somehow. Do you know if this 458 00:42:44,120 --> 00:42:48,480 specific candidate, would this be your horse in a race? Is there anything about 459 00:42:48,480 --> 00:42:54,320 this specific way that you think would be the best fit for post-quantum 460 00:42:54,320 --> 00:42:59,310 cryptography? naehrwert: Okay. Your opinion is very 461 00:42:59,310 --> 00:43:03,410 valid. Of course, we don't know if it's hard, right? This connects back to the 462 00:43:03,410 --> 00:43:07,400 other questions: How do you trust something like that? Again, people do 463 00:43:07,400 --> 00:43:11,950 crypto analysis for 40 years or whatever. And then you say, oh, no one found 464 00:43:11,950 --> 00:43:16,030 anything - it's probably hard, right? But it hasn't been an exact 40 years. You 465 00:43:16,030 --> 00:43:21,480 cannot say that. Indeed these things are relatively new. And personally, I'm not 466 00:43:21,480 --> 00:43:28,430 gonna, I don't know, believe in any of these things until some time passes. So my 467 00:43:28,430 --> 00:43:33,060 reason for looking into these things really is more a mathematical curiosity, 468 00:43:33,060 --> 00:43:38,500 because I think these things are beautiful. And the cryptography that 469 00:43:38,500 --> 00:43:43,370 arises from it is more of a side-effect for me personally. So I'm not going to put 470 00:43:43,370 --> 00:43:51,180 out any guesses on which of these things is actually going to win the PQ race or 471 00:43:51,180 --> 00:43:56,140 whatever. Microphone 2: (Yeah. I am.) You showed or 472 00:43:56,140 --> 00:44:01,660 said you think it's hard for the classical way and for the quantum cryptography way. 473 00:44:01,660 --> 00:44:08,830 I think I just read a paper last year about a combined way in classical and 474 00:44:08,830 --> 00:44:14,261 quantum cryptography combined, which outperforms either one of those ways. Do 475 00:44:14,261 --> 00:44:23,820 you think this could also be relevant or gonna make this one way to put in 476 00:44:23,820 --> 00:44:27,600 computable in polynomial time? naehrwert: Are you talking about an 477 00:44:27,600 --> 00:44:32,640 algorithm that somehow combines a classical step and a quantum step to break 478 00:44:32,640 --> 00:44:33,900 this? Microphone 2: Yes. 479 00:44:33,900 --> 00:44:39,390 naehwert: Yeah well, most algorithms that we say use a quantum computer involve a 480 00:44:39,390 --> 00:44:43,330 classical part anyways. If you think about Shor's algorithm, there's a classical part 481 00:44:43,330 --> 00:44:49,600 and a quantum computer part. So I'm not sure which algorithm you read about, but 482 00:44:49,600 --> 00:44:53,560 I'm sure that somehow all the quantum algorithms involve a classical part 483 00:44:53,560 --> 00:44:58,690 implicitly anyways. Herald: Signal Angel? 484 00:44:58,690 --> 00:45:03,400 Microphone 3: Yeah. Can you please name the mentioned contestants in the list 485 00:45:03,400 --> 00:45:10,400 'Challenge-based Isogenies'? naehrwert: So there is SSIKE, I believe: 486 00:45:10,400 --> 00:45:16,170 supersingular isogeny key encapsulation, but actually I don't really follow the 487 00:45:16,170 --> 00:45:22,080 NIST thingy closely, so I actually couldn't even name all the names that are 488 00:45:22,080 --> 00:45:27,440 involved in it, but you can look it up on the NIST website and I believe somewhere there 489 00:45:27,440 --> 00:45:33,190 is also a classification of the contenders into this view. So they will tell you 490 00:45:33,190 --> 00:45:37,180 which contenders are based on lattices and which contenders are based on codes and 491 00:45:37,180 --> 00:45:41,400 which ones are somehow based on isogenies. But off the top of my head, actually, I 492 00:45:41,400 --> 00:45:49,990 don't even know. Sorry. Microphone 1: So if I got everything 493 00:45:49,990 --> 00:45:56,730 correctly, though, those isogenies are group homomorphisms between the elliptic 494 00:45:56,730 --> 00:46:03,580 curves and the factor group of the elliptic curve by g. And which has kernel 495 00:46:03,580 --> 00:46:05,040 g again. naehrwert: Yes. 496 00:46:05,040 --> 00:46:10,170 Microphone 1: And you said that finding the isogeny path in the graph is rather 497 00:46:10,170 --> 00:46:15,720 difficult. But wouldn't the real difficulty rather be finding the subgroups 498 00:46:15,720 --> 00:46:20,290 G - because a group homomorphism between the elliptic curve and the factor group 499 00:46:20,290 --> 00:46:23,450 with kernel g is simply the canonical protection. 500 00:46:23,450 --> 00:46:29,500 naehrtwert: Exactly. So I see you are mathematically trained, which is very nice 501 00:46:29,500 --> 00:46:34,140 and I appreciate that, this is great and I am very happy about that. And yeah, if you 502 00:46:34,140 --> 00:46:41,440 look at the slide actually, the secrets are these alphas and betas, which somehow 503 00:46:41,440 --> 00:46:46,420 determine the subgroup. And yes, finding those isogeny path is equivalent to 504 00:46:46,420 --> 00:46:50,240 finding the alpha, somehow, that generates this group. And as you said correctly, 505 00:46:50,240 --> 00:46:56,670 finding the isogeny path is somehow finding this group. But it's just 506 00:46:56,670 --> 00:47:00,940 restating the problem. But it's still hard somehow to find this group. Yeah. 507 00:47:00,940 --> 00:47:05,430 Microhone 1: All right. Thanks. naehrwert: Thank you. Very cool. 508 00:47:05,430 --> 00:47:08,940 Microphone 2: Yeah, thank you for the great talk. So, can you play this game a 509 00:47:08,940 --> 00:47:15,270 little bit further? I mean, can you choose higher-dimensional abelian varieties to 510 00:47:15,270 --> 00:47:19,440 make it even more secure? Or is it just absolutely inaccessible? I mean, from the 511 00:47:19,440 --> 00:47:24,160 computation perspective, the choice of field of definition is difficult, for 512 00:47:24,160 --> 00:47:26,430 example, so... naehrwert: Okay, so the question was on 513 00:47:26,430 --> 00:47:30,510 whether you can use higher-dimensional abelian varieties and maybe for the people 514 00:47:30,510 --> 00:47:35,760 who don't know what that means: You can attach a dimension to these things in the 515 00:47:35,760 --> 00:47:41,270 elliptic curves, somehow have a dimension 1 attached to them. And the question was, 516 00:47:41,270 --> 00:47:45,720 can you somehow look at dimension 2, dimension 3 or higher? And actually, back 517 00:47:45,720 --> 00:47:51,210 in the days when people were thinking about the DLP problem on the points of 518 00:47:51,210 --> 00:47:55,570 elliptic curves that I mentioned briefly, people had the idea of maybe using 519 00:47:55,570 --> 00:48:01,231 dimension 2 or dimension 3. But it turns out, that the DLP problem actually, at 520 00:48:01,231 --> 00:48:06,170 some point, gets easier in higher dimensions. So, classically if you look at 521 00:48:06,170 --> 00:48:10,250 the DLP, you somehow want to stay at dimension 2, but now, what you can do is, 522 00:48:10,250 --> 00:48:14,570 you can look at isogenies between dimension-2 and dimension-3 ones. And 523 00:48:14,570 --> 00:48:17,860 actually the problem that arises there - and this makes elliptical curves very 524 00:48:17,860 --> 00:48:23,260 special - is that we can compute isogenies rather efficiently for elliptical curves 525 00:48:23,260 --> 00:48:27,510 because of Velu's formulas. Okay. So this gives us a very direct means of 526 00:48:27,510 --> 00:48:32,670 computing D, but it actually gets hard as the dimension grows. For example, for 527 00:48:32,670 --> 00:48:40,090 dimension 2 already, the only isogenies that I am able to efficiently compute are 528 00:48:40,090 --> 00:48:45,890 2- and 3-isogenies. So there are some packages out there that can compute higher 529 00:48:45,890 --> 00:48:50,850 ones, but only if my prime is very small and for dimension 3 and higher it gets 530 00:48:50,850 --> 00:48:55,810 even harder. And then there is another thing that comes into play. So dimension-2 531 00:48:55,810 --> 00:49:00,300 varieties, they all arise from what we call hyperelliptic curves. But if we look 532 00:49:00,300 --> 00:49:07,260 at dimension-3s and higher, then sometimes you land at a point in your graph that 533 00:49:07,260 --> 00:49:11,600 does not come from a hyperelliptic curve anymore. So there is another complication. 534 00:49:11,600 --> 00:49:17,600 So I mean, I had a friend who was looking into genus-2 isogenies and it's possible 535 00:49:17,600 --> 00:49:24,260 to go there. But I don't know. I think personally this is more of a toy than 536 00:49:24,260 --> 00:49:31,440 something that's good in practice. Microphone 2: Can you use this scheme to 537 00:49:31,440 --> 00:49:35,650 implement a fully homomorphic encryption scheme? Or is it already? 538 00:49:35,650 --> 00:49:40,860 naehrwert: Uhhh... No. No. *laughing* 539 00:49:40,860 --> 00:49:45,440 naehrwert: Yeah, no fully homomorphic encryption is somehow a pipe dream, but I 540 00:49:45,440 --> 00:49:51,030 mean sometimes it's possible. So the idea is that you can add cipher texts and get 541 00:49:51,030 --> 00:49:55,840 the sum of the ciphered texts and have a second operation, namely you should be 542 00:49:55,840 --> 00:50:00,120 able to multiply ciphertexts and get the multiplication of two ciphertexts. But we 543 00:50:00,120 --> 00:50:07,490 didn't even talk about encryption. Microphone 2: Yeah. Another question: Is 544 00:50:07,490 --> 00:50:12,110 there any crypto primitive used in the isogeny approach that cannot be Stark- 545 00:50:12,110 --> 00:50:16,020 reduced to finding a hidden subgroup in an abelian group? 546 00:50:16,020 --> 00:50:18,870 naehrwert: Could you repeat the question, please? 547 00:50:18,870 --> 00:50:22,960 Microphone 2: Is there any crypto primitive used in the isogeny approach 548 00:50:22,960 --> 00:50:28,560 that cannot be Stark-reduced to finding a hidden subgroup in an abelian group? 549 00:50:28,560 --> 00:50:36,860 naehrwert: Okay. I think this question tries to connect back to the hidden shift 550 00:50:36,860 --> 00:50:44,110 problem or the hidden subgroup problem and Berg's algorithm. But I think I'm not able 551 00:50:44,110 --> 00:50:47,670 to answer that question now without talking to the person that actually asked 552 00:50:47,670 --> 00:50:55,130 it because it's a bit vague. So I'm sorry about that. 553 00:50:55,130 --> 00:50:59,050 Microphone 3: How do you send an elliptical over the wire? 554 00:50:59,050 --> 00:51:02,680 naehrwert: Yeah, maybe I should answer that actually. So we saw the 555 00:51:02,680 --> 00:51:09,000 parameterization of the curve that had these coefficients A and B. But what 556 00:51:09,000 --> 00:51:14,510 I didn't tell you is that to an elliptic curve you can actually attach what we call 557 00:51:14,510 --> 00:51:19,770 an invariant in mathematics and for an elliptical curve, this is called a 558 00:51:19,770 --> 00:51:25,670 j-invariant and it's a single integer which determines this elliptical curve 559 00:51:25,670 --> 00:51:29,600 uniquely. So if I want to send an elliptical curve, I can simply send you 560 00:51:29,600 --> 00:51:34,600 its j-invariant. And if you know the field of definition, you're going to be able to 561 00:51:34,600 --> 00:51:40,190 somehow recompute it just from the single value. So it's actually quite a compact 562 00:51:40,190 --> 00:51:45,970 representation which makes this also interesting. Yeah. 563 00:51:45,970 --> 00:51:49,260 Herald: I guess this is all. Thank you. 564 00:51:49,260 --> 00:51:54,860 *applause* 565 00:51:54,860 --> 00:51:58,800 *postroll music* 566 00:51:58,800 --> 00:52:23,000 subtitles created by c3subtitles.de in the year 2020. Join, and help us!