The Future of the Post-Quantum Competition: the Signatures'

Welcome to Cloudflare TV. This time we are presenting latest news on post-quantum cryptography. My name is Armando Faz and I want to introduce you to this Cloudflare segment. We're going to talk about post -quantum signature schemes and their future. And for that we have two special guests that are joining us to talk about this topic. So we have Luca de Feo and Ward Beullens who are experts on the field. So could you please give us a little bit intro about yourself? Luca, we can start with you. Sure. So hi, I'm Luca de Feo. I'm working at IBM Research in Zurich and I work especially on isogeny -based cryptography, which is one sub -branch of post-quantum crypto. I work on signatures, key exchange, encryption and other topics of course related to public key cryptography. I just joined IBM slightly more than two years ago. Before that I used to work at Université de Versailles in France and I've been in crypto for almost 10 years now. That's really cool. So, Gerrit. Yeah, so hello everyone. My name is Ward Beullens. I joined IBM just two months ago. I finished my PhD in Belgium in 2011 last year. And yeah, my work is on post-quantum signatures. I work a little bit with isogeny-based signatures, mostly with multivariate signatures and also like some other weird things like Legendre symbols and primitive kernels. So yeah, I like having many different branches of cryptography. That sounds really cool. But okay, so let's try to say for our audience, what is this about this post -quantum cryptography? So basically what we know, our connections, our communication, all is about encryption and the use of cryptography to produce signatures that allows to authenticate to some other person that we are talking to the Internet. So the current algorithms, they are really strong with the actual computing power. However, with the use of quantum computers, they present that there's a threat with the current algorithms that we know. So if we were able to have a very powerful quantum machine, they can solve the problems that in which the current cryptography is based. So that would be like a serious problem. So in order to solve this, this is where we call it post-quantum. So what is the preparation that we have in order to make certain replacement and putting our research on algorithms to replace that will be super strong even with a quantum computer. So in this lens, I'm talking about post-quantum cryptography. So the NIST, which is the National Institute of Standard and Technology in the US, they started a competition in 2017 about making a call for what are different proposals or post-quantum algorithms. And since then, several proposals have been discussed and analyzed. And some of them have been attacked. Some of them have been resisted to the current cryptanalysis. And here in the room, we have expert in that material. Now, the post-quantum competition splits in two parts. One of them is the algorithms for key encapsulation schemes. And the other is for digital signatures. So in this case, one of the different algorithms or let's say categories of post -quantum algorithms are like isogeny-based cryptography. The other is like multivariate equations. And for the case of isogeny, so I want to reach this to look at who can help us to give a better understanding of that. So I heard that isogeny-based cryptography is very related to elliptic curves. But first of all, so what is an elliptic curve? Like in very simple terms. In very simple terms. Of course, yeah, it requires some mathematical background to define an elliptic curve precisely. But something that should be understandable by anyone who's been, who's done some mathematics in high school. Elliptic curves are the solutions of some cubic equations like x cubed plus y cubed plus xy, et cetera, equal zero, something like that. And so they just can be drawn as curves in a plane. But that's not really what is most important for cryptography. It is important that we have a question that gives a computational representation for these objects. But what makes them useful for cryptography is the fact that the set of their points forms a group. So a group is a generalization of addition, like one plus one equals two. And on an elliptic curve, a point plus a point makes a third point, in a way that's described by mathematical equations. This is at the heart of pre-quantum cryptography, just because groups are a very good foundation for cryptography. And they have been for more than 20 years now in everyday communications when you use TLS. So yeah, these are elliptic curves. But if you don't know anything about mathematics, I can just say that elliptic curves are nice guys. And they each have a name. You can name, I don't know, John, Jake, Sarah. We mathematicians call this the Jane variant. And you just must know that it doesn't matter if Jake is looking at your face or looking at your back. So if you're looking at Jake's face or at Jake's back, it's always Jake. And that's the same with an elliptic curve. It doesn't matter which equation you use. The important thing is that at the heart, it's still the same elliptic curve. And this is something we call the Jane variant, which is a we attach to any elliptic curve. So OK, so we have a diversity of elliptic curves. And then we're identifying different elliptic curves by this quantity called the Jane variant, right? So what is special with this Jane variant? So usually in the cryptography that is currently deployed, we are just caring about one elliptic curve or maybe all these homomorphisms that are, or all the curves that map to this specific curve. But in the case of isogeny-based crypto, we have many, many curves, some of them identified by the Jane variant. So what is the connection here with the isogeny? Absolutely, absolutely. Yeah, first of all, there is an infinity of different elliptic curves of different Jane variants. But of course, we never deal with infinity in cryptography because we deal with finite structures. And so we will focus on a set, a family of elliptic curves like old elliptic curve cryptography, pre-quantum elliptic curve cryptography, as you said, just use one elliptic curve. So let's say everyone's been using the Armando curve for ages now. But yeah, isogeny-based cryptography is different because what we care about is not the elliptic curve and its point in itself. Actually, we don't care almost at all about the group structure of elliptic curves because otherwise we wouldn't be post-quantum. So we are doing something really different. And you can picture this as isogenies. Technically, there are morphisms of elliptic curves. So you can think of them as polynomial transformations between different equations of elliptic curves. But really, the way you can picture this is that there are connections between these elliptic curves. Like each elliptic curve, Armando, Luca, Ward, each has an address book. And in this address book, I may have Ward's phone number, and then Sarah's phone number, and some other connection with other elliptic curves. And you can picture every line in the address book as one connection, one isogeny. So what this is making is a network of connections, a graph of isogeny, pretty much the same way that when you use Facebook, you have a list of friends, and that's your social graph. Well, elliptic curves and isogenies make a graph, what we call an isogeny graph. And the main difference with Facebook is that, unlike Facebook, isogeny graphs are very good at keeping secrets. That's really awesome. So basically, yeah, the elliptic curves are having a very good time. They make the social network of them. They connect one to each other. And always, there is a way to keep connected. I mean, you can reach one to the other doing sort of hopes. And so it is true that, yeah, as you mentioned, that isogenies is that like, are these kind of connections, right? Like this kind of mathematical mappings that allow us to travel into this helps. So why, even if they have been studying for some time, why they become more relevant like in these days? So yeah, isogenies, of course, have been studied since around the 50s, 60s. Like the definition of isogenies itself was likely before World War II by Andre Weil. But they were mostly used as a tool for number theories, for studying the theory of elliptic curves. Of course, they were used in pre-quantum ECC too. They are a fundamental ingredient in point counting algorithms. But they were never used to make cryptography. It's only in the 2000s that we started understanding better the problems. And we realized that there is a hard problem with these isogeny graphs, which is I have a small address book with a few connections to a few curves which are near myself. But using this address book, then I can go to my friends' friends and then to my friends' friends' friends, et cetera, and I can make very long connections. And then there is a very hard problem if I find two elliptic curves in this graph, but I don't know how someone can go from one to the other. It's a hard problem to find a chain of connection between these curves. So this problem, as far as we know, is a difficult problem to solve for a computer, even for a quantum computer. And it's since the beginning of the 2000s that we've been working on various ways of exploiting this problem for making both key exchange and signatures. And it turns out that usually when you define schemes based on isogenies, you end up with very compact parameters, like your key exchange, your signatures will use very little bandwidth during the execution of the cryptographic protocol. And so this is a very interesting property for the competition, because in some cases, you may be very much constrained on bandwidth. And so far, isogeny-based systems offer the best performance in terms of bandwidth. Unfortunately, there's the opposite, there's the back side, that isogenies are extremely computationally expensive, much more than other candidates. And that's something that's not as good, of course. So it's always a matter of choosing the best compromise. Yeah, exactly. So in this case, there's a trade-off between space and time. So with isogeny-based crypto, we have like short sizes, but it's still the time for computing isogenies. It takes much more time than other approaches. So we know that in the competition, there are some finalists. So we are on round three, and then there are a few finalists. Unfortunately, there are no algorithms for signature schemes, which are based on on isogenies in the competition. I mean, of course, you have been authored several papers that proposes certain schemes. So I think one of the most famous is C-Sign or Skew-Sign. So can you tell us a little bit more about these schemes? Sure. So yeah, as you said, the only isogeny-based candidate in this competition is Psyche, which is a key encapsulation mechanism. So same thing as a case change, more or less. And the reason there are no isogeny-based signatures in the competition is that at the time the NIST competition started, we knew no efficient, by any measure, isogeny -based signatures. All signatures based on isogenies were both slow and large. So there wasn't a big interest in submitting those. And it was a big open problem for isogeny-based crypto for several years to find the compact isogeny-based signatures. So things started changing a few years ago, first with the discovery of C-Side and the associated signature scheme C -Sign, which were decently compact, comparable to lattice-based schemes, although they were pretty much slow. Ward, near me, made a huge contribution to this aspect of signatures with C-Fish, which is a scheme derived from C-Sign, but which is much more efficient. We're still talking about something that is as compact as lattice-based crypto, but that's definitely not as fast. So even for C -Fish, it's unclear why you would prefer that to lattice-based or other kind of signatures, which are better established, have been studied for longer. And now the last breakthrough, we reached it very recently with Antoine Allureau, David Coel, Christophe Petit, and Benjamin Veselovsky. We published this new signature scheme called C-Sign, which is by a fair margin, the most compact post -quantum signature scheme. It is size of signature plus probability combined are five to six times smaller than the best candidate currently in the NIST competition. So size-wise, this is very interesting. Performance-wise, it's definitely not great. We're working on it. We're slowly improving things, but it will take a while before this is usable. And also from a understanding the security perspective, we still have a lot of work to do. Yeah, that are two great variants of the algorithm. Depending in the application, there are some applications where we need to have very short sizes or signatures on public key, but there may be other applications in which we can relax this parameter and then, well, allow bigger signatures and then improve the time, the computation time. So yeah. So hopefully we can see these approaches in the next step for the NIST competition or in further research. Yeah, this is a topic that I also am very glad to take time to bring in your research and then try to see if there are some other optimizations. But now, so it's time to pass to what Gart is working and in which he's very expert on that. So we talk about isogeny-based crypto. Now we are moving to multivariate cryptography. So, well, I heard that this kind of cryptography is based like matrices, linear algebra. So I think most people are familiar with Gaussian elimination, how to solve a system of equations, but how do you make the connection with multivariate starting from that? Yeah. So multivariate cryptography is called multivariate cryptography because the main problem that we rely on is the problem where you're given a list of quadratic equations in multiple variables and the problem is to find a solution. And so yeah, this is a very natural problem. And it turns out that this is much harder than the degree one case. Like degree one, we know it can solve a polynomial time with Gaussian elimination, but as soon as you pass to degree two or higher, then this problem becomes very hard. Like we know it's NP -hard. We believe that it's exponentially hard on average, even for quantum computers. So this makes us a good problem to base post-quantum cryptography on. And so, yeah, the goal of multivariate cryptography is to try to make use of this hardness to turn it into a signature scheme or an encryption scheme. So OK. So basically, we started with something that is simple to doing, like finding solutions to a system of questions. Then we make it a little bit difficult just by using quadratic equations rather than linear equations. And but the other ingredient is that there is not the same number of equations and the number of unknowns, right? Yeah. So typically, if you're going to make a signature, then you're going to have a trapdoor function, like how RSA is a trapdoor permutation. But in multivariate signatures, you usually don't have a permutation, but you have some kind of surjective function. So usually, you go from like 100 variables to 50 variables or something. So this means that with very high probability, if you pick some element in your output space, there will be many, many preimages. So even though we don't have a permutation, we can still do signatures. Because if you want to sign some message in your outer space, you will be able to find some element that maps to this. But of course, you cannot do this with a random multivariate quadratic system because, as I just said, it's hard to find preimages. So somehow, you need to embed a trapdoor. And yeah, the way this is usually done is by picking some very simple system of equations for which you have some kind of algorithm to find solutions. And then you're going to mix this with some linear maps to make it look random. And then the attacker cannot find preimages, but you still can because you know the trapdoor structure. Yeah. So it is interesting that when one starts to read about multivariate, there are some like in general, in cryptography, there are some funny terms. So something that I was reading about oil and vinegar. So what is this about? Yeah. So oil and vinegar is one of the oldest multivariate schemes. It's almost older than I am. It was invented in 1997, I believe. So yeah, this is just a very simple approach to make a multivariate trapdoor that's just based entirely on linear algebra. The trapdoor structure is just some space on which polynomials vanish. And it turns out that this seems to work pretty well as a trapdoor. But yeah, the problem with oil and vinegar is that the public keys are quite large because the number of variables typically is like three times as large as the number of equations. So yeah, that means your public key is just this bunch of equations and they have a lot of variables. So there's a lot of coefficients like for every pair of variables, you have a coefficient. So just storing a public key is going to take a lot of memory. So yeah, oil and vinegar is a starting point for multivariate cryptography because it seems to be secure. But then there were a lot of approaches to try to make it more efficient and in particular to try to make the public key smaller because that's the main disadvantage. So approximately in terms of in the order of kilobytes or megabytes? Yeah, hundreds of kilobytes. Hundreds of kilobytes. Yeah. Yeah. Okay. Yeah. Just to make a connection, like for example, one scheme of like, let's say RSA or let's say RSA 2048 is just like 2k or at most, like depends on the compression. But yeah, so this is like many times there's a magnitude than what is currently used. So yeah, following that analogy of oil and vinegar, so you have this algorithm called Mayo. So can you talk a little bit about that? Yeah. So I already mentioned that the problem is that public keys are so big. And so with Mayo, we try to solve this by basically, instead of having a big system of equations as your public key, you can use a small system. But of course you cannot use a small system directly because it's too small. So we can just brute force and find solutions. But before you use this small system, you're going to basically take multiple copies of it and mix it together to make it look like one big system. So essentially you take your oil and vinegar, you'll make many copies and then you'll mix them together and then you get your Mayo trapdoor. So that's where the name comes from. And yeah, this seems to work pretty well in terms of reducing the key size because you can get a key size of only 600 bytes. But yeah, the problem is that we have this new hardness assumption that asks if you make a big system in this way by taking copies of one system and mixing it up. The problem is, is this as secure as solving this kind of system as hard as solving really random systems? And yeah, this is something that needs to be investigated. That sounds really cool. But one other thing that I, let me just switch a little bit. So one other contenders, which is based on multivariate is Rainbow. So you have in the past presented some tags that demonstrate that maybe the parameters of Rainbow are not sufficient to give a certain security, but very, very recently you have this new paper that where you can show that this actually practical. So can you tell us a little bit more about this? Yeah, so Rainbow is another variant of oil and vinegar that uses some strategy to reduce the number of variables. Yeah, this makes the scheme a bit more complicated and it means that there's a lot more attacks to explore. So yeah, that's what I did. And it turned out that there was some kind of attack that works really well. You can do it in practice to do a full key recovery in 53 hours. So yeah, it means that Rainbow unfortunately is not secure. And how is the extrapolation of this attack? I mean, I read that you can like just switch parameters and that's fine. Or I mean, that's fine for a weekend, but maybe you need like stronger security for that. Yeah. So the attack is still exponential, but you basically, what the attack does is it makes some kind of guess. And if the guess is correct, then you can solve, instead of having to solve the big Rainbow system, you can solve a much smaller system. But the system is still kind of large. So you're still, asymptotically for larger and larger public keys, you're still going to have a lot of trouble solving this smaller system. So yeah, this means you can, if you really want to use Rainbow, you can just use bigger parameters. But actually that's not really a useful thing to do because the key sizes and the signing times of Rainbow will be slower than oil and vinegar. So you will be better off to just use the much simpler scheme, oil and vinegar, instead of using those more complicated scheme, which is more expensive and which is much less understood in terms of security. Okay. Okay. I see. So, okay. So Rainbow came to, in order to like, trying to reduce some parameters, I mean, some parameters, sizes on the parameters. But now with this attack, so if we go back to, if we increase again, these parameters, so that makes us competitive as the oil and vinegar approach. Is that- Yeah. Less competitive, actually. Yeah. Oh, well, less competitive. And yeah. So, okay. So with that, so we're approaching to the end of the segment. So as you may know, so there is still like a lot of investigation on the post-quantum signatures. And here we have like some proposals that ones that are based on isogenies, others that are based on multivariate equation. And there are many others like those based on lattices. But what would be like your final words with respect to the competition? So are you ready to propose something like for the future? I think this is an open question. We are definitely looking forward to NIST announcements. And yeah, NIST has suggested that they may open again to the competition to new signature proposal because the pool has really shrinked a lot. Right now, like with Rainbow that there is only lattices and hash based signatures and maybe picnic. So it's a very small pool and doesn't really fit all use cases. So yeah, we're definitely looking with interest to the competition if it ever reopens. I'm sure we're not the only one thinking about it. Just yesterday on EPRIN, there was a new paper by several authors on cubic forms, a signature from cubic forms with interesting parameters. So yeah, I think we'll see lots of new ideas coming in the next months on signatures. So yeah, more interesting work to do for years to come, in my opinion, many years to come. Okay. Well, I'm going to thank you so much for sharing your time with us and see you next time. Thank you very much. Thank you.