Are the isogenies kaput?! There’s a new attack that breaks all the known parameter sets for SIDH/SIKE, so Steven Galbraith helps explain where the hell this came from, and where isogeny crypto goes from here.
This rough transcript has not been edited and may have errors.
Deirdre: Hello, welcome to security cryptography, whatever. I’m Deirdre.
Thomas: I’m not qualified to be on this podcast.
Deirdre: Yes, you are.
Thomas: I’m Thomas.
Deirdre: and today is not quite an emergency pod, but it’s a pretty special pod with our special guest Professor Steven Galbraith. Hi Steven.
Steven: Hey guys. Thanks for having me on your show.
Deirdre: Thank you for attending. This is a bit of a short notice scheduling and we’re all in different parts of the world.
We’re here because this is a bit of a day of grieving for, one of the best well known, highest attention isogeny-based, theoretically quantum secure, crypto schemes, SIDH: supersingular isogeny diffie-hellman. There’s been a new attack published, a well, preliminary writeup of an attack, by Wouter Castryck and Decru.
And it looks to be a classical attack that fully breaks the SIDH construction, uh, in polynomial time. And by polynomial time: there is a Python script that broke the highest security parameter set, and I ran it on my M1 MacBook in 20 minutes, like an hour ago. um, Steven, you have done a lot of work in this area, both attacking and constructing isogeny based, uh, crypto systems.
Can you give us a quick overview of SIDH, and then we can get into this attack and why it’s so devastating.
Steven: Yeah. So we are talking about post quantum cryptography here. So we’ve got classical, um, elliptic curve cryptography, which has, has been used all the time and at R. And things like that. And one of the problems is that quantum computers would, uh, solve the factoring problem, solve tic curve, discrete logs.
So there’s a lot of interest in new ideas, news, new kinds of schemes that we can use for cryptography, but would hopefully be secure against a quantum attack with a quantum computer. And the other important thing to say about post quantum crypto is we’re talking about stuff that, that you can implement and run right now on today’s hardware and on the internet, doesn’t require, um, new technology to, to, to work. So we’re looking for things that we can still use on our phone. Um, but hopefully is secure against an attacker with a quantum computer,
Deirdre: right.
Steven: and there are various types of post quantum crypto, and one of the most popular is lattices.
And that’s great. I think lattices are awesome, but I also really love elliptic curves and the, the great thing about isogeny crypto. Very closely related to elliptic curve crypto. So it’s not the same because if it was the same, it would be broken, um, by Shor’s algorithm. So it’s a kind of post quantum alternative to elliptic curve cryptography. And for people who know what Diffie-Hellman is, it’s really close to Diffie-Hellman in some sense. And, um, that makes it very beautiful, very elegant, and very appealing. And it’s been, it was, so this, this idea really came out, um, by Jao and De Feo in, I guess, 2011 or something. It’s only about 10 years old and, uh, Uh, since certainly in the last five years, it’s been a very, very active area of research.
Deirdre: Mm. so to overview the protocol, as opposed to other isogeny based protocols, which was a distinction we, we will get into after we talk about the attack, basically how you do SIDH as it’s been constructed, and if you go look up the NIST post quantum,, contest competition, whatever you wanna call it.
Um, it’ll look similar, but not exactly the same, cuz they, they construct it into what they call SIKE. Uh, the public parameters include a starting elliptic curve. Some points that are on that curve. And these are all using a, a prime to define the prime, the prime order field that they operate. Well, the prime order extension field that they operate over.
Um, and then one party will generate a new curve and some points, and those points are on the new curve and they are images of some of those base parameters, under their secret isogeny that they have constructed. And then the other party will do the same. But for these other different points that they operate over, they operate at, they have generate a different new curve and different new points that are on that curve and they exchange them.
Those are their public keys. They exchange them. And then you finish your Diffie-Hellman, by using your other party’, public points and public curve, and try to apply your secret isogeny to their points and curve and vice versa. And you’ll eventually come to the agreement of a new elliptic curve and you can take the J in variant of that elliptic curve.
And that is your shared secret.
so,
that’s yeah, hop in.
Thomas: So right off the bat here, like the distinction between, and just I’m asking questions and, and playing dumb, cuz I am dumb on this topic. Right. But right off the bat in, in like kind of conventional elliptic curve cryptography, we fix a curve, we just have a single curve. Right. So like we all, we’re all using curve25519, right?
We’re not coming up with curves on the fly, but in isogeny crypto, we are in a sense coming up with curves. On the fly. Right.
Deirdre: yeah.
Thomas: So I watched the, uh, I watched Costello’s tutorial, like the, the broadcast he did for, um, for Microsoft. And I kind of worked my way through the, the tutorial paper. So like, is it, is it true that like, in sort of the same sense we’re in elliptic, in conventional elliptic curve, we have like a base point, um, in, in SIDH or, or SIKE, whatever SIKE is just an instantiation of Right? It’s like the package version of it for. For right. But we sort of have a base curve instead of a base point.
Deirdre: Yes. Um,
Thomas: And then we have, I, I, yeah. And then we have isogenies which like, and isogeny is kind of a general like kind of, if you’re not a mathematician blows your head off kind of concept, but here isogenies are kind of straightforward formulas that we’re applying to points on curves.
Am I crazy? You’re I can’t tell if you’re nodding or you’re simultaneous Deirdre is simultaneously nodding and shaking your head.
Steven: yeah. I mean, they they’re, they’re, they’re exactly. They, they functions that map a curve to another curve and they map points to points. Um, Yep.
Thomas: And so like, we, we can kind of, we start with this like base curve, right. And then, and you, you have to kind of explain the math to me here, but like you can, you can derive from that base curve kind of a constellation of related curves, um, where we apply these isogeny formulas to take, you know, some value with a secret mixed into it and hop from curve to curve in that constellation of curves and you’re Alice and I’m Bob and Alice is gonna wind up on some star in this constellation, and Bob’s gonna wind up on some totally different star in this constellation. And then somehow we’re gonna do some kind of sharing thing where we can share public information and land on the same third different star, fourth different star, or
Deirdre: Yeah,
Steven: And that’s the, that’s the, the hard thing it’s easy to go off in random directions. Um, the hard thing is to make sure you, you end up at the same place. And if, if, if people who know D Hellman, you know, Alice can compute G^a Bob can compute G^b. And the key point is they can both end up at G^ab.
and so you’re looking for the, you’re looking. Some analog of that, where you, where Alice is taking some, some arrow or some function to some curve, and Bob’s taking a function to another curve. And, but, but they need to, you need to sort of agree and end up with a kind of a, it’s like a square. We think of these things as squares and you, we want to get to that corner, the kind of opposite corner, and you need to make sure you’re both going to the same place.
And that’s why you can’t just get away with sending the curve. An SIDH you have to send these extra points as well, which is the. Which is a real pain in the neck and the cause of all our problems are the fact that Alice and Bob are not just exchanging an elliptic curve. They’re exchanging an elliptic curve and a pair of points.
Deirdre: yes. And the original constructions were over "ordinary curves". I’m doing air quotes on the ordinary curves because those are the curves we’re used to in classical elliptic curve crypto. And they were found to be weak against an attack. And so the construction moved to the supersingular curves.
So that’s the S in SIDH. However, when we moved to SIDH we became, uh, secure against this certain class of attack, but we lost that commutativity so that we, once upon a time, we were just able to use these ordinary curves. And then we would’ve be able to complete the Diffie-Hellman square with just those curves.
But we lost that and adding these auxiliary points, these images of these, you know, points on the original curve under your secret isogeny allowed the math to commute and actually to let us agree on the same curve again, but people have been concerned that they leaked a little bit too much information about your secret isogeny ever since they were introduced.
And there have been papers that have been like, well, if you construct your SIDH parameters, just so you can attack them using the auxiliary curve, auxiliary points, but they were never very significant attacks and they were never against some of these parameters that we’ve been looking at for, I don’t know, going on six years now, until like almost two weeks ago. And then all of a sudden there was a, a preprint and. It took as far as I can tell, it takes the auxiliary points and it takes the specific curve and is able to use the fact that you’re able to compute most, all of the endomorphism ring of the base curve and the auxiliary points and is able to use them. This higher dimensional algebraic, geometry that I had to, to cram a crash course on to get a little bit, and you’re able to compute that secret isogeny.
Thomas: so this is the point where we explain for the non mathematicians here, how a Richelot isogeny works.
Deirdre: No, I dunno. We’ll I dunno if we’ll get all the way into that today. Um, Steven, can you try to give us an intuition of how this attack one works? And two is so devastating after very small kind of attacks for many years.
Steven: Yeah. I mean, I was as surprised as, as anybody. the auxiliary points have always been a concern and absolutely, um, they were clearly a problem for SIDH and I, my gut feeling was that there would be a quantum attack. I was never very convinced that SIDH would be secure against a quantum attacker.
So my, my gut feeling was that there would be some kind of quantum attack that used the auxiliary points. But so I was as surprised as anybody when there was, um, really a, a, a classical attack, Yeah. So how does it work? So I’ve actually been, I wrote up a little note, um, this morning about, um, about the, this Kani theorum.
So the, the,
Deirdre: Oh good.
Steven: key, the key concept is, um, a paper by Ernst Kani from 1997. He’s a number theorist and algebra geometer, who who’s done a lot of work on, when Jacobians are products of curves and stuff like this. Anyway. So, so he had this paper, um, which just had what was needed, just sitting in it
Deirdre: Yeah,
Steven: what it, what it boils down to.
Yeah. So the key point to the attack is you have to go up a dimension. You, you can’t think about elliptic curves anymore. You have to think about products of elliptic curves. So you have to think about in some kind of new object, which is E_1 X E_2, where, where E_1 and E_2 are elliptic curves.
And so. so this is pairs of points, right? This is a set of pairs, {P,Q}, where P lies on E_1 and Q lies on E_2.
Deirdre: mm-hmm
Steven: And you can consider this thing as, as something called an abelian variety. It’s a generalization of elliptic curves. It’s a very special case of an abelian variety, and there’s, um, notions of isogeny and so forth that, that live in that world.
And yeah, most of the things, most of the things in that world are, are not products of elliptic curves. They’re Jacobians curves. Um, so yeah, to make, to cut a long story short, the way the attack works, the way the theorem works is it says if you choose a subgroup of a certain form and you take a— so, okay.
Subgroup. So isogenies somehow correspond to subgroups. I, I saw the act of isogeny is like quotienting out by a subgroup. So you can, you can think of an isogeny as being a, a function from one curve to another. You can also think of it in terms of its kernel. So kernels, just a fancy way of saying the things that map to zero, you can think of it as a, as a subgroup.
Um, and so if you take this product of elliptic curves and you write down a particular, uh, subgroup of it, when you quotient out, and when you take the isogeny, this theorem by Kani tells you under what conditions you’re gonna end up back at a product of elliptic curves again, rather than the general case of being a Jacobian.
So if this, um, if the certain conditions are satisfied, so you can write down this product of elliptic curves, you can write down a subgroup, you can compute the isogeny because someone worked out how to compute these isogenies, that’s the Richelot part, and what the theorem of Kani says, if these certain conditions hold, then you will end up at a product of elliptic curves.
Deirdre: Mm-hmm
Steven: And that becomes a test, that becomes a test you can use, I’ve got certain points. If these points satisfy this condition, I’m gonna compute something and get a product of elliptic curves. If these points don’t satisfy some relationship, I’m gonna compute something and I’m gonna get a random looking thing, which will not be a product elliptic curves.
And so the, the whole, so, and this theorem was just sitting there for 20 and so the whole, the whole magic was people realizing, ha I can use this theorem. This gives a criteria to test some algebraic relationship between points and then it it’s actually relatively straightforward. I mean, it’s the kind of thing that once you see it, you’re like, holy shit.
You know, I could have done that. Once you see the trick, pretty clear how you can use this as a way of, um, of getting partial information, um, except there’s one more obstacle you’ve gotta solve and you’ve gotta solve, you’ve gotta be able to compute a isogeny whose degree is kind of outside your control.
Um, so you end up with this weird thing where you, where you have to look at a number like, um, three to the three to the, some power minus two, to some power and you, and, and suddenly this, the shape of this. Um, pops up and, um, and, and the, the effectiveness of attack depends on exactly what’s going on with this power of two minus this power of three.
And so if we talk about the two papers, the paper that’s clearly, there’s been two groups of authors that have been working on this. Um, not entirely in isolation because they’re because one of the authors is a PhD student visiting the others. They’ve clearly been talking about this stuff. SO the theorum was known about, and the idea was known about.
And so the paper that’s come out, um, uh, just in the last, uh, day or so, um, at the time of recording, um, so that’s the one by my know, and Martindale, um, it sort of gives, an idea of attack. And then the paper that’s actually came out earlier by Castryck and Decru. They’ve actually gone a bit further.
So they’ve said, yes, you would get stuck here, but Hey, if we know something about the base curve, we can actually push beyond this and we can push further. So the, the first paper actually goes further than the, than the second paper, but they’re all based on the same observation of Kani.
Deirdre: Yeah. And so that, that thing that you needed to know is more information about the endomorphism ring of the base curve. Is that correct?
Steven: Yeah, so you need to be able to compute this weird random isogeny. You need to be able to compute it on points. Um, you need to really be able to evaluate it and, um, and its degree is, large and you don’t have a lot of control over it. So if you know the endomorphism ring of E_0. Then it’s easier because you can somehow write, um, you can try and set up this thing so that it’s actually an endomorphism yeah.
least you’ve got something you can evaluate.
Thomas: yeah. I’m, I’m gonna sound super dumb here. Right? So, um, So I, I think that like the intuition behind what you just explained about how, like, you know, we, we, you know, we take these mathematical objects and we bring them up to a higher dimension and we can do some computations and we’ll get something that makes sense if we, you know, guess right.
And we will get random stuff if we guess wrong, like that, that I like the broad kind of outline of that is like, oh, Almost every Oracle attack works like that
Deirdre: Yeah.
Thomas: that. Yeah. So I immediately latched on right there. Like that was great. Right. So I guess my question is like, is there a simple, like, intuitive way to understand what it is that we’re guessing here?
So I, I understand that like we’re getting, um, you know, kind of points on curves. Um, and that, we’re what we’re trying to discover is like the sequence of isogeny steps that were taken to reach those places.
Deirdre: very, that’s very, it that’s basically it.
Steven: Yeah. So I guess the key, another key fact about isogeny crypto it’s annoyingly, not very efficient. again, if, you know, if you know about, um, normal elliptic curve, crypto, or RSA, you know, about the square and multiply algorithm and you can compute G to the G to the power a, um, quite quickly by doing, you know, the last thing you do is you go G times, G times, G times, G a-times, that would be madness.
You do squareing and multiplication, and you can, exponentiate efficiently. Unfortunately, with isogenies, back to the dumb thing. How do you compute a large degree isogeny. You compute it by composing a whole bunch of small degree isogenies. So isogeny world is, kind of clumsy in that you really are doing the dumb thing of G times G times G, except it’s phi_1 composed with phi_2 composed with phi_whatever.
Um, so, so in SIDH. When, when Alice is choosing her, um, her protocol message, there’s this base curve and she’s computing a long isogeny of degree two to the N, but she’s computing it by taking an isogeny of degree two. So a little step and then another little step and another little step. So she takes N little steps and publishes the, the end, the curve she got to, and then she takes these two points and maps them across. And then Bob does the same thing. He computes the isogeny of degree 3. And then another one of degree three and another one. So he computes some large power of 3. and sends that, that curve. So, um, so Alice’s secret is really a sequence of isogenies and so’s Bob’s, and it’s always been obvious that a really natural way to attack would be to somehow recover this thing kind of bit by bit by by working.
Um, and so some work that I did some years back on, on an adaptive attack, which was really using like a decryption Oracle as a test. That’s exactly how it worked. And we, um, we could learn the, the secret key kind of back— well, it’s sort of , this is a little endian or big endian question, but, um, but essentially what we would do is you would learn the secret key bit by bit, which boiled down to kind of finding the path and reverse you would work out what the j-invariant it was of the, if the first step back in from the end and then you gradually go back. Um,
Thomas: And this is, this is, this is GP. This is G PTR that you’re talking.
Steven: GPST yeah.
Deirdre: Yeah,
Thomas: Yeah. Okay. I’m, I’m, I’m allowed to get these things wrong. Right. And like my understanding of GPST is it’s named for the, yeah. It’s the names of is the authors of the paper, which is like the convention in cryptography. Right. Um, but my understanding is that basically takes kind of textbook SIDH it’s the difference between textbook SIDH and like something like SIKE that you could actually deploy is the fix for the GPST attack.
Deirdre: Yeah. Yeah. Thomas, you know, a lot more than you let on. Jesus . Um, okay. Now my first question is we basically knew that if you could compute the endomorphism ring, Of the destination curve that you could compute the secret isogeny, that like, that was like a fundamental security reduction of isogeny based crypto that we’ve known for a bit, right? But this is if you can compute, did we know that or did we, did we show that for computing, the endomorphism ring of the base curve? I don’t remember.
Steven: No. So, so the, the, the question of whether the, whether there’s. whether you want the base curve to be kind of special and have known endomorphisms. So, yeah. So again, for, for context, we’re talking about supersingular curves here and supersingular curves have really quite complicated endomorphism rings. So they’re, they’re maximal orders in quaternion algebras and they’re noncommutative and they’re, quite weird.
Deirdre: And I still don’t know what that means,
but
Steven: it’s, uh, well, anyway, all it basically means is that you, you take a sort of, one of your classic curves, like y² = x³ + x, and all you need to realize there’s something that acts like square root minus one. And that doesn’t commute— that anti commutes with Froebenius, and that’s an easy, an easy calculation that P is congruent to 3 mod 4, so i^P = -i. So, um, so you end up with this non-commutative endomorphism ring.
Now. Yeah. So there are some curves that you can just write down and you can see very easily what the endomorphism ring would be. And, but if you take a long path in the isogeny graph— if you take random isogenies and, and then forget what you just did, then you don’t, then you don’t know what the endomorphism ring, of the curve is.
Deirdre: Okay.
Steven: it’s, it’s long been a question of whether you should choose the special curve or the, or the general one.
And, um, there’s been, quite a lot of discussion about this in the literature. So, um, there’s definitely some protocols where you absolutely have to, you don’t want anybody to know the endomorphism ring. And so you have to have some kind of trusted setup or, or some process um, because the only way we know to write down— this is also an annoying problem.
We don’t know a way to write down random.
Deirdre: That.
Steven: a way to generate a random, supersingular curve without knowing it’s endomorphism ring and, and a whole bunch of me, me and a whole bunch of people, um, wrote a paper on this at CFAIL. So that’s that’s next is CFAIL. And we have a very, a very, um, a paper with who, whose, whose list of authors almost, um, fills out the page limit for the, for the CFAIL.
Um, and it’s on some ideas that don’t work about how to generate a random, supersingular curve. So, um, so that’s already an Anno—, so there’s two annoying problems. There. There was already a bit of suspicion about, are curves with known endomorphism ring weaker for some applications.
Deirdre: Yes.
Steven: and two, we don’t really know how to solve that problem very well.
Um, we would, so we’ve got a suspicion that they might be weaker. And so you’d like to have curves without known endomorphism ring, but we don’t really know how to build them without some kind of trusted setup. So that’s, that was annoying as well. And, um, and in, in SIKE the actual NIST submission, SIKE, they did start with a special curve for better or worse.
And, um, so they really, um, kind of. Well, in retrospect, shot themselves into the foot, unless you’re a conspiracy theorist. In which case you would argue that no, they, they, they would’ve been suspected of putting in a trap door if they’d done anything else. Um, so it was actually better, better that they went for the weak curve straight off, rather than being accused of having a back door.
Deirdre: Rolling my eyes as hard as they can roll. all right. I was, I was just about to ask about, like, it, it’s so frustrating that we’ve you and others have tried to figure out nice ways to generate random starting curves like this. And it seems like. Our only hope might be to do something like this trusted setup to generate a, a more secure starting curve.
But then, uh, the Martindale paper came out yesterday and it seems to indicate that that might not even because
Steven: Yeah. Now
Deirdre: Yeah.
Steven: I don’t think so. So, so yeah, so to get back to the, to the main thread, so the, the original, um, the, the original two
Deirdre: Yeah,
Steven: Castryck-Decru paper, the really like I said, there’s this bit where you have to compute the isogeny, whose degree is a power of three minus a power of two or vice versa.
And, to do that efficiently, it helps if you know the endomorphism ring. So if you know the endomorphism ring of the curve, you can do that step. that’s the, the one where there’s code available. That totally works. And, and, and it breaks the, um, Microsoft challenge and it breaks the SIKE instances and, and they’re all dead because they all start with a special curve.
Um, so at the moment we don’t know how to really do the attack in general and the paper by, um, Mineo and, and Martindale. I mean, they say it works for general curves. Um,
Deirdre: Ha.
Steven: I don’t wanna be to sound ungenerous here. I mean, it’s, it’s, it’s nice work, but I mean, what they’re really saying is we got stuck at this point, whereas Castryck
Deirdre: Oh,
Steven: Decru, they saw that there was a problem and saw ah, here’s a problem we can solve if we use special curves.
So, so I mean, it’s not that they’ve taken the Castryck-Decru method and somehow solved that problem. It’s the other way around:Castryck and Decru, it got to exactly the same point that Martindale alone mine did, but then they said, ah, but if we do this, then we’ve solved it. So there’s really nothing in the Martindale mind, minor paper, that’s um, you, you’re still just basically looking at some number of the form, large power of two minus large power of three and hoping that it has smooth enough factors. And, I mean, this is really a stretch because you don’t just need, I mean,
You’ve got this random number. You want it to be smooth. So you want it to be a product of small primes. Why is that? It’s for two reasons, right? Two reasons you want small primes. First reason is cuz you can only compute small prime degree isogenies. So if you are gonna have an isogeny degree, 300,000, you have to compute 300,000, um, things. But also because you have to work with torsion points, you have to work with points of, of that order.
And they’re defined for some extension of the ground field. What’s the extension? Well, it’s like L minus one. If you’ve got a prime L in the worst case, it’s like an L minus one degree. Well, I can’t actually even be worse, but, um, in the supersingular case it’s controlled. So, um, so you’ve got, oh, I’ve got to compute 300,000 multiplications over a field extension of degree, 300,000.
I mean, it’s just hopeless. So, so, um, there’s no, from what I see, there’s still in the general case of an unknown endomorphism ring,
Deirdre: okay.
Steven: There’s no reason to believe you’d get any loss of security. That’s what I’m saying today. I mean, we, you would need new ideas to, well, you’d need some kind of new tricks, I think, to, to push beyond this, but who knows?
Deirdre: Okay. Cuz I, I saw that yesterday and I’m, you know, in, in Vegas for all the hacker conferences or whatever. So I’m like, oh no, it’s even worse. like our, our like last best hope, which is like doing something very expensive to generate a randomly generated curve with an unknown endomorphism ring might also be like, not even that great. Okay. Thank you. I thought it was even worse than I thought.
All right. So now. Now that several of us have a bit of an intuition of how we leverage this attack. And, the implementation that we’ve, uh, been talking about, uh, the, the original authors of the Castryck-Decru, uh, paper published, some Magma.
it’s a mathematical, uh, library that a lot of, uh, academics can use, but you need a license, blah, blah, blah. So, a bunch of enterprising, mathematicians, ported it to Sage, which is a Python based open source platform. And they were able to get a naive implementation working and it would break the largest parameters in like hours, and lots of quick improvements to math and algorithms in Sage and in their script, I can now break the largest parameter set for SIKE in… six minutes on my laptop. Excuse me, 20 minutes. oh, it’s a big, big 20 minutes on my, MacBook air M1 laptop, um, which is just ludicrously easy. When we thought that was like a beastly, like turn it up to 11, belt-and-suspenders parameter set two weeks ago. Against not even, not just against classical, but for future quantum computers. anyway, so, I will have a link to that in our show notes.
So that’s for SIDH. There are— I’ll pose the naive question: is all isogeny-based cryptography broken?
Steven: Fortunately not. So, yeah. So we’ve got, we’ve got SIDH, which is which is broken in a special case. And, and, you know, if we’re feeling optimistic, um, it might be saveable with trusted setup, but then we’ve also got, uh, several other things. So the most, um, obvious one is something called CSIDH.
And so this. CSIDH uh, C stands for commutative. Um, and it’s a, but the joke, the S a pun on the fact that there was some European research project workshop on an island somewhere. And, and they came up with the idea while they would by the sea side. so that is, um, different, and it doesn’t have these annoying auxiliary points.
So the good news is you are really sending, just elliptic curves. So to get back to Thomas’s question, it’s, you’re still going from a curve to a curve. And so your protocol message is an elliptic curve, but it’s, even more like Diffie-Hellman is really like Diffie-Hellman.
Um, so CSIDH is quite nice, but unfortunately CSIDH is not quite so quantum resistant.
So there’s a, there’s a subexponential algorithm due to Kuperberg, and, um, there’s been a lot of papers, um, somehow arguing that this algorithm is quite practical and, um, I was, I was re initially. Pretty unconcerned about Kuperberg’s algorithm. And I, I wasn’t convinced that it was gonna actually be a big problem, but I’ve gradually become, become convinced.
I mean, there’s a paper by Peikert on this that, that helped change my mind and, and work by, um, various others. Uh, and so what we’re— the problem with CSIDH is we’re not quite sure how big the prime needs to be.
Um, and, and quite what the efficiency is. So it’s kind of, it’s kind of, it’s cool. Great for protocols.
Cause it’s so close to Diffie-Hellman and lots of people writing papers about it and coming up with various schemes, which is nice. Um, but it’s a little bit unclear about whether it’s really practical for actual. Like TLS or something like that.
So that’s CSIDH. And then there’s also more, more sort of generalized isogeny problems. And I’m thinking particularly about signature schemes here. So there’s been a lot of work on signature schemes, and the signature schemes can be based on really quite generalized isogeny problems. And if you’re, if you’re a theoretical cryptographer, the point is that you only need a one way function for a signature scheme.
So you can do, Fiat-Shamir type signatures without needing quite the same algebraic structure you need for Diffie-Hellman. So there’s been various work on signatures. I’ve worked at a bit on this topic, and there’s in particular, a very cool scheme, which I didn’t work on called SQIsign, which, again, it’s not entirely clear how practical it is, but it does have a pretty short signature.
So, so this is, uh, still very much alive, totally unaffected by this stuff, because there is no auxiliary points. Um, it’s based on just a special case, but still a fairly generalized general isogeny problem. So, yeah. So there’s still, there’s three things to keep in mind:
first CSIDH might be saved with some kind of trust to set up.
Deirdre: oh, uh,
Steven: S SIDH might be saved. CSIDH is, is very much alive, uh, apart from the Kuperberg thing. And again, there’s no reason to think that these ideas would have any relevance for, for CSIDH at all.
And then there’s things like SQIsign and other signature schemes, which, which again, should, not be affected by this kind of attack.
Deirdre: Yeah. And then, um, related to SQIsign and kind of signature schemes, uh, I think it was De Feo and others published, was it you and De Feo published the isogeny-based proof of knowledge? Uh, recently?
Steven: Oh, I hate that paper. God, that
Deirdre: why? Hi,
Steven: Oh, it’s so ugly. Oh, that’s been the most painful paper. Yeah, though. I have to say that was that’s vaguely relevant for signatures, but that was really about the adaptive attack. Right. That was about, that was more on the hope of getting non-interactive key exchange.
Because you want to, you want to do something, so yeah, this is, this is back to, this is back to how beautiful Diffie-Hellman is, right?
Diffie-Hellman is the most beautiful thing, because Alice can publish G^a and Bob can publish G^b and, and you normally think of it as sending each other a message, but you know, these can be public keys or something, and you can get this, you can get this noninteractive, um, key exchange and, and what you want is isogeny versions of that.
And CSIDH, yes. CSIDH gives you noninteractive key exchange, and that’s why it’s quite easy to build, um, Diffie-Hellman-like protocols offered, but SIDH didn’t because of these cuz of this adaptive attack. Um, but if you, if you would publish an SIDH key and a non interactive proof of correctness, then, um, then you can get on.
So that’s really what that, that paper was about.
Um,
Deirdre: I was very hope happy because, uh, I was able to start telling people, Hey, you can verify this proof on your long term SIDH key. You don’t have to use SIKE. and so you can start slotting it into places. And then I had to be like, yes, it’s a bit large. You probably want to just use it for kind of long term ID, key pairs or something like that, but you can do it.
Steven: Yeah, it was not, it was not very nice.
Deirdre: Okay. So
Steven: I dunno if Thomas has any questions about this stuff. I feel like we should
let him
Deirdre: well, like,
Steven: checking. You’re still awake.
Deirdre: Yeah. We’re like,
Thomas: I’m mostly, I’m mostly following, but you guys are kind of covering where I would’ve like asked questions anyways.
Deirdre: Okay, cool. alright, now we’re kind of getting into speculative territory, which is. Sometimes areas of cryptography go through, uh, kind of like a, painful growing period where like the first constructions, the first stab of how you do something seems alright. And then there’s just like, Break break, break, break, break.
And then they’re like, okay, let’s reformulate. And we’ll try to do this a little bit differently. And then we come up with a kind of more mature version and that’s like, okay, we had to kind of learn, learn a little bit, grow a little bit, but this is the thing. And or something like that. And I don’t have a good analogy off the top of my head, but I’m mostly kind of wondering.
Is this kind of giving us some lessons, some directions for research about how to move something like SIDH forward, or do you think it’s gonna like, are we there’s been research about using like hyperelliptic curves over smaller fields to do, is based key exchange and things like that? Like, that’s been an area, like, is that fruitful or do you think it’s gonna be more of these other areas or
Thomas: I was, yeah, I was sort of wondering, cuz like, you know, I was in high school in 1993. Right. But like, you know, I was wondering if it was kind of roughly analogous to like conventional curves and like the MOV attack or something like that, where like we’ve got like a special brand of curves that we’re thinking about using.
And it turns out that that special brand of curves is totally janked up for doing, you know, the kind of cryptography that we want. And then like for 10 years after that. Right. Like you have, you have like Bruce Schneier saying I don’t trust the math on curves. Right. Because there’s stuff like, you know, the MOV attack, which is not relevant to any of the things that we end up really using.
But, you know, I don’t know, is this the, is this the moral equivalent of that?
Or I know we’re, we’re asking for predictions, but.
Steven: yeah, I mean, the, I think. So, yeah, I got, I got into, I got into elliptic curve cryptography in the, in the mid nineties when it was still very much a new subject. And that was, that was absolutely the narrative. The narrative was that, you know, elliptic curves were so new, the mathematics was so complicated.
How could you be sure it was secure. There was this famous quote from Rivest, um, comparing it, you know, to Cheldian poetry and nobody understands it and all this kind of stuff. Um, and it was, it was, ‘RSA is so simple’, until you’ve tried to understand the number field sieve. And then you realize that RSA is not simple at all.
Um, yeah. And the, the story with pairings is really funny, right. Because of course, yeah, there were elliptic curves were proposed, people even did, um, choose supersingular curves. Um, for efficiency reason, there was a, there was some early papers that said, oh yeah, you should use supersingular curves. Cuz then you got this really fast doubling map and whatever.
Uh, and then of course there was the, the, um, paper by Miller and Vanstone and also paper by fried R and then they, they sort of killed supersingular curves. But then in, in 2000, 2001 pairing based cryptography became alive. And suddenly it was like, oh no, ractually some of these curves are actually good because we can use them for pairing based crypto.
Um, and that became, you know, that’s still an industry, right. I’m still a, still a thriving area of, of, of work. So, um, so it’s interesting how you, the pendulum kind of swings between between more structure and less structure: you want, you kind of want the most general case because you think that’s gonna be more secure.
Uh, and then at some point you’re like, oh yeah, but there’s this special feature or there’s this gadget that I can use. So I’ll, so I’ll go, I’ll go a little bit more towards the, the special case. And we see that all the time in cryptography and we see that in lattice cryptography, right? So you’ve got, the general, the most general lattice that’s completely unstructured.
And you have to write down a huge matrix to, to define the lattice. And of course we don’t do that. We do things like NTRU, we work with with structured lattices, and because they’re much more compact, they’re much more efficient. We have fast fourier transform to do the, the ath— multiplication and, and, or the arithmetic more efficiently.
So there’s always this tension between the general, the general problem, the general case, which we feel like ought to be more secure. And the, the special case that, that gives us more structure.
Deirdre: Mm-hmm
Steven: Um, in terms of isogeny, I I’ve, I’m not gonna make any bets. I mean, it’s, uh, it’s, it’s really hard to say. This. I mean, this shows that, you know, here was a, here was a theorum that was lying around in the literature.
And, um, boom, I mean, as you say, if you can break that in minutes on your laptop, it’s incredible. So, um, I mean, it certainly tells you that the field is not mature. That’s absolutely right. You know, here was, here was something that, that, um, And, you know, we don’t know that someone’s not gonna do the same thing to elliptic curve discrete log tomorrow.
Right? I mean, why do we believe, why do we believe elliptic curve discrete log is hard? Well, we believe it because there was 20, 30 years of, of people really studying elliptic curve, discrete log. And, and we have, you know, good confidence that people like Geddard Fry and Joe Silverman and, and Hendrick Lenstra , really thought about it. And, um, and then lesser people like myself and Nigel Smart and, and, uh, and we spent a lot of time trying to break it and Taka Kazu Sarto and Neil Koblitz, and, you know, there was a, there was a lot of attempt to break curves and, and we gave lots of talks about it and wrote papers.
And at the end of decades of time, um, elliptic curves were still secure and that’s the only reason we have any confidence whatsoever in curve crypto, right? This is just because a bunch of mathematicians looked at it. and this was always, the problem with, with isogenies is, is not enough people are looking at it and there’s, two sides to this question. You need the, you need number theorists and algebraic geometers to look at it. Um, and it’s fantastic that, that, uh, Walter and Chloe and, uh, Thomas and Luciano have done that and found, found this idea. But you know, you also need quantum algorithms people to look at it because if you’re talking post quantum crypto, you need to be sure, not just that all the number theorists and geometers and people who understand classical stuff have looked at it, but also people with a, with a bit of an understanding of quantum algorithms have looked at it as well.
Um, and only then can you be sure it’s really post quantum secure. And I, I was, I was not confident we were there with isogenies. I there was a, you know, the, the number of people who really understand quantum algorithms and isogenies, very very small
Deirdre: very small
Steven: And so, um, I’m, I’m actually not surprised that that NIST didn’t choose SIKE, um, as a, finalist, I’m not surprised at all. my prediction for the NIST competition was extremely bad, so I didn’t publish it, but I will at least say that SIKE was not there. Um, I did. I just didn’t think it was mature. I’m not surprised they didn’t take it. And they’ve been proved to be correct because, because here’s an attack.
Um,
Thomas: And compared to, uh, so compared to SIKE, the, the impression I have is that we have, you know, kind of like for the same reason that we kind of believe in conventional curves is the 30 years of research we’ve done on them. We’re in approximately the same place on lattice and NTRU and stuff like that.
Like, NTRU goes back in like a long time, too. Right. So like we have more con. Yeah, we have more confidence in the lattice crypto, than we do in isogenies, right. guess one, this is the apropo nothing. Right.
But I was wondering when I was reading your kind of FAQ post on the, uh, on the Decru paper was the, the theorem from Kani. Was that motivated by cryptography or was that just pure abstract number theory work.
Steven: Pure abstract number theory. Absolutely. Utterly unrelated to, I I’ve met, I’ve met Ernst Kani. He works with Gerhard Fry or he worked, I mean, they were both of a similar generation and, um, and Fry got interested in cryptography, but Ernst Kani was not interested in cryptography at all. I probably met him around the time when the paper was, was being published and he was giving talks on, on this kind of topic.
Um, I may, I may have even seen that theorem presented. I, I, don’t no recollection. Um, but no, I can assure you, he wasn’t the least bit interested in cryptography. Um,
Thomas: That’s somehow more, more disturbing, right. Is like, cuz it suggests that there’s other things like that.
Deirdre: Yeah.
this kind of dovetails with something you just mentioned was, um, Kristen Lauter, who was One of the people in the early two thousands who started looking at these supersingular isogeny graphs, not just general isogenies, which was a little bit earlier in the literature, but like specifically supersingular isogeny graphs to use for one way function.
Um, including, I think she, published a hash function, a very slow post quantum, uh, hash function, based on this. And she gave a talk one time when she basically, kind of articulated, a concern about isogeny based cryptography having a lot of algebraic structure and that both allows it to be useful in all kind of the ways we describe, but also makes some cryptographers nervous because it basically amounts to having a lot of avenues of attack on these certain constructions.
Do you think that isogeny based crypto is more vulnerable because of its algebraic structure? Or do you think lattices have similar algebraic structure, but it’s different and therefore… like, does that make any sense at all?
Steven: Yeah, I, I— look for, for public key cryptography. You, you are always, there’s always this tension between, between structure. Because you, if you’re gonna have something like Diffie-Hellman working, you’ve, you’ve gotta have some structure, right? You’re not gonna get this out of just random mathematics. There needs to be some reason why things come together.
so all of cryptography is this tension between having enough structure to do something useful, um, but’s not enough that that makes it, fall over, um, to an attacker, and this is what we see in multivariate crypto, for example, I mean, yes, we know that solving a system of random polynomial equations is NP-hard, but you have to put a trap door in there, right? And so then you get Rainbow, um, and, uh, braid groups was another thing. Braid groups are really beautiful mathematics and yes, certain problems are hard, but you, you, if you’re doing anything like Diffie-Hellman, you have to end up with essentially subgroups that commute with each other. There it falls over because there’s various attacks.
Um, and, that’s absolutely the tension and, you know, it’s kind of a miracle that it works at all.
You look at something like elliptic curve cryptography, right? You’ve got elliptic curves. They’re kind of almost perfect. You, you they’re the minimal representation you could possibly hope to, to get. They’re super efficient. Um, You can, you can hash to random points. You’ve pairings if you want them. I mean, you could not really dream of something as good as elliptic curves, and unfortunately we’ve become totally spoiled by them. Right. So everyone just says, well, why can’t we have, why can’t we have something that just plugs into TLS and works like elliptic curves do, huh? What’s the problem with you guys? And it’s like, well, they were just, they’re a miracle. Elliptic curves are a miracle. They work so well.
And I see the, the, the, you know, the NIST, you know, ‘NIST is calling for signature schemes with short signatures and efficient verification’. Yeah?! You think?! I mean, that never occurred to me! We should come up with signatures that are just ECDSA or Yeah, that’d be nice. if it was easy, we would’ve done it already.
Um, so it is, it’s hard. So I, this is a long answer. I mean, structure, you, you can’t… get rid of the structure and, the whole story of post quantum crypto is things that are slightly less structured than RSA and elliptic curves, right?
So you’ve, you’ve either got less algebraic structure or you are introducing some kind of noise in some way, which, which comes with its own, difficulties and inconvenience. Um, so you’ve, you’ve had to throw away something to get it, to be post quantum anyway, and if you throw away too much, you, you don’t have anything useful anymore.
um, so it’s really hard. It’s really hard. and I mean, what, what we would ideally like getting back to the maturity of the field, you know, what we really want is, diverse systems. I mean, the, the problem we’re in now is that we only have RSA. I’m talking about, you know, TLS today. We have RSA and elliptic curves and then we have our authenticated encryption and symmetric crypto, which is good, but, you know, we’ve, we’ve, we’ve, we’ve you stuck with RSA signatures, ECDSA, EdDSA, you know, Schnorr signatures, um, and, and Diffie-Hellman key exchange and RSA, um, encryption.
And Shor’s algorithm breaks everything. It’s a problem. It’s a problem of diversity. If we had more schemes, then maybe we wouldn’t have had such a problem with, quantum computers coming along in the first place. And so obviously what we would like for the future is to have more variety of computational assumptions.
So we’re not putting all our eggs in, in one basket. And at the moment we’re kind of the way NIST is going. We’re kind of putting all our eggs in, into structured lattices.
mean, I I, like them. They’re good. Uh, but you know, you would like to have more diversity and, and so that, you know, you’re not, you’re not at the mercy of just one new idea.
Deirdre: yeah, what’s McEllice? Is that codes?
Steven: Yeah. That’s codes.
Deirdre: Its codes. Was that in round three?
Steven: Uh, McEllice is an alternate. Yeah. So one of the, um, one of the, uh, round four, uh, candidates. Yeah.
Deirdre: All right. So. You’re not exactly hopeful, but
Steven: I’m not super hopeful about isogeny, but you know, you’ve gotta be the, the thing, the thing I’ve been holding onto, um, Is, uh, you’ve gotta be, you’ve gotta be gracious in defeat. So I, I’m not gonna name names, but you know, there’s been there’s— over the NIST competition. There’ve been some very sore losers who have not, um, have not taken kindly to being broken.
And I’m, I’m very proud of the, isogeny community that we’re, um, you know, David Jao, Luca De Feo, I mean, really the inventors of it were, were Jao and De Feo. They were inventors of SIDH. And you can imagine both of them were feeling, a bit grumpy about it, but right from right from the get go, um, you know, they’ve been utterly gracious about it.
I mean, David Jao’s been interviewed, He was in a piece in Ars Technica and he was very gracious about it and very, very quick to, to, to acknowledge the good work. Um, Luca De Feo was writing sarcastic tweets within, within Um, You know, and that that’s, that’s how to be, how to be is to go, ‘damn, that’s good work. Um, yep. We’ll have to wait and see.’ And it’s not over, but, um, but you’ve gotta at least be gracious about it and not, um, and not be a dick, like some other people have been over the years.
Deirdre: what do you mean you don’t like, like thousand terabytes size, RSA keys? Like that’s post quantum secure, right?
Steven: That’s a nice idea. Actually. I like that idea.
Deirdre: Like it it’s pretty straightforward. I will say that I was down when I, when I saw the news about this attack, because like, isogenies helped draw me into a career in doing cryptography in some way. I love them. I think they’re beautiful. And they’re my, they’re my faves.
but learning the mathematics to understand this attack, the Castryck-Decru attack, has been fun. And then watching other people implement this attack in Sage and speed it up and like, just. Algorithms and like speeding up these Richelot isogenies and this, that, and the other thing has been really, really cool.
and so that’s kind of helped me like work through my grief, I guess.
yeah. Steven Galbraith. Thank you so much for joining us and making the time. This has been a wonderful conversation.
Steven: Thanks. I enjoyed it too.
Deirdre: yay. Awesome. All right, I’m gonna hit the button
