A Requiem for SIDH: Efficient algorithms for supersingular isogeny Diffie-Hellman
     Deirdre Connolly
     >> We are gonna be starting again in just 2, 3 minutes.
     [Standing by to begin]
     
     >> All right! Hello! Hello! Give 30 seconds to get everybody back in here. Pretty much ready to go. Good to see you all. Our next speaker is Deirdre Connolly. She has a number of presences online. Has her podcast, security cryptography whatever, which is a fantastic listen. A cohost, and kind of instigator, I don't know the full story how that came about.
     DEIRDRE: We all knew each from a Slack and we all said, we should do a podcast about security in the news. Happened three times and now for a year.
     ZEESHAN: It's a fantastic thing, and working for the Zcash Foundation. And her Twitter account is a good follow. You can Google her name and Twitter and it will come right up. And yeah, what we started talking about speakers, her name came up right away. Deirdre Connolly, take it away!
     [ Applause ]
     DEIRDRE: Hi. Sorry, we're starting late. I'm Deirdre. Today we are gathered here together in memory of SIDH, supersingular isogeny Diffie-Hellman. And they asked me, because it's Papers We Love, to talk about it, yes! Efficient algorithms for supersingular isogeny Diffie-Hellman. Between the talk request and today, SIDH, I'm wearing a lot more black than usual. And we will describe why this is a Requiem for SIDH and not it's just really cool. What's Diffie-Hellman? It's a way to establish a shared secret over a public channel between two parties who have never communicated before and have no shared secret information between them. Why do you want to do this? You want to do this if you like your HTTPS browser connection. If you like your VPN connection. If you like your WhatsApp sending encrypted messages with the signal protocol in the signal messenger. All of these cryptographic protocols use Diffie-Hellman in some way. They're slightly different, but all do the same thing to a degree. There are common parameters that everyone frees on, everyone, including your adversary can see. You do some secret stuff and then combine your secret stuff with your peer's public stuff, based on that are secret, and you're able to agree on a shared secret between the two of you and that's it.
     Based on everything that's public that your adversary, you and the other can see, and you can use that for keying material. Encrypt all of your web traffics using that secret material. Or use it to start ratcheting, or do one Diffie-Hellman per secret message you send and then ratchet it forward and do a Diffie-Hellman every time.
     For the past 20-ish years, going on 20 years, the way we have been doing Diffie-Hellman in modern cryptography is via elliptic curve with Diffie-Hellman. What's an elliptic curve? This is a polynomial of degree 3, Y squared equals X, this is the short form. There are several forms, but this is sort of the standard, you know, representation.
     Why do we like elliptic curves for Diffie-Hellman? We like elliptic curves for Diffie-Hellman because they give us efficient, short, and secure group laws for a bilin group. What's that? It's an algebraic secure that gives you from the communicative properties, distributed and associated properties. And we really like those things for something like Diffie-Hellman where the commutativity of the algebraic structure lets us swap things around, and share things in public and we get to come to agree on the same mathematical result at the end of the day. Why do we like elliptic curves for this? This is a polynomial. It's straightforward. Not all polynomials give you an algebraic group law out of the math.
     Elliptic curves do. Elliptic curves are practically just like the nicest way to do algebraic group law in regular math. It falls out of math in this very beautiful way.
     So, what do I mean about operating over an algebraic group? In point here is a solution to this polynomial. There's a X and Y value, and you can solve it and plot it. This is an elliptic curve plotted over the real numbers. For cryptography, we plot over a finite field and you will see that later. This is a point. For the curves we use for cryptography, we call this a group element. We are using an elliptic curve to create and do group arithmetic. So, a point is pretty much a group element. But I will get into the details of when it's not exactly a group element. So, what can we do with these points as group elements? We always to define a group have an element that is called the identity.
     And if we're representing our group law as addition, basically, which we do for elliptic curves. It's adding a number to zero. Add N to zero, you get N. In this case, you add P, a point, a solution on the elliptic to zero, you get an identity. And you can invert, take the inverse of P and add it to P and you get zero, the identity. You can also add P to itself several number of times and you will get another solution on the curve. Sometimes it will be zero and sometimes it will be something else. Depending.
     So, the way that we do this is we, instead of -- the way that we do this to add a point to itself is we take the tangent at curve at the point. Find where it intersects somewhere else on the curve and it must, by definition, intersect somewhere else on this curve. And then the actual solution to what is the value, the solution on the curve, of a point added to itself is that intersection point reflected over the X axis and then find the over place where that reflection is on the curve. And that's your solution.
     So, that gives us 2P equals R, basically. To be clear, you can add points to each other. So, you can add the same point to itself several number of times. You can't multiply points together. So, you can't do P times P. You can do P plus P. But when you add a point to itself N times, we call that scalar multiplication by N. So, this is what you do when you are, you know, doing regular multiplication. You're adding, if you're doing 3 times 4 with the integers, you are adding 4 plus 4 plus 4. This is similar to what we're doing and where the scalar multiplication comes from. And you have a point and add it to itself L times and you come around to the identity, that number, L, is called the order of P. And P, as generating a whole group, a subgroup -- [Audio stopped] -- is a generator of a group.
     Okay. So, that's -- now you know everything about elliptic curves. So, how do we use this for Diffie-Hellman? What we do is we set up our parameters. Everyone knows this, including the people you're trying to do Diffie-Hellman with and any adversary. Pick a curve, a specific equation, pick a point, everyone knows and agrees to start with. It just makes things easier. All of this is arithmetic mod a prime P. Picking a prime P and having it nice for your elliptic curve is a science and an artist. But all of this is arithmetic via a mod P. All of the solutions wrap around the prime P. We love primes in cryptography.
     So, you generate a number, mod P, each, Alice and Bob, generate a mod P. Do a scalar of your secret value via your generator point and gives you a point. Alice has a new point, capital A. Bob has a new point, capital B. And these a often called public keys or, you know, whatever. So, A sends -- Alice sends her public point A to Bob. And Bob sends their public point B to Alice. Alice does a scalar maul of her secret A, times Bob's point, B, and Bob does a secret scalar B times Alice's public point, big A. And by the magic of commutativity, they arrive at a new point that they arrived at. And only they, because they note secrets, combined with the public values they have shared, only they know this secret. This is -- reduces to the hard problem of trying to find that secret as a fundamental computational problem in cryptography. For over 30 years now, this has been a efficient, hard-to-break way to do cryptography, do Diffie-Hellman, do a whole bunch of stuff. And we have built many, many cryptographic protocols on it.
     So, why am I talking about this? Well, we have a problem. Which is that these are theoretically completely broken. If we get a large, efficient quantum computer online to run certain attacks against these protocols. Elliptic curves, finite field, Diffie-Hellman, which proceeded elliptic Diffie-Hellman. All are broken by Shor's algorithm. In 1995, '96. It requires a large proportionally -- you need as many logical qubits as secret bits in the discrete law of the secret. Logical, efficient. All of these terms are implementation details are just an engineering problem that they have been trying to solve for 20 plus years now. And they will probably be continuing to solve it for a while. But they are getting better. There are quantum computers by Google, IBM, other organizations that are getting bigger and better steadily and more efficient. And more correct.
     And it takes a long time to standardize and deploy new cryptographic systems. Especially when it's based on new mathematical problems. For example, elliptic curves were originally published in about 1985 by Koblitz and Miller and a couple other people. It took -- I'm conservatively saying 15, 20 years from when it was originally published in a paper to really getting it deployed at scale in the web, in VPNs, in cryptography. It takes a long time. So, when cryptographers and people who care about security saw this threat, they were -- they were like, we need to get started. Because we have to figure out cryptographic algorithms and mathematical problems that are resistant to these types of attacks, this whole class of attack. And we have to figure out how to build things with that. And we have to standardize them. And we have to deploy them.
     That takes a long time. So, people have been trying to find quantum-resistant problems to build stuff on. So, does that mean we're screwed with elliptic curves? These nice things with lovely mathematical and algebraic properties that let us build stuff with them? Are we done? We have 25 plus years of using them for cryptography. And many, many, many more years of lovely mathematics behind elliptic curve cryptography that would be a shame to throw away. And the answer is no. Otherwise I wouldn't be talking.
     Moving from finite field Diffie-Hellman to elliptic curve went from something with a little less structure to more structure. Instead of numbers mod P. We went to elliptic curves, polynomials and used them to do algebraic groups instead of just the integers. What if we used the curves as this set of things that we're operating over. As opposed to points on a single curve and operating over those? Does that give us anything? And the answer is yes. So, in theory, if I said, here is a starting point -- a starting curve that we all agree on. And then I generated a new curve and it's over here. Find me the path between these two things in this connected graph.
     And kind of instinctually, you would just be like, that looked hard. That's a path finding problem in this graph. And the answer is yes, this is a supersingular isogeny graph over a point parameter set. This is a considered a computationally hard problem for classical attacks and quantum attacks. And even after everything I will tell you, this is a hard problem and we're still building new cryptography on it. And so, this kind of insight about the nice properties of these sort of -- if you take all of these nodes in this graph as hand-wavy elliptic curves and try to traverse maps between them in this interconnected graph, that is considered a hard problem. Like just full stop. And that was kind of the idea to revive elliptic curves in a post-quantum world.
     So, those little connections, those edges in that graph, these are isogenies. Which is a little weird term. It's fun to say. Isogenies. What is an isogeny? So, an isogeny is very similar to that scalar multiplication that I talked about earlier. But it's kind of a more -- the more abstract version, the kind of generalized version of scalar multiplication. A isogeny is a map from one elliptic curve to another elliptic curve that is uniquely defined by a subgroup of points on that starting curve. Your pre-image curve. When you have that map, you can take all the points on that starting curve, shove them through this function, this rational map. That's unique defined by this isogeny. And you will get a point on the destination curve. Including the starting curve maps to the identity on the destination curve. So, this is a little bit of an example. This is a toy example. You can kind of see -- this is a very, very small degree map. You can -- like, you can literally write it all down right there. Between a real curve, but plotted over a very small prime field as opposed to cryptography will use the exact same curve over a very, very large prime field. And generates the map to the new curve.
     You can kind of see it's preserving symmetry, it's preserving kind of relations between points. But not exactly. This is a group homomorphism. But it's not an isomorphism. It's not translating every point to every point. It's surjective between the two groups. This is some fun stuff. It turns out, if we pick our parameters correctly, you get cryptographically-secure isogenies that are 2 to the 372 degrees and you can't write it all down. There is these nice formulas that let you plug in all of those points in that generator group, that group that uniquely defines that isogeny. And you do like the sigma and add them all up.
     And you can crunch through them all and get a cryptographically-secure rational map, write down your isogeny map, to get something like this, but it's very, very slow. So, if you want to use this for cryptography, you can do it, but it's not efficient. And we really need things to be efficient to deploy them in the real world. What you do instead is use this nice composability property of isogenies and you break down that large degree isogeny map into lots and lots and lots of small degree isogenies like that one that I just showed on the white slide. And you just pipe them through. It's like a function -- oops -- and it's just like a function that you put the input in and the output in, output out, and you feed that output to a new function call and you put that -- chain them all together like a daisy chain. And that results in the same rational map, the high degree one. But it's much, much, much more efficient to compute it. So, this is what we do in real like implementing these algorithms in the real world for elliptic curve isogenies. And this is the same as walking in a graph between these two degree isogenies, these little, between these elliptic curves.
     So, this is basically what it looks like. Kind of like that toy example again, where you will be walking between the same nodes, between two parties. Alice on one side will be walking in the two degree isogeny graph, every node has three edges coming out of it. And Bob will be walking between the same set of elliptic curves as nodes, but he will be walking in the three isogeny graph, with four edges coming out of it. And then they will exchange some public information. And then they will, quote, unquote, do their walk to the other curve. From the other curve that their peer has shared. And then vice versa. And they will come to an agreement. They will find each other somewhere in this graph.
     And we can use this for Diffie-Hellman. This brings us to SIDH, supersingular isogeny Diffie-Hellman. Updated in 2015. This is Diffie-Hellman at a high-level. You have a public-starting curve kind of like we had at the beginning. Each party will generate a secret generator point for the subgroup that uniquely defines their secret isogeny. So, with that's what this brackets are A and brackets are B is saying. We're generating a secret point. That secret point generates a subgroup on E. And that subgroup uniquely defines that secret isogeny, Alice, it's by A, Bob, it's by B. We push our elliptic curve, our public elliptic curve through our secret isogeny to get a new elliptic curve. So, Alice has EA and Bob has EB. They exchange them. On Alice's side, she quote, unquote, applies her secret isogeny to walk, quote, unquote, from Bob's public curve that he just shared with her to a new point. And what she's actually doing is trying to take the generator point, the secret generator point, that she used for her secret isogeny and apply it under Bob's secret isogeny and I'll explain how we actually do this in a map later. And she tries to do that walk from Bob's public EB. And they both come to a new final elliptic curve. The shared secret elliptic curve.
     But one thing that's kind of funny about this, it's not the same exact polynomial on each side. If you write down the coefficients of each elliptic curve as a polynomial, they'll be different, probably. Not always, but probably. But you can just plug those coefficients into this little formula and you can get the J invariant. The J invariant basically means that these curves are the same. They are isomorphic. So, that isogeny map diagram that I showed you before, it's even more the same than that. They are the same curve, quote, unquote, up to isomorphism. And that J invariant is literally just a number, and that is your shared secret. So, that's how you're able to come to an agreement on these curves.
     Okay. I'm gonna get into the nitty gritty of what you use. Elliptic curve. This is a supersingular elliptic curve defined over a quadratic extension field. Quadratic extension field, everything is over a prime, except it's a tuple primes. You don't worry about that, we do it because it's more secure for SIDH. The public parameters include PA and QA, Alice's generator points, basic life. And Bob has his generator points. They will be used to help gin rate my secret value.
     So, Bob, on his side, will pick some random scalars, M and N, and multiply M by PB and NQB and add the results and have a new point. And that point is the generator of the subgroup over E. It's the subgroup of E, that public curve that everybody knows.
     And that uniquely defines their secret isogeny map. And shove the public curve through their secret isogeny map and get their public key, ED, the new curve. But that's not all they do for SIDH. They have the public curve, EB for Bob, their public key. But they also have Alice's generator points, PA and QA. Under the secret isogeny, under Bob's secret isogeny 5B. They call these, these auxiliary points. This was the key insight that allowed SIDH to happen because SIDH was only motivated when isogeny Diffie-Hellman was over on the other hand curves like in ordinary cryptography today. There was an attack found that showed it was vulnerable to a sub-exponential quantum attack that leveraged the structure of the endomorphism ring of ordinary curves. It's a little bit more algebraic structure about the elliptic curves when they are ordinary. Because it is commutative. They were able to use that to launch these attacks. These are other elliptic curves, supersingular curves, it's not commutative. But the lack of that, meant you couldn't just share elliptic curves. You needed that commutativity to come do that agreement. Because that's a sign, a signal part of Diffie-Hellman. These auxiliary points helped solve that issue. And this is how.
     So, Bob receives Alice's public key. That includes Alice's secret isogeny applied to the base points that Bob used to generate his secret. And then Bob applies his secret scalars, M and N to Alice's secret isogeny to the base points he used to generate his secret. And because these isogeny maps compose nicely and have the associative and distributive properties that we really like, this thing that you can do with these auxiliary points is the same as if Alice somehow had direct access to the generator point that Bob used to generate his secret isogeny and passed it through her secret isogeny.
     The math just falls out nicely. And it just works. And you're able to agree, again, and get that commutativity that you need for Diffie-Hellman on a shared secret elliptic curve with the encrypted contributory behavior from Alice and Bob's secret values and you're able to agree on the same shared secret that is based on both of their secrets that they generated.
     Yay! It's very beautiful. And like when I realized that this is how that worked, it was just -- I love SIDH and I love isogeny because this math, it just kind of falls out and it's very beautiful, I think.
     So, through earlier this year, this was -- this scheme, these problems, that is auxiliary points were considered secure. The best known quantum attack was proportional to the prime to the one sixth. The best known classical attack was proportional to the prime and one-fourth. But this doesn't even include between when SIDH was published and some of the most recent parameters that people are considering for the post-quantum cryptography competition. Some parameters were picked that were considered middle of the road. Not cutting too close to the edge. They're not too conservative. They were right in the middle. More crypto analysis were showing that was too conservative. That there was more analysis in the past few years that showed that SIDH in particular was stronger than we originally thought. We were able to bring parameter sizes down by maintaining the security level. It went faster, all these nice things. We were getting more and more confidence in SIDH. And isogeny problems in general over the past few years.
     But... isogeny crypto has been considered very slow for a very long time. It was first proposed in some form in like 1996. There was a hash function proposed in 2006. SIDH was proposed in 2011. And updated in 2015. And that whole time it was considered very promising. Everyone was very happy to have -- to make sure that elliptic curves didn't die. They were happy to have a completely separate mathematical problem to base cryptography on. Because we wanted diversity, we didn't want all our eggs in one basket like we had. Because they all turned out to be vulnerable in the same way. And the public keys and the public values that we had to share around or not wire were very small. They were the smallest. That was very, very attractive. But they were slow. These isogeny computations, everything over FP squared, they were just slow.
     So, someone tried to make it faster. So, this is the paper I love. This is efficient algorithms for supersingular isogeny Diffie-Hellman by Costello, Longa, Naehrig and research. Published in 2015. And basically, they said I wanted to go fast. But I want to go fast in a cryptographically-secure software way. They did it. They implemented this. They took all the tips and tricks that we learned from about 25 years of implementing elliptic curve cryptography and algorithms in the -- in regular software and they applied it to SIDH in particular. And so, they were able to get almost a three times speed up over the next-best implementation. And not just that, they did it all in a constant-time way. In a side-channel resistant way. In a cache-timing attack way. And they were able to do it to get compression for your public keys. So, you even got smaller public keys than the already very, very, very small public keys if you wanted it. So, here's some of the stuff that they did. Which is they took well -- none of this is like groundbreaking. It's just that they did it for all SIDH. And it all adds up. One of the things that's nice to do when you're implementing elliptic curve cryptography is not to use those coordinate systems that I showed you earlier. But to go into a projective coordinate system and one of those is the Montgomery Projective Coordinate System. Because it lets you do stuff faster. And that also lets you, if you're doing it in that sort of curve model, it also gives you access to the Montgomery ladder. If anyone has heard of curve -- signatures, using the Montgomery ladder is attractive. It lets you have a fast, correct, and constant time implementation of scalar multiplication. And you're using that all over SIDH. That's a win. Projective coordinates are a win. Avoiding inversions in the group and inversions in the field until the very last minute. Inversions are very expensive. Save those to the last minute, you go even faster. All this stuff. And then it's not just the scalar models, not just the classic stuff, they generated a new secret isogeny and shoving points and curves through them. They did that over Montgomery as well.
     The other thing that they did is they picked new params that have nice form that let you do these compression tricks even faster. They picked a nicer generator points. Those PA, QA, PB, PB, QB in a nice way so you have fewer scalar multiplications to be done. Related in a certain way, instead of N times P and N times Q, you do one scalar mole and that gives you what you need that you previously had to do more than one previously.
     All this is online. This is the implementation that most isogeny researchers have been pointing to. And building off of for 6 years now. Because it's fast, it's constant time. It's C, which is, you know, people still write C for some reason. And it's pretty good. It is a very tightly-knit together implementation of SIDH. It's not a general isogeny cryptography library. But it's very, very useful. And everyone can learn a little bit of something from that code.
     Now I told you about those auxiliary points, right? So, almost immediately -- not immediately -- but almost immediately after SIDH was published, people looked at those auxiliary points that are in the protocol and they were like, uh, are you giving too much information away? People were like, show me an attack. Show me an attack where I'm giving too much information away about my secret values.
     There was an attack. We really like using Diffie-Hellman in static settings. For example, your signal protocol, signal protocol, WhatsApp, Signal, messenger, you have a long-term key pair. You have an ID key pair. You have a lot of key pairs, but you have a long-term one. You do Diffie-Hellman with that over and over, a triple Diffie-Hellman when you start a new conversation with a new person. And you keep that long-term Diffie-Hellman key pair for a long time. Unless you throw it away and you have to reset all your conversations and stuff like that. We thought you could do this with SIDH. Turns out that you can't. Those torsion points, those public auxiliary points, were leveraged in a active adaptive attack when you use a long-term static SIDH key pair. So, we basically told everyone, like, ah, and part of the reason that we -- this was kind of considered game over for static SIDH is that we don't have reliable, efficient ways of doing public key validation. They're kind of -- they kind of suck. We have better ones now. But they're slow and they kind of take away all the efficiency that you would get. So, we basically had to tell people, all right. You can't use it for static settings. You can use it for ephemeral. You can use it for ephemeral stuff, for VPNs, for HTTPS, for TLS. You can use it in a lot of ephemeral settings. You can't use it for static. That sucked.
     More stuff. More attacks that showed if you picked your parameters wrong, if you had imbalanced parameters, if you did -- set up these things in the wrong way, you leveraged the auxiliary points to leverage an attack. But we're just sort of like, oh, okay. Is that it? Like we've had years and years of -- especially in the '90s -- of like we had to learn the lessons of how not to pick elliptic curves for regular elliptic curve crypto. This felt kind of like that. We're going through the growing pains of figuring out how not to pick parameters. And especially parameters they mentioned for the efficient algorithms paper for Microsoft Research. Their parameters stood up. Yeah, we figured that out. Those are standing up, they are not vulnerable to the auxiliary point attacks. Okay. This seems fine. This seems like growing pains. But this seems fine.
     [ Laughter ]
     Um... we thought it was fine. We were quite -- we were quite confident. The NIST competition had picked its round 3 results. And they had moved the only isogeny-based one, which is based on SIDH called SIKE. SIKE was taking the no longer secure and static setting SIDH and turning it into a static setting called SIKE. You have to tweak it a little bit. We were very happy. We were sort of, this looks nice. And we were moving forward.
     August 5th, someone drops this paper on ePrint. The main place where you drop papers that have not been reviewed but have been vetted by a human to be like, this is about cryptography. And I was in Vegas for DefCon and a bunch of other stuff. Please, please don't. I'm trying to have a nice time. Please stop. And this -- and people looked at this and they're like, ah, this looks really bad. This looks really, really bad. The caveat in this paper was, oh, we need to know this information about the starting curve. We need to know the information about the endomorphism about the starting curve. Okay. This is bad. But we have work ongoing about how to pick a starting curve with an unknown endomorphism rank. We have to pick new parameters. But okay. It's a very, very serious wound. But it's not dead yet. And then this came out three days later. And as you can see, arbitrary starting curve. We're just like, ah, ha. And it's -- these two papers had the similar idea. But one was saying, like, oh, we can get most of the way there. Even if you have -- it doesn't even matter what starting curve it is. We don't have to know as much information. The first one came out first and had a full attack. And this one was sort of halfway there. But it had this other side of it, where we're just like, does this mean that like all of them are broken no matter what starting curve we pick? And the people I was talking to were basically like, not quite. But it still doesn't look good.
     Okay. Okay. And then this one came out. [Audio stopped] --
     On the largest parameter set available and it cracked in an hour. It was supposed to be the Spinal Tap, you know, it goes up to 11 parameter set that NSA was going to recommend if they ever deployed SIDH. Broke it in an hour. It's dead. So, this is kind of the first attack. And this is -- I -- I'm only gonna hand wave this because it involves higher dimensional varieties that I did not understand when these papers came out. I'm going to hand wave this very briefly. The idea is that when you're doing your walk in the isogeny graph, that's your secret. You can just start with guessing. If you're an attacker, and you have someone's public key, you have all the public parameters, you can just start at the starting curve that everyone starts at and you just start guessing. But what you want, is, because if you're Bob. When you -- when you go to your first hop in the graph. There's only three options for you. You just have to figure out which option is the right way that you're going. And then you only have to make about, I don't know, 250 hops in that large parameter set. You need an Oracle to tell you if you're on the right path. If the guess that you're making is correct. And it turns out the insight, it was not just staying in this genus 1 setting. But to go to a higher dimensional algebraic setting -- or -- setting. What it was, you can multiply elliptic curves together. This is a thing you can do. Not points on curves. But curves themselves as like a whole group, as a whole algebraic variety. There was a theorem, it was just sitting there for 20 years. And people just didn't note it that it was useful in this way. That says with overwhelming probability, if you try to create a higher dimensional isogeny map between elliptic curves and you create an isogeny map and where do you land? With overwhelming probability, you are not gonna land on another multiplication of two elliptic curves. You are with overwhelming probability gonna land on this thing which is a Jacobian, a boolean visitor, it's gobbledygook. The important thing, if you land -- if you take an isogeny map from two elliptic curves that you just guessed. You're guessing these multiplications from where you are in your attack, and you create a higher dimensional isogeny map and you do land on a -- another product of elliptic curves, you are with high probability correct.
     Like, that is the high probability like you are on the right track. That is your Oracle. So, what that means is that if you multiply two elliptic curves together and generate a secret isogeny and then you do land on another multiplication of elliptic curves together. You are, when you go back down to where the base level that we have been operating on the whole time, you are in fact generating the correct next hop between an elliptic curve to the next elliptic curve. And that's it. And the way that you make your guess, the way that you generate these elliptic curves and say, oh, I'm trying to generate an isogeny. Where am I going? Is this anything? You need those torsion points. And then that's it.
     And you just run this for an hour. You just kind of do some informed guesses. And this sort of map that was just sitting there for over 20 years just lets you figure out if you are -- if you're doing the correct guesses from curve to curve to curve. And that's it. You're done. It's broken.
     There's a good talk from -- I think it's -- I think it's Decru, you can go on YouTube and just be like -- what's the name of the paper -- yeah. Efficient key recovery attack on SIDH. Thomas Decru. He's presented this several times in the past few weeks. Everyone is like, oh, my god, what did you do? And this paper is online. If you will to go into higher dimensional math, higher varieties, it melts my brain a little bit. But it's cool if you want more details on that. Of so, I was -- Luca was very funny. Because Luca was on holiday when this happened. And he just went on Twitter and he was like, this looks really bad. I'm on holiday. I'll tell you more about it when I come back. I'm just like... goals. Like, no matter what is going on in your career or your life or whatever, like if you're on holiday, like you finish your holiday. And deal with it when you come back.
     So, what does this mean? Does it had mean isogeny cryptography is dead? No. It does not mean that isogeny cryptography is dead. It means that SIDH, the protocol that uses these auxiliary points to finish the Diffie-Hellman commutativity program, that is dead. These are assumptions based on isogeny cryptography and where they stand. This is from -- IsSIKEBrokenYet.gitHub.io, set up by Luca and some other people.
     These -- all the ones with SIDH in their name -- they are hella dead. They are broken. These are not. These are all the problems that basically depend on that isogeny graph that I showed you and like that's it. Those things are still considered computationally hard and we don't have any well-known, good attacks, efficient attacks against them. Quantum or classical. So, isogenies are not dead. SIDH is hella dead. And these were the schemes that were built on those computational assumptions. As you can see, SIDH, dead. SIKE, dead. This other one, elliptic curves, dead. CSIDH is a different beast. Doesn't use the same way. This is a signing algorithm, this is knowledge that you can do -- this one's dead for a different reason. These runs are not dead. And this does not include a sighting algorithm that I'm very excited about because it's both very efficient in size and there have been multiple improvements in efficiency of computation in the past few years. Sealine are not dead, the auxiliary points are not part of the scheme.
     RIP SIDH. We hardly knew ye. This was a big bummer. Because SIDH in particular that paper, the efficient algorithms paper from Microsoft, was like part of really getting me into cryptography as a career and as a field. Because I saw this protocol. And I was just like, what is this weird math stuff? Because I already knew elliptic curves. Oh, no, the thing that I like is broken. I'm sad. No, it's not broken. You just have to throw a bunch more math on top of it and you can do stuff with it. This is amazing. And then that paper made it real. Instead of something that's esoteric and weird and off in its own corner, but not realistic. The efficient algorithms paper made it real, made it fast, something you could deploy. It was software, they proved you could implement it securely and it's not just full of foot guns that make it hard to do in a secure, side channel-resistant way. It was fast. When it just got brutally killed in a week in August, I was really bummed. I was really bummed.
     But, you know, it was a great little crypto system while it lasted. Were you a good crypto system? No. For a while... you were the best. That's it.
     That's it.
     [ Applause ]
     ZEESHAN: Thank you so much. That was fantastic. All right. We are now breaking for lunch for an hour. A couple notes on that. The way to do that is that the food trucks are behind the registration for Strange Loop. You're gonna go back over to the main part of the area and head up the stairs, outside. You're on your own for paying for that, if that's a problem or if you have an issue with that or need something, please talk to the organizers. You have probably seen us around. raise your hands, organizers. A couple of us around. Yeah, we will be back here just after 1:00 for our next set of speakers. Thank you!