Birds Eye View on the Mathematics of Post-Quantum Cryptography

Hi everyone, my name is Sofía Celi and welcome again to another segment of Cloudflare TV. Today we have a very special guest to continue on this path of talking about post-quantum cryptography. Our guest today is Steven Galbraith who is the head of the Department of Mathematics at the University of Auckland and his interest is in a lot of very interesting topics of mathematics and today we're going to be talking with him about post -quantum cryptography. So welcome Steven and I'm really happy you're here. Thank you, it's nice to be here. Okay so maybe let's just jump in into the topic of itself and of course just go back and leave it because this is the question that is always posed by the people who are interested in quantum computers and hear about the quantum world and post-quantum cryptography. So what is post-quantum cryptography and why we need it? Well yeah, the problem is quantum computers. So there's the notion of quantum computer and people are building these things, still relatively small scale, and there's Shor's algorithm that is a very powerful algorithm that you can run on a quantum computer and unfortunately it solves a small number of mathematical problems but they're just the ones that we're using for a lot of public key cryptography at the moment. So a lot of current systems like TLS have got public key crypto systems based on number theoretic problems and if a quantum computer that's sufficiently powerful could be built then these systems will not be secure. So the question is what to do, what to do about this potential quantum computer and you could kind of put your hands over your face and say it'll never happen or you could plan for the future and so many people are planning for the future and I think the really important thing about post-quantum cryptography is that we're still looking for systems that will work on current computing technology and infrastructure. So we're not going all the way to quantum where we need quantum devices and quantum channels, it's just ordinary algorithms that will run on your phone that will work over the Internet but hopefully based on computational problems that a quantum computer cannot break as far as we know. Yes that's deeply interesting and you mentioned a specific algorithm, a quantum algorithm. Maybe you can talk a little bit more of how actually it works, this Shor's algorithm. Yeah I mean I'm not an expert in quantum algorithms but essentially it's this there's this basic, the basic concept is period finding and it's actually related to Fourier analysis and Fourier analysis is a ancient piece of mathematics, well a couple of hundred years and it's used in processing, signal processing and audio signals, that's how you hear, it explains harmonics and a lot of things we're familiar with from sound. So anyway so there's this piece of mathematics called Fourier analysis and Fourier transforms which is very well understood and there's a thing called the quantum Fourier transform and it's somehow the key, it's the key to doing some things much more, much more powerfully on a quantum computer. You'll sometimes hear people talking about parallelism, a quantum computer works in all states at once and it's not a really very good model for how a quantum computer is working I would say. It's better to think that there's a couple of very kind of magic operations that you can do with a quantum computer and they kind of unlock. It's like you've got a software library with this magic function that just happens really quickly and that somehow allows you to write a bunch more programs but it doesn't solve everything. You have to be able to translate your problem so that this magic function can unlock it and so factoring integers, solving discrete logs, these problems can be transformed into this period finding problem and that makes elliptic curve cryptography and RSA and pairing-based cryptography, it makes them vulnerable to quantum computers. Yes and we hear sometimes also for example of the other quantum algorithm that migrates certain types of cryptography which is Gruber's algorithm but we hear that it's not so, that that one is not so scary because of parallelization precisely because it needs a lot of parallelization. Yeah that's right I mean there's there's actually lots of quantum algorithms and yeah there's Gruber's algorithm, there's things that are of interest to people doing material science and chemistry and things like that but they're nothing to do with cryptography so we're mostly focused on Shor's algorithm because that's the one that has the biggest effect on public key crypto. Yeah okay so if Shor breaks most of the mathematical base of the cryptography that we use nowadays, what is the alternative? What kind of other maths can we use to create post-quantum algorithms? So there's, the way I look at it is there's two kind of different directions you can go in. So the fundamental thing you need, the reason why you can break discrete log and factoring is you have essentially a fairly rich mathematical structure that you're working with. So in the case of RSA it's a group, you even have a ring, never mind what these words mean but for elliptic curves it's a group, but you have quite a lot of structure and you have certain operations you can perform and that's enough. Any, basically any finite group you could do some, or abelian group, you could do some kind of Shor's algorithm. Now, so the question is that's somehow the structure, there's so much structure, there's so many cool things you can do that makes it great for cryptography because you can build really nice protocols and you can make nice signature schemes and with elliptic curves you have pairings and you have all this wonderful mathematics but unfortunately that mathematics is also what allows Shor's algorithm to be created. So if you're going to make something post-quantum you're going to have to leave some things behind, you're going to have to walk away from such a structured object. So there's kind of two ways you can go, you can just gradually take away structure and work with gradually more primitive mathematical objects, so that's one way to go. And the other way to go is you add noise, so you stop everything being exact anymore and so somehow instead of working with exact equations you work with things that are not really equalities, they're true up to some error term. So post-quantum cryptography has these two directions, there's the directions where there's less structure, which would be for example multivariate crypto or isogeny-based crypto, or there's kind of the adding noise approach which for example is code -based or lattice-based. Yeah, so let's talk a little bit about the later ones first because we hear a lot about lattices on the post-quantum NIST process that's currently running, so what are these lattices, why do we use them now in this post-quantum algorithm? So yeah, so a lattice, I think the word, when I think of the word lattice I think of sometimes if you're making a pie and you put the pastry and kind of stripes on the top of the pie, or maybe you have something in the garden, they also have this word trellis, right, which is like something that the plant can grow up. So a lattice is really a kind of a regular kind of crisscross type shape, so it's a bunch of points in space, but they've got this very regular pattern, you go a certain distance to the next point and a certain distance again to the next point and so on. So it's actually just a very regular kind of shape, it doesn't look very interesting at all, you would just say it's just some points. But what happens with lattices, once you go to very very high dimensions, is there's a whole bunch of computational problems that seem to be very hard both for classical algorithms and we believe, or some of us believe, for quantum computers. So the idea is you can somehow describe a lattice in lots of different ways by basically giving some vectors that generate it, and given these vectors, there's two types of problem that might be hard. So it might be hard to find a short non-zero vector, so it might give you a bunch of vectors that are quite long, and some combination of them corresponds to a short vector, but it may be computationally difficult for you to find that short vector, so that's one problem. And the other problem is the close vector problem, which is where you have all these points in space, and I give you a point, I take one of these points and I add a small error term to it, so it's a little bit beside, and I mean, if you do it visually, you think, what's the problem? You could just see whether, but if you can't see, if you're in really, you know, 500 dimensions, a thousand dimensions, you can't see what is the lattice point you're close to anymore, and that's the close vector problem. So it just turns out that we do not have efficient algorithms for these problems, and they've been studied a long time, maybe more than 50 years they've been studying lattice algorithms, and they seem to be some quite challenging problems, which is exactly what cryptography wants. Cryptography needs hard problems. Yeah, but when one reads about the current proposed candidates for standardization on the NISPOS quantum process, usually they are defined in other terms, they are defined, for example, about the short integer solution problem, so how then actually relates to the security of lattices? Yeah, so there was this really nice work by Regev, Oded Regev, and he came up with this formulation called learning with errors, is the first one, and then short integer solution comes next, and it's kind of a really nice kind of framework for talking about lattice problems without actually talking about lattices. So the learning with errors problem talks about a matrix and a vector, and the word lattice doesn't appear anywhere in this problem, but what it really is saying is you have a matrix that defines a lattice, and you have a vector which is actually a lattice point plus a small error, so it's connected to this close vector problem. But by abstracting away the lattices and expressing it in this very nice algebraic way, it's very easy for cryptographers to start using this to build protocols without, you can make protocols based on learning with errors without really knowing anything about lattices, you just, as long as you know some basic linear algebra, you can start defining these things. So LWE is a computational problem that connects with a computational problem in lattices, and Regev has these results that really prove some reductions between them, and short integer solution, that's essentially a kind of a dual problem where you're again looking for a short vector in a lattice. So again the formulation is by giving a matrix, which defines a lattice, and the question is to find a very short vector in this lattice. Yes, so that is very interesting because for some people maybe they will be more familiar with how lattices work, and for others more about the representation on SIE for example, so you can go in both ways to try to understand post-quantum cryptography, it's very amazing, at least for us. And for the other family of other problems that you can use to create post-quantum algorithms, you mentioned isogeny, so that's a very interesting word, it actually doesn't have that much relation to other languages. So what is an isogeny? Yeah, isogeny, it's a strange word, I find it a very peculiar word, I think it means of the same type, I think it is used in biology for meaning like a similar species or something. But yeah, I mean when I was first getting into cryptography, when I did my PhD, or after I did my PhD, people used to talk about elliptic curves being so complicated, and at that time RSA, everyone knew RSA, and elliptic curves were kind of new, and everyone said, oh elliptic curves, the mathematics is so complicated, and there's a famous quote by Rivest that says understanding elliptic curves is like reading Chaldean poetry. Anyway, there was this idea that elliptic curves were hard. Oh my goodness, people didn't know how lucky they were, right, that was only elliptic curves. Then in 2000 we had pairing-based cryptography, which is much more complicated, you have to understand pairings, and everyone had to go away and learn what divisors are, and Miller's algorithm. And unfortunately, isogeny is this whole next level again, you know, you thought elliptic curves were hard, oh my goodness, now you need to know morphisms of algebraic curves, you need to understand maximal orders and cartoonian algebras, all this kind of mathematics. So it's actually very hard to give a a nice simple idea of what it is, but basically it's instead of working with the group like we used to do, it's maps between the groups, so you're no longer saying I've got a group, I'm exponentiating, you know, g to the power x, I'm now saying I've got a map that goes from this group to this group, and then this group to this group, and we're somehow moving within kind of graphs, so we're moving, we've got vertices and edges, and the vertices are groups, they're elliptic curves, and we're kind of moving through these graphs, and there's weird structures above all this that allows us to make protocols work. But yeah, it's not, I'm afraid it's not so easy. But one of the things that I found very interesting about isogeny is that with the other types of quantum cryptography that is proposed, certain constructions that we are accustomed to, there's not a one-to-one mapping, so a lot of the protocols we use are accustomed to the way Diffie-Hellman works, which is not completely possible to achieve by using chems based on lattices or other constructions. But there's some ideas to actually use isogeny in a Diffie-Hellman way, so how, what's the research around that? Yeah, so there's this really, really nice idea, Jiao and Defeo of SIDH, and it's very elegant, and because yeah, there's really difficult, if you're walking in a graph, the idea is, you know, we start at one point and you walk somewhere, that's fine, maybe Alice does that, and she walks to some point, and then maybe Bob starts the graph and walks to some point. How can we get Bob to start from Alice's curve, and Alice to start from Bob's curve, and end up at the same place? That's kind of what you want to do with Diffie-Hellman, you want Alice does g to the a, Bob does g to the b, Alice can take Bob's value and go g to the power a, Bob can take Alice's value and go g to the power b, and they end up at the same place. That's what you need for Diffie -Hellman, and there's this incredible difficulty, if you're doing, if you're just wandering through a graph, how can you make sure you end up at the same place? And Jiao and Defeo very elegantly solved this problem, and it's one of those, when you're doing research, every now and then something comes up, and you just go, oh, I wish I'd invented that, and that's one of, for me, that's one of the ones. At the beginning, I wasn't that interested in isogenes-based crypto, and at some point, I really understand that that was a really good idea. I wish I'd thought of that one. Yeah, so then you get something that's very much like Diffie -Hellman, and then lots of stuff comes very easily, and then there's this other thing called Seaside, which is even better. It's even more like Diffie -Hellman. It's much more complicated to explain, but it's really very close to Diffie-Hellman, and again, it makes a whole bunch of things. You've already, protocols you've already got based on discrete logs, you can quite easily translate them to isogenes, but not everything, unfortunately. There's still some operations missing, because we've, like I said, we had to take away the structure for it to be post-quantum secure. We've had to let go of a few things, and because we don't have some of those things, it makes some protocols, like signatures, much more difficult. But there's also some advances now, actually, in the signatures. On the isogenes, it's also very interesting that it is the isogeny-based candidates, or constructions, the ones who have the smaller parameters, it seems. So do you think it's also the research is going to keep advancing on isogenes, on the signature, or Diffie-Hellman direction? Yeah, I think there's definitely, I think there's some kind of barriers that we will, I'm not sure we're going to get through. So I don't think it's ever going to be very fast. So the, yeah, we've got a, we've essentially got a, one of the problems with post-quantum crypto is that we don't have anything that kind of ticks all the boxes, that does everything we want to do. We've got some things that are very fast, but sometimes the keys are large, or the messages are large, or the signatures are large, something kind of blows up. So we've got very fast things, especially the things based on like entry type things, but it was based in rings. So you can have speed, but you may lose a little bit with bandwidth, or with public key size, or signature size. Or with isogenies, we can get the keys, public keys, nice and small, and potentially, well in ciphertext and things, small and potentially maybe signatures. But everything is quite slow, and I feel like there's kind of some, there's some barrier there. I don't, I don't feel like we can, I don't, I don't think there's some magic idea we're going to get that suddenly make it really fast. But I think there was, yeah, I'm sure there's going to be a lot of progress on, I mean, I'm amazed how much progress there is. There's still, when, I mean, I had PhD students working on this topic, and I remember one student in particular, I said to him at the start of his PhD, I said, this isogeny stuff is really cool, but I don't know, you know, you have, you have three years to do a PhD, and you know, in three years time, it may all be completely destroyed. Well, I can tell you, his whole PhD was on isogenies. He wrote it, he submitted it, he's been gone already for more than a year, and the subject is still going, and there's lots of, lots of results, lots of interesting papers coming up. So yeah, it's pretty active. And it's also a little bit similar to also what happened with elliptical cryptography, that it was for a while also in a little bit of a neutral state until there were some advances to actually put it in in practice and making it faster. Maybe there's hope for the same on isogenies, hopefully, that it will take, but it will take a lot of years as it took with elliptical cryptography. Okay, and there's the last one that you also mentioned about post-quantum cryptography, which is multivariate equations. So what are those, how are those used to construct post-quantum algorithms? Yeah, and again, this is a, this is really kind of basic mathematics. This is stuff that's very well understood. I mean, polynomials have been studied all through mathematics, and certainly this kind of multivariate systems, they were studied. I mean, algebraic geometry goes back a long way. So the idea here is that you really have, you really have, it's all based on algebra and mathematics, but there's not really any algebraic structure at all. It's nothing like a group. You really have something just like a one-way function. So you can, you have some huge horrible system, and you can evaluate it very easily, but it's hard to reverse. Now, so you can certainly make one-way functions out of it perfectly safely. You could make a hash function, a multivariate hash function, it would probably be okay. But that's not really what we want. We want more than that. So most of the time, people are trying to put a trap door into it to get something that's invertible with the secret. Because, I mean, that's the standard way to make a signature scheme, is where you have a one-way function with a trap door, so people can somehow compute, sort of hash the message in some way, and then you can invert it to come up with the signature. And what's proving to be difficult is to put secure trap doors in a way that keeps the keys, again, you can do this if the key size blows up and you have enormous public keys, but the challenge is to have relatively small public key, still an efficient scheme, but with a trap door in it, which is hard to attack. And that's, I would say multivariate crypto has a history of schemes being proposed and broken and proposed and broken. And iteratively over time, things get better understood and the schemes get better, but it's not quite the same as the history of things like RSA or discrete logs or lattices, where the initial concept is somehow quite clear and quite well-defined. And well, I have to be careful with lattices. Lattices had a few bumps in the road as well, but since RegEv, lattices are pretty well understood. The same can we say, I don't know if you can talk a little bit about also that there's some concerns about, for example, the security of some of the sojourney construction, specifically the Diffie-Hellman-like, yeah, what are the difficulties there down the road on those sites? Or what difficulties have you found? I think, I mean, security is definitely an issue with all this post -quantum stuff. I would say post-quantum cryptography, for that purpose, because it's post-quantum, has really only been going very strongly for about 10 years. I mean, I remember maybe 12 years, but that sort of point, I remember I started to, and everyone used to say before that, oh, this might be useful for post-quantum cryptography, but they didn't really mean it. And about 10 or 12 years ago, people actually started to take it much more seriously. And so in that time, there's been much, much more people have started working in it and really directing themselves and thinking more about post -quantum security. But that's not actually very long. 10 years, 12 years is not actually very long for studying these things. And there's lots of schemes, lots of parameters, and there's different, when you talk about security, you can be talking about attacking the mathematical problem in its pure state. You can be talking about attacking the way that's turned into a crypto system. You can talk about different attack models, like some kind of adaptive attacks or side channel attacks, false attacks. There's lots of work to be done to understand this stuff. And the biggest risk, of course, with any of these schemes is that there's an attack just around the corner that hasn't been discovered yet. And I mean, we've seen this with the multivariate where fairly elementary attacks are still being found. With isogenies, I definitely have concerns about isogenies. Again, not so much whether there's a classical algorithm that we don't know about, but whether there's a quantum algorithm we don't know about. I would not be surprised if next week someone who really understands quantum algorithms publishes some paper and has some kind of break on isogenies. But yeah, the thing you're particularly talking about is Seaside and the ones related to that, where there's an algorithm due to Kuperberg, which is a kind of framework for attacking something called the hidden shift problem. And we certainly understood that the scheme can be expressed in this way. And then, so the question is, well, how significant is that approach for attacking the system? To what extent should you, how big should the keys be to get a certain security level? And this has certainly been a contentious point. I mean, at the beginning, I was fairly unconcerned about it. My attitude was that the Kuperberg might exist, but you actually have to have a quantum circuit to compute the basic Seaside group, actually. And that quantum circuit will be so big, no one would ever write it down. But I feel like I've been essentially disproved by there's been sequences of papers that have worked on that point. And I have to accept that maybe it's not completely unthinkable that someone would actually build a quantum computer that could implement that circuit. In which case, then the rest of the Kuperberg would run. But this is where the question of what is quantum security or post-quantum security becomes really difficult. Because at the moment, we only have very primitive quantum computers. We don't have anything even close to good enough to run something like Shor's algorithm with gates that behave like quantum gates and with error handling. And then now you want to, even if you get something that could break RSA, which might need thousands or tens of thousands of qubits, then to go to something like, can we build a quantum computer that can actually compute the Seaside circuit and run Kuperberg's algorithm, which requires storing quantum states and reloading or, you know, I've got no idea. I don't know anything about this stuff. But it's not clear that there's, you know, with classical computing, there was really a point that once transistors were working, then it just scaled up. And, you know, computers, you think about the period between 1950 and say 1980, a 30-year period where computers went from huge things that filled an office to kids had them. I mean, I had a computer in the early 80s, a home computer, you know, to play games on. So in a 30-year period, you know, the world changed. People have been working on quantum computers for close to 30 years now, and we're still we're still right back in the filling the room, and it does this tiny thing. So I've got no idea. So that's the really big unsolved problem. What does the security level mean? What do we actually have? Is Kuperberg's algorithm a threat? Or do we only have to worry about Shor's algorithm? I've got no clue. I mean, we should be conservative. That's the only solution is to be conservative and say, well, actually, we probably should be aware of all these things and take a fairly conservative option. And if that means it's slow and it's got large keys. That's probably what we should do. Yeah. Yes, that's also one thing that I'm a little bit scared of, but at the same time, it's a little excited to see what the future will look like with a quantum computer and what security will be. I don't know what excites you. This may be the last question because we're running a little bit out of time. But what is in your final words, what excites you about post-quantum cryptography and the quantum computing world that's coming? I mean, what I love about it is it's just bringing more and more mathematics in. So it's just it's great. And everyone should try and learn more mathematics because you don't know what's going to turn out to be useful. We've got mathematics that was developed all through the 20th century by number theorists and geometers, and everyone thought they were just doing pure mathematics. No, it's applied mathematics now.