36C3 preroll music Applause naehrwert: Yeah. Thank you for the audience and thanks that you came. Thanks for the Congress for giving me the opportunity to be here tonight, to be able to tell you a bit about post quantum cryptography, a bit about as isogenies. I mean, just educate the people a bit about what that means, even, because I'm not too sure how many of you heard about that before. Yeah, let's just jump right in. So my day job is being a mathematics PhD student at an undisclosed university. You can ask me in private if you're interested. So previously I did physics. I was also or maybe I'm still a bit active in the console hacking scene. And if you're interested about that shameless plug, you can find us at Nintenbros Assembly later. You can ask us all about our somehow console hacking endeavors. But enough about that. So I brought you some pictures, screenshots of websites. So I don't know if you have seen the chatter on social media and the blogs here recently about that Google paper on quantum supremacy. So there is a Nature article about that beyond quantum supremacy. And there is a Verge article that Google confirms quantum supremacy and breakthrough, whatever that means. There is Google's own blog post about it. Notice there are always these shiny pictures of these huge tubs filled with helium where they house these quantum computers. So supremacy means the state or condition of being superior to all others in authority, power, or status. So calling something quantum supremacy, I mean, that screams something being pretty amazing. But what actually does this mean for us? What does it mean for cryptography? And I think I can relieve you all about from from maybe some fears that you had for us in practice. Maybe today it doesn't really mean anything yet. So for cryptography none of our underlying assumptions, whatever it means for now, are being actively broken yet as we know or that we know of. But in theory, they are broken. Okay. And because they're only broken in theory, that's pretty good. So we can still blame the designers and implementers of whatever we cook up for when things go wrong. So that's nice, too. But as I already wrote in the abstract a bit for this talk, we should be, somehow, better be safe than sorry. So instead of somehow waiting until the point of where quantum computers somehow become feasible to break our cryptography, we should probably research it today. It's a bit with the climate change, right? Suppose it's right to save our climate today instead of waiting until it's too late. So if we're going to be reborn to do the same for cryptography. There are also three upcoming talks I want to advertise here a bit. I think I don't remember the days, but descriptions look pretty interesting. So I'm going to leave that up for a few seconds. There is one called Provable Insecurity, one called Cryptography Demystified and one about high assurance cryptography software. I'm sure this is gonna be interesting. Okay, let's return back to what I want to talk about. So there's something I chucklingly call the Post-Quantum Cryptography Zoo. There are a few buzzwords up there. You don't really have to know what they mean. I'm just going to say them out loud. Lattices, codes, multivariate polynomial systems. That's also a bit of a mouthful. And hash based cryptography. And there is the one that I want to briefly talk about tonight called supersingular elliptic curve isogenies. OK, so this is the stuff that I really like. Isogenies, they are great. And now I'm going to tell you why they're so great. All right. So I don't know how many of you have a mathematics background. Maybe I can do a test. Can people raise their hands where if they have some formal training in, say, algebra? Yeah. Okay. So that's pretty good. So I'm just gonna tell you some something about it. There are decimal numbers. This is Pi. Then there are rational numbers somehow the are, one half, one third and so on and so forth. Then there are integers from minus infinity to plus infinity and they follow nice whole steps. But for working with those numbers and for cryptography, we want something that's nicer behaved. We want somehow a finite set. OK. So this is just important for implementation. And the ones that we want to work with, I'm just going to remind you, are the integers modulo N, so we take some positive integer N, big N, and then we consider the set from zero to N minus one. Okay. And these numbers do follow certain addition and multiplication rules and it pretty much works like a clock face. OK. I chose N is 12 here and, just bear with me, imagine my clock face goes from zero to eleven instead of from one to twelve. But it's really the same. For example, if I tried to add ten to five. OK, I start from ten. I go two steps and then I arrive at zero. This is where my clock ticks over. Right. Like on a real clock. And then you go three more steps. And so ten plus five mod twelve is three. So it's numbers that kind of behave this way. Think of addition on on a clock face. And for the computer scientists out there or, I mean, everyone probably knows about that, for a computer they're like the 8 bit integers where N is 2 to the 8. And then these are the numbers from 0 to 255, and so on and so forth. So these are the numbers that we want to work with. Just to set the stage a bit. And these isogenies. We will live in a world where we we work with somehow related numbers to these integers mod N. And now for big N, we choose a prime P and then these integers mod P, they represent what we call the finite field with P elements. Okay. And you can think of this as a set that has exactly P elements and really kind of behaves like the real numbers. Okay. You can add numbers, you can subtract numbers. You can divide by everything but zero. Okay. And this finite field with P elements works really the same. It's just a finite set, but everything is invertable except zero. Okay. And these are the numbers that we want to work with and computers can do that. So that's fine. And just for the sake of telling you, there are also fields that have somehow P to the R elements, but they are not the same as what people are. Okay. But there is a way to construct it. But that's all you need to know about. So this is really the set of numbers that we're going to work over and that that's all you need to know. Okay. So the cryptographic problem that I want to focus on this talk is simple key exchange. I'm not gonna talk about signatures, I'm not going to talk about encryption, nothing. Let's just focus on this one simple problem of how do Alice and Bob exchange a key without anyone else somehow getting access to that key? And I mean, there are somehow classical solutions to that. I could put my key in a suitcase and I could bring it to Alice or I could somehow pay someone to bring the suitcase to Alice. Or maybe people heard about the thing where I put my lock on the box and I ship it to Alice and she puts her lock on the box and she ships ships it back now I remove my lock and I ship it to Alice again. OK, so there are countless ways, but we want to somehow do this in a nice, instantaneous kind of way using mathematics. Okay. So this simple problem is what we're going to focus on. And classically (whatever that means for now) this has been set off by Diffie-Hellman. And this is this nice paper from 1979 the title is New Directions in Cryptography. So this already tells you that something important must be going on and what you somehow invented there was a way to exchange keys between two parties using a nice, well- defined problem. Okay. And how does it work? Okay. I'm just gonna tell you how it works. So there are two parties, Alice and Bob. A and B. They agree on a safe prime modulus, N. Okay. So this is the integers mod N, which I saw, and a generator G. So what does that mean? Basically in my set, from zero to N, I want to single out one element such that every element can be written as a power of that element. And somehow this means it generates it. Right. So every Y can be written as G to the X mod N. Okay, this is my setup. And then there is Alice and Bob and they agree on these two parameters. Okay. And now how do we do the key exchange? So it's very symmetrical. So Alice chooses a random A in the set from one to N minus one. And she sends big A is G to the small a mod N to Bob. And as you might have guessed it, because I said it's symmetrical, Bob does the same. Okay. So how does the picture go? So Alice on the left, she chooses a random small A. And she sends that big A to Bob. Bob chooses a random small B. He sends the big B to Alice. And then somehow, you know, you have to combine them somehow. Right. How do you do this? So this is nice to compute the shared k, the shared key. So Alice takes the B, she got from Bob and raises it to the power of her own random secret value. And Bob does the same. And magically from mathematics, they both get the same small k. And now I'm going to tell you why, somehow, this is hard for anyone else to get the same small k. So now bear with me. I'm gonna write it down mathematically, first of all, why not teach you a bit about that as well? So this is this diagram, this commutative diagram that somehow represents this key exchange that just happened. Okay. So Bob and Alice, they both started in the left upper corner with the G and they both end up in the lower right corner, the G the AB. So they both are able to somehow compute G to the AB and no one else is. And how does that work? Well, Alice will only compute the horizontal arrows, so she only raises to the power of small A because that's her random secret that only she knows. And Bob only computes the vertical arrows, so he only raises to the power of small B, because that's the secret to he knows and no one else does. And I mean by the commutativity and the associativity of exponentiation, they just agree on the same G to the AB which is which is cool. And somewhere in there there hides a problem that we like to call the discrete logarithm problem and it just happens for integers mod N if I choose my N appropriately, I'm not gonna tell you how, but just believe me if I choose it appropriately. If I give you Y and G, for you it's hard to find the small X. Somehow like taking a logarithm, and we call it the discrete logarithm because it's a discrete set of numbers instead of the continuous decimal numbers, what we started with was this discrete finite set of numbers and this DLP is hard. Okay. This is a hard problem for classical computers. And the best classical generic algorithm - I'm not gonna talk about somehow algorithms that specifically target integers mod N, I'm just going to talk about generic algorithms for for this DLP problem. The best algorithm somehow has run time square root of big N the number of elements and say I chose my N about the size of 2 to the small n, or n bits. Then solving this takes exponential time in n, right, because the square root of 2 to the n is still pretty big. Okay, this is about 2 to the n half, and if I make n a thousand is still 512 bits. So this is a hard problem. But recently there has been a record for factoring and DLPing over a seven hundred ninety five bit modulus and they use a bit of a better algorithm, but still, I mean it still took them a long time. Okay, so if I remember correctly, this feed took them 4000 core years on a two point one gigahertz computer. I mean, that's still 4000 core years. So this is a long time. Okay. But as you can see, it's possible to solve this. I mean, just put enough, if I have a big enough hammer, I can solve this. Okay. But again, you can make N pretty big, bigger than anything being able to solve this anymore. But. Okay, so there is a quantum algorithm for this and this is this other paper from 95. Peter Shor. So he thought of this algorithm that solves the DLP in polynomial time. Okay, now remember our big N we took about two to the small n. And this Shor's algorithm only takes small n to the cube? And I mean, if N is a hundred hundred cube, it's not that big. And I can make a thousand by a thousand cube is still not that big. Okay. So there is a good algorithm that assumes the existence of a quantum computer. I mean as outlandish that might sound, but still this algorithm in theory breaks the DLP. Okay. So I don't know, maybe in 20 years or 30 years, 100 years. I don't know personally, but if there is a quantum computer eventually that somehow runs this thing, okay, DLP's broken, classically. So. Well, what to do? As I said, let's just try to come up with cryptography for which we don't know a quantum algorithm. Okay. Or for which we expect there won't be a quantum algorithm ever. There are a few candidates. Again, there's this zoo. Lattices, codes, this long word, and isogenies. Okay. Now what I want to tell you about is what is an isogeny, and how do I do key exchange with an isogeny? Okay. Because I know, it's a fancy word, but what does it mean? Okay. There was this other word that started with elliptic curve isogenies, so probably I should tell you about what is an elliptic curve or give you a reminder if you've seen this before. So I look at this equation in two variables and two constants, the variables X and Y, my constants are A and B. And the equation is Y squared is X cubed plus AX plus B. And now what I want to look at is all the solutions to this equation, all the possible pairs Y and X or X and Y. And of course, they're going to look different somehow for the different possible numbers that I can plug in for X and Y. And again, you might have guessed it, first of all, we're going to look at it over the decimal numbers and then later we want to consider this again over our finite field, okay, because we like we like this discreteness. And over R, a simple equation, I just chose some values for A and B, B I set to zero, A I set to 1, uh, A I set to zero, B I set to one. The solution set looks like this. And actually it extends infinitely far on the right side, up and down. Okay. So this is just somehow a snapshot of what the solution set looks like. But over my finite field, and I chose one with one hundred and one elements, it looks like the set of points. Okay. So elliptical curves look differently over different fields. But that's fine. That's fine. Okay. Now, quick reminder of why people like elliptic curves. So there is something called the point addition law. So I can take two points on this curve and I can somehow add them. Okay, but this is not really addition in the sense of numbers. There is somehow a law that I have to apply. And let me quickly show off how this is done. So how do I add two points on this curve? Well, you take these two points, you put a line through it, and then there is a law that says that if I put a line through two points, then it has, the line has to cut the curve from the third point. Okay. So I put the line through these two points. It cut the curve in the third point all the way up on the right. You know, what I'm going to do is I'm going to reflect the point down on the X axis. Okay. So I draw this other line, I reflect it down. And then what I define is that other, that I cut, this I define to be the sum of these two points. Okay. So. And that works. Okay. I can add points, I can subtract points. There will be the inverse. So this kind of like X like integers mod N when you only consider addition, kind of, kind of, it's not really the same, but you can also single out the special point O like beautiful O we call the origin, whatever that is. And this origin kind of acts like a zero. So if I add the origin to the point where I get the point again, or if I add the point and its inverse I get that point, I get zero. Okay. So there's something like a zero. And you can also multiply points, right. I mean what is multiplication, it's just repeated addition. So in brackets n, this is what I write for point multiplication, just add the point n times to itself. Okay. So there's nothing fancy going on here. So you can somehow add points. You can multiply points. That's pretty cool. And if you look closer, you can look at the special set here that I denoted E brackets, big N. And these are all the points on the curve such that if I multiplied this point for N it gives me zero. Okay. And this set for the mathematically inclined people among us I know say this is somehow the N-torsion of an elliptic curve, whatever that means. But if you're interested, you can look it up. And this set kind of acts like additive integers mod n - like two copies of it. Okay. And now this is where the term super singular comes from. One of the definitions. This is not the only definition, but this is one of them. If you look at the elliptic curve, not over the reals, okay, or whichever numbers, but over this finite fields. And if you look at the torsion, the P-torsion, then this behaves differently for different types of curves. Okay. The P-torsion is either empty, then we call the curve super singular; or it's just one copy of of integers mod P and then we call it ordinary. Okay. It's not really important to know what that means. It just means that there is a distinction for curves somehow that's somehow ingrained mathematically deep down there. And because this E N torsion is somehow two copies of of integers mod N, additive integers mod N, I can generate it by taking linear combinations of two points, say P and Q, and these are like the generators we saw earlier. Right. But these are not additive generators instead of somehow exponential generators. But it, everything behaves kind of similar. And now you can really use this to do cryptography already. If you wanted to write it. You can. You can somehow look at the DLP in that group, but there is the problem again that the DLP in there, there's Shor's algorithm again. Right. So even if you do cryptography in this group, you run into the same problem. OK, so we have to do a bit better. We have to search further. And this is where isogenies come on. Come into the play. So one way you can think of an isogeny is, remember how we found integers mod N by somehow dividing Z by all the N multiples. And you can do something similar with an elliptic curve. if you can somehow take part of this N-torsion and you can divide an elliptic curve by this. You can mod it out and it turns out this is mathematically well- defined and it gives you another elliptic curve. Okay. So I take a curve, E1, I take a part of my N-torsion. I divide elliptic curve E1 by G and I get another elliptic curve E2. And there's something else that comes along with this construction. And this is what we call the isogeny. This is a map. OK. Along with this construction comes a map from E1 to E2. And this map is what we call an isogeny. An isogeny is the map that takes us from one curve to another curve. And this map is kind of special because it behaves in a nice way and it plays nicely with the structure that's already ingrained in our curve. Namely, I can either add two points on my starting curve and send it through that map to the other curve. Or it can take two points on my starting curve. I can send it through the map and edit over there and it gives me the same thing. So this map behaves nicely with point addition. That's pretty nice, just as a side note. So this map is special. So this is just the remainder of what I said: Adding points on E1 and sending the result to E2 is the same as sending points to E2 and adding them there. So this map somehow plays nicely with my laws on my elliptic curve. Now I have to make a definition: In mathematics, the kernel of a map is the set of all the inputs to the map that are sent to zero. And we saw this origin O here that acted like zero. So the kernel of my isogeny, I'm just going to define as all the inputs to the isogeny that are sent to the zero on the other curve. And in written notation, it's the set of all P in E1 such that the map of P is 0. It turns out that this kernel for my isogeny, that I started out with somehow recovers this part of the end portion that I used to construct. So there's two ways now to think of an isogeny. So this is what we start with. We reconsidered E1 mod G and it gave us this map from E1 to E2. But if I start with this map from E1 to E2, we also find the G again. So there are two ways to represent this map. We can think of a subgroup - this G - or we can think of the map. And ultimately somehow there is a correspondence between the various subgroups for different N and isogenies that are somehow emanating from a curve. We can think of this link or the hairs on my head, they are going out and then they're going to reach other electric curves maybe. And these notions can be used interchangeably. So somehow there is a correspondence. And again, I can choose different ends. So some- how from one curve, I can have many outgoing isogenies that are different in a sense. And now the thing is in practice, we actually want to compute these maps. So right now, this is just general abstract nonsense. I didn't tell you anything of how to compute these things. I just told you there are some more correspondences. But I mean, what does that even mean? Right. It's useless if I can't use it in practice. And then there is another thing: You can compute these things, there are formulas, people have worked on this. But somehow the cost grows if I enlarge N. So really, in practice, for applications, I want to choose a small N. Maybe two or three - that would be pretty good. And now the thing is, it's the supersingular curves for which I can some- how control or choose the possible ends very very easily. So this is the reason why we reconsider supersingular curves. Now I can choose my prime to be of this form and then magically this is going to force 2 and 3 being possible. So this is the reason why we choose supersingular ones. There's some theory which is not interesting for you, but it's important for implementation. And there's a way basically for us to force the curve to have those isogenies that we like. But there is another important reason and this is the reason that actually makes it interesting for cryptography. So what I can do is: I start with an arbitrary curve, and this just might not be a supersingular one, just any curve and say I consider all the outgoing two isogenies if these are possible, 4 and 2. So there's going to be 1, 2 and 3. And then again, from E1, I can again consider all the outgoing isogenies, and so on and so forth. So what's going to happen here is: This is going to generate a graph, where the vertices of my graph are elliptic curves and the edges are isogenies. So somehow behind the scenes there is this graph hidden. Now, it turns out that if you do this for a supersingular elliptic curve - and I generated this yesterday for you, so this is one possible graph - I can remember which prime I took. But here you can see all the ellipses are ellipitic curves and all the edges between them are 2 isogenies. So this is an example of a supersingular 2-isogeny graph - okay, this looks pretty wild. I can do the same for N = 3 if it's possible, or is 5 and so on and so forth. There are many many graphs hidden. But why is the supersingular graph specific and important? Well, it turns out that somehow the supersingular one is connected, and it's what we call a Ramanujan graph. I'm going to explain this in a second. And as a bonus, for implementation purposes, it turns out that you can do all your implementation in arithmetics in the finite field with p^2 elements. This is nice. So I'm just gonna say that if you don't consider supersingular curves and you go along these graphs, then what's going to happen is that somehow this "field of definition", what we call it, could grow for you to be able to go further, but that would suck for implementation. But supersingular ones is nice so, F_p^2 is enough. So this is again, is good for implementation. So somehow magically many many things happen here that are benefiting us. And again, why is it nice that this is a Ramanujan graph? A Ramanujan graph has certain optimal expansion properties. This means that if I start from a random point in my fraph, and I take a random walk with some- how logarithmic steps of the total amount of vertices, then this will put me in a very uniform place in that graph. And this is is good for cryptography. Because you only need to take log many steps to somehow randomize yourself in that graph. And this is what this could look like. I started at that red ellipses over there. This was my starting point. And then I generated a few random walks, and the blue points are where I got placed. This might not prove anything, but it gives you an idea of how, some- how uniformly, it places me around that graph. So, it's good for cryptography, but there are other reasons, so supersingular elliptic curves somehow I can actually compute how many of these curves I will have in my graph. This is another reason to be looking at these things. Because if I don't even know how many curves are in my graph - well I can't really say anything about the security - but at least for supersingular ones, I can see they're roughly p/ 12 many. Okay, and then again, if I'd choose my p about n bits, well then I really know that my graph has about 2^n elements. And at least there I can see something about the cryptographic strength, right? I can make M big and then you can say: Oh yeah, you have this random graph, you take some n-length walks and n-length walks and then it places you randomly in there and the whole graph is about 2^n elements. And then I can say something about the expected runtime of algorithms. So this is another reason why we want to consider supersingular curves: Because I can tell you how many elements are in this graph. So a quick summary of what we saw, why this is nice. So what you get is a compact representation of an (l+1)-regular graph. And we saw examples, e.g. l = 2, l = 3. Bigger values are possible, but we don't even care about those because this is what gives us the fastest arithmetic such that we can work with F_p^2. This is nice, this keeps our implementation fast. I can tell you how many vertices are in the graph: about p/12. And again, such that the graph for mixing properties that are useful for cryptographic applications. So because I want to use this ultimately for cryptography. And again, that's what we said: If I choose an n-bit prime p, then the graph has about 2^n vertices - so exponentially many vertices. And it turns out that there are some hard problems that I can ask you to solve in this graph that don't have good quantum algorithms. So one hard problem is this: I take two super singular elliptic curves, so I just give you two random curves in this graph and ask you to find a nice arch in the path between those isognies, or three isogenies. And it turns out that this just doesn't have a good quantum algorithm. So classically, I mean the numbers are super important here, but classically the complexity is p, over the fourth root of p, and the best quantum algorithm is a bit better at it. I mean again, it's not super important what's there. What's important is that there is no polynomial time algorithm compare to ideal p that we started with. So if I make this p very large and your quantum computer, your hypothetical quantum computer, will probably not solve this. Okay, so that's cool. So how do we do key exchange? I start with a supersingular elliptic curve E, where I chose my prime p such that two and three isogenies are possible. And then Alice - earlier I remember she chose a random number a - but now Alice will choose a random subgroup A, and she will send E mod A to Bob. This amounts to Alice for computing the nice isogeny. And again, this is a very symmetrical key exchange, except that now Bob won't use the same generator but Bob will use the 3 isogenies. So Bob will choose a random subgroup B, and then he will compute E mod B and send this to Alice. And this is the picture: There's Alice, there's Bob. Alice chose A, Bob chooses B. Alice sends E mod A to Bob, Bob sends E mod B to Alice. And then how do they agree on a shared key? They will just mod out by their respective subgroups again. And it turns out that the elliptic curve that they find is going to be the same for both of them. Okay, so how does that work? Again, let's return to our graph: Say Alice and Bob agree on a black curve - the black curve on the left side. And then Alice will compute these red steps, which correspond to taking a subgroup. So Alice will compute these red steps for her secret subgroup and she will end up at the red curve in the upper right corner. And Bob will do the same. But now Bob is not in the 2-graph, but in the 3-graph - so this is the three graph. And the black curve that he started from in the 3-graph is down there. He will also select a random subgroup, compute the secret path and Bob will end up in the blue curve. Now Alice will send her red curve to Bob. And Bob, will send his blue curve to Alice. And then Alice will consider the blue curve in the 2-graph. So Alice starts from the blue curve that she got from Bob - and this is the position in the 2-graph. And again, she computes that same secret path and ends up in the green curve, which is up there. Bob got the red curve from Alice. So Bob has the red curve there. Again, he computes the path and then ends up at the green curve. And it turns out that the green curves here and there are the same. And this is going to be the shared key for them. This is SIDH. Okay. This is how you exchange a secret key using the supersingular isogeny graph. That's the whole magic. And again, let's compare these two things a bit: the DLP- based one and the SIDH one. So we had the square, Alice and Bob started in the upper left corner and again ended up in the lower right corner. And SIDH looks very similar: Alice and Bob start with this common curve E in the upper left corner. Again, Alice computes only horizontal arrows because she knows her secret group A, and Bob only computes the vertical arrows because only he knows his secret group B. And again, they both end up in the lower right corner, where they define the shared key. But now in this case, the shared key is not an element to the a^(ab), but elliptic curve. But again, there's a mathematical way to attach a unique number to it. So it's a solved problem to actually make some bytes out of this. And yeah, that's SIDH. That's everything. This is a nice example of a post-quantum cryptography scheme that we have today. And now let me finish with a quick conclusion. I showed you this "zoo": There are several candidates somehow for post-quantum cryptography. And among them are some schemes based on supersingular elliptic curve isogenies, and we've seen that we know some hard problems involving these isogenies that are hard for quantum computers, which makes this one possible scheme for a quantum computer world. And probably I should say that we don't envision a world here where we users like me or you are in possession of quantum computers. Probably, what we think about is that state actors are in positions of quantum computers. So this is even more important for us to be looking into these things. And what we saw was to perform a Diffie-Hellman-like key exchange using these isogenies. But - this is what I didn't tell you about in his talk - there are also schemes for signature-based isogenies, there is this scheme for key- encapsulation-based isogenies. So there are other possible candidates for other cryptographic building blocks based on isogenies and these hard problems. And if you're super interested about this, you can either ask me or come to our assembly and if you like reading scientific papers, papers about such isogenies and cryptography in general, you can find this on the eprint archive. So this is a web page where people post pre-prints about their papers and there's a huge collection about, among of them, isogeny papers. So if you're interested in this, this is the place to research. And with that, I would like to thank you all for your attention. applause Herald Angel: Is there any question? OK, I got the Signal Angel there, doing some Morse code? Microphone 1: Yes. Can you recommend any literature for the theoretical background? naehrwert: The theoretical background? There are a few papers that are nice. Okay. The question again was literature about theoretical background. And yes, there are a few papers that are giving some nice, even theoretically involved summaries about the background. And your best bet is to go to eprint and you enter 'isogenies' in the mask of search terms, or 'SIDH', and look at the papers that say, maybe, 'A Short Introduction to Isogenies' or something like that. I mean, you will find them if you search for them. I don't know them from the top of my head, but they're out there for sure. Yeah, and thanks for him - So there is a very recent paper by Craig Costello, also somewhat titled 'A Short Introduction', something like that. So this is also maybe a good source for you to look at. Herald Angel: Um, yeah, 'Isogenies for Beginners'. naehrwert: 'Isogenies for Beginners'. Thank you. audience laughing Microphone 2: Hello. Yeah. So you've used elleptic curve as an algebraic group, right, to compute these isogeny graphs. Why do you use elliptic curves - what's the properties of elliptical curves as a group? So, could you use any group to compute these graphs and could you use these as the basis for your scheme or your key exchange scheme? naehrwert: Okay, so the question was why use elliptical curves and the group structure that the impose to look at isogeny graphs involving elliptical curves and whether I could use other groups. And actually, there's a two-fold answer maybe. So if I go back - or actually let me go to my backup slide, which gives you SIDH in its full glory - you consider some extra information being sent, namely these generators from my group and actually the same commutative diagram for SIDH. You could, in theory, compute using another group as well, that has the proper subgroup structure, but the graph that you will find is probably not going to be interesting. I mean it's really somehow that Righello property that makes the graph interesting for cryptography. But yes, in theory, the SIDH commutative diagram you could also compute for other groups, yes. Microphone 2: OK. Microphone 3: Uh... How good are classical algorithms that tried to reverse that SIDH problem, because that will be the bound for how large your keys have to be, to be secure. naehrwert: Yes. So the question was: How good are classical algorithms? And again, I said, I think the runtime for those is squared of p. And this tells you how big you have to choose B. Microphone 3: And how confident are you that this really is hard for quantum computers as well? naehwert: Well, how confident am I that this is really hard for quantum computers? So first of all, cryptography is all about confidence, right? So someone proposes a problem, this problem gets crypto-analyzed. And if it's not broken after 40 years, then people will say, I'm pretty, pretty confident this is good. And maybe if the NSA doesn't tell you anything about it, or maybe if they don't have, you know, anything on it, then you can also see that you're confident in it. But I think this is really a question that only time can answer, right? Microphone 4: Yeah. Is it possible to prove that no polynomial-time algorithms for the isogenies problems can exist for a quantum computer? naehrwert: Yeah, that's a good question. How do you prove that no algorithm exists? This brings us into territories, like ... Yeah. I don't know. Yeah. No. Let's not do that. Microphone 1: Yeah. Good talk by the way. At the last slide you say that this is hard for a quantum [computer]. But that can't be true because we don't even know if any algorithm is hard for classic computers. Right? So, I'm guessing you're saying that intuitively it feels hard, which, you know, is the same intuition I have about e.g. factoring in. So, you mention there's multiple candidates for post-quantum cryptography, and they all intuitively feel hard somehow. Do you know if this specific candidate, would this be your horse in a race? Is there anything about this specific way that you think would be the best fit for post-quantum cryptography? naehrwert: Okay. Your opinion is very valid. Of course, we don't know if it's hard, right? This connects back to the other questions: How do you trust something like that? Again, people do crypto analysis for 40 years or whatever. And then you say, oh, no one found anything - it's probably hard, right? But it hasn't been an exact 40 years. You cannot say that. Indeed these things are relatively new. And personally, I'm not gonna, I don't know, believe in any of these things until some time passes. So my reason for looking into these things really is more a mathematical curiosity, because I think these things are beautiful. And the cryptography that arises from it is more of a side-effect for me personally. So I'm not going to put out any guesses on which of these things is actually going to win the PQ race or whatever. Microphone 2: (Yeah. I am.) You showed or said you think it's hard for the classical way and for the quantum cryptography way. I think I just read a paper last year about a combined way in classical and quantum cryptography combined, which outperforms either one of those ways. Do you think this could also be relevant or gonna make this one way to put in computable in polynomial time? naehrwert: Are you talking about an algorithm that somehow combines a classical step and a quantum step to break this? Microphone 2: Yes. naehwert: Yeah well, most algorithms that we say use a quantum computer involve a classical part anyways. If you think about Shor's algorithm, there's a classical part and a quantum computer part. So I'm not sure which algorithm you read about, but I'm sure that somehow all the quantum algorithms involve a classical part implicitly anyways. Herald: Signal Angel? Microphone 3: Yeah. Can you please name the mentioned contestants in the list 'Challenge-based Isogenies'? naehrwert: So there is SSIKE, I believe: supersingular isogeny key encapsulation, but actually I don't really follow the NIST thingy closely, so I actually couldn't even name all the names that are involved in it, but you can look it up on the NIST website and I believe somewhere there is also a classification of the contenders into this view. So they will tell you which contenders are based on lattices and which contenders are based on codes and which ones are somehow based on isogenies. But off the top of my head, actually, I don't even know. Sorry. Microphone 1: So if I got everything correctly, though, those isogenies are group homomorphisms between the elliptic curves and the factor group of the elliptic curve by g. And which has kernel g again. naehrwert: Yes. Microphone 1: And you said that finding the isogeny path in the graph is rather difficult. But wouldn't the real difficulty rather be finding the subgroups G - because a group homomorphism between the elliptic curve and the factor group with kernel g is simply the canonical protection. naehrtwert: Exactly. So I see you are mathematically trained, which is very nice and I appreciate that, this is great and I am very happy about that. And yeah, if you look at the slide actually, the secrets are these alphas and betas, which somehow determine the subgroup. And yes, finding those isogeny path is equivalent to finding the alpha, somehow, that generates this group. And as you said correctly, finding the isogeny path is somehow finding this group. But it's just restating the problem. But it's still hard somehow to find this group. Yeah. Microhone 1: All right. Thanks. naehrwert: Thank you. Very cool. Microphone 2: Yeah, thank you for the great talk. So, can you play this game a little bit further? I mean, can you choose higher-dimensional abelian varieties to make it even more secure? Or is it just absolutely inaccessible? I mean, from the computation perspective, the choice of field of definition is difficult, for example, so... naehrwert: Okay, so the question was on whether you can use higher-dimensional abelian varieties and maybe for the people who don't know what that means: You can attach a dimension to these things in the elliptic curves, somehow have a dimension 1 attached to them. And the question was, can you somehow look at dimension 2, dimension 3 or higher? And actually, back in the days when people were thinking about the DLP problem on the points of elliptic curves that I mentioned briefly, people had the idea of maybe using dimension 2 or dimension 3. But it turns out, that the DLP problem actually, at some point, gets easier in higher dimensions. So, classically if you look at the DLP, you somehow want to stay at dimension 2, but now, what you can do is, you can look at isogenies between dimension-2 and dimension-3 ones. And actually the problem that arises there - and this makes elliptical curves very special - is that we can compute isogenies rather efficiently for elliptical curves because of Velu's formulas. Okay. So this gives us a very direct means of computing D, but it actually gets hard as the dimension grows. For example, for dimension 2 already, the only isogenies that I am able to efficiently compute are 2- and 3-isogenies. So there are some packages out there that can compute higher ones, but only if my prime is very small and for dimension 3 and higher it gets even harder. And then there is another thing that comes into play. So dimension-2 varieties, they all arise from what we call hyperelliptic curves. But if we look at dimension-3s and higher, then sometimes you land at a point in your graph that does not come from a hyperelliptic curve anymore. So there is another complication. So I mean, I had a friend who was looking into genus-2 isogenies and it's possible to go there. But I don't know. I think personally this is more of a toy than something that's good in practice. Microphone 2: Can you use this scheme to implement a fully homomorphic encryption scheme? Or is it already? naehrwert: Uhhh... No. No. laughing naehrwert: Yeah, no fully homomorphic encryption is somehow a pipe dream, but I mean sometimes it's possible. So the idea is that you can add cipher texts and get the sum of the ciphered texts and have a second operation, namely you should be able to multiply ciphertexts and get the multiplication of two ciphertexts. But we didn't even talk about encryption. Microphone 2: Yeah. Another question: Is there any crypto primitive used in the isogeny approach that cannot be Stark- reduced to finding a hidden subgroup in an abelian group? naehrwert: Could you repeat the question, please? Microphone 2: Is there any crypto primitive used in the isogeny approach that cannot be Stark-reduced to finding a hidden subgroup in an abelian group? naehrwert: Okay. I think this question tries to connect back to the hidden shift problem or the hidden subgroup problem and Berg's algorithm. But I think I'm not able to answer that question now without talking to the person that actually asked it because it's a bit vague. So I'm sorry about that. Microphone 3: How do you send an elliptical over the wire? naehrwert: Yeah, maybe I should answer that actually. So we saw the parameterization of the curve that had these coefficients A and B. But what I didn't tell you is that to an elliptic curve you can actually attach what we call an invariant in mathematics and for an elliptical curve, this is called a j-invariant and it's a single integer which determines this elliptical curve uniquely. So if I want to send an elliptical curve, I can simply send you its j-invariant. And if you know the field of definition, you're going to be able to somehow recompute it just from the single value. So it's actually quite a compact representation which makes this also interesting. Yeah. Herald: I guess this is all. Thank you. applause postroll music subtitles created by c3subtitles.de in the year 2020. Join, and help us!