A very unscientific guide to the security of various PQC algorithms
After publishing my series on UOV, one feedback I got was that my blog posts made people feel more confident in the security of the scheme, because “at least someone is looking into these things”. I don’t necessarily know if that is the takeaway I would make from my posts, but it gave me the idea to write my extremely subjective, and very much biased guesstimates for how secure I consider various approaches and problem families within PQC.
Since unfortunately I do not possess infinite wisdom or the gift of time travel, these are at best informed guesses, and I take no responsibility for being wrong on any of them.
## Generalities
There is a somewhat popular saying in cryptography “attacks only get better”. It’s a vacuously true statement, since obviously an attacker will always use the most powerful technique currently known, but I think it is also at least slightly misleading, implying that progress on attacks is not only inevitable, but also somewhat continuous.
Instead, what we are seeing is usually something like this: Initially, when a certain technique is first seriously discussed, attacks come in quickly and parameters have to be adjusted to account for them. With time, as our understanding of the space grows, we tend to refine those attacks, but it is a process of diminishing returns. It is possible that some novel mathematical technique starts a new spurt in advances in attacks, but importantly, there is usually no continuous improvement in attacks.
As an example, if we look at RSA, we first have the naive factoring algorithms such as trial division and Fermat’s method, which predate cryptographic use. Then, in the seventies, they get joined by the first major improvement in the space, Pollard’s rho. In the 80s, we get the quadratic sieve, as the first subexponential algorithm, joined by various lattice methods. Finally in the 90s, more than 30 years ago, we get the current best factoring algorithm, the general number field sieve, a refinement of the quadratic sieve, as well as further improvements on lattice techniques. Quantum algorithms also first enter the scene, with Shor’s algorithm. After that, successes die down substantially, mostly confined to relatively minor improvements to the general number field sieve.
This is not because we stopped working on factoring algorithms, but most of the effort shifted to other targets such as The Montes’ algorithm for factoring polynomials over discrete valuation rings.
If we look at elliptic curves, the story of attacks is even less exciting. There is, to this date, no known generic classical attack against elliptic curves that is better than a space-time traded off version of a brute force search. This is again not because the topic isn’t studied, elliptic curves are one of the most fundamental building blocks of algebraic geometry, and we know them in great depth. In fact, we know them well enough that we can even start to explain this lack of attacks: They are the most generic form of Diffie-Hellman out there.
All in all, this makes our job predicting the future of which algorithm is likely to break and which ones are likely to last, very, very hard. We are not looking at nice, predictable trends, but instead are mostly looking at a process that jumps in huge steps every few decades.
A different view to look at the same trends is to say that a scheme gets more trustworthy every time it survives an attack. From that point of view, attacks that fail teach us something about the scheme itself, adjusting our priors, making it more trustworthy. This is particularly true for attacks that tell us something fundamental about the underlying problem; the more general the attack, the more it can teach us why a scheme is resiliant.
But, now, without further ado, my personal list about how safe I think various approaches to PQC are, together with how familiar I am personally with the space and how much I think it has been studied.
## 1st Place: Hash-based Signatures
There isn’t much to say about hash-based signatures. They have a security reduction to the properties of the hash function used. Any signature scheme, and pretty much any public key encryption scheme requires a hash function somewhere in its construction, be it to compress the message, act as a random oracle, a key derivation function, or as a one-way function. If we cannot construct a secure hash function, we cannot do cryptography. In fact, if we consistently failed in creating secure hash functions, we would most likely live in a universe where P equals NP.
Hash-based signature schemes have reduction proofs that reduce their security to that of their underlying hash function. As such, hash-based signature schemes are at least as secure as any other asymmetric (or symmetric) cryptographic primitive. They have plenty of drawbacks, but lack of security is not one of them. While I haven’t studied them to great depth, there is also just not much to say about their security. They are secure.
Note that one of the drawbacks that some hash-based signature schemes have is the necessity to keep state (LMS/XMSS). While these schemes are as secure as their hash function if used correctly, the same is not true if the state is not managed correctly, i.e. if one-time-signatures are used more than once. While I have extremely high confidence in the mathematics of hash-based signatures, I also have extremely low confidence in our collective ability to not corrupt state once in a while.
## 2nd Place: Lattices
It is hard to overstate my confidence in lattices. General lattices, such as used in FrodoKEM, being broken is pretty much all but equivalent to proving P = NP, at which point all cryptography vanishes (since symmetric cryptography reduces to boolean satisfiability very easily), and it is time to find another career.
Lattices feature heavily in arithmetic number theory, as they arise very naturally when studying number fields. As such, lattice algorithms are actually far more central to mathematics than factoring algorithms. The number of problems an efficient lattice reduction algorithm solves is far higher than that of an efficient factoring algorithm. The main reason for that is that lattice problems are the simplest form of Diophantine equation problem, the linear Diophantine equation. You can see an example of this in one of my previous blog posts. This makes lattice reduction one of the most useful algorithm to calculate pretty much about anything in discrete mathematics.
Far from being constrained to just algebraic number theory, they also show up in algebraic geometry, in the description of Abelian varieties over the complex numbers. Or, as it turns out, p-adic numbers, as studied in my PhD thesis. Given how central they are to mathematics, I would be extremely surprised if someone, somehow, found a way to improve on generic lattice reduction. Even when it comes to quantum algorithms, lattice reduction is probably one of the most studied one, and so far, no generic improvement has been found, and several fundamental looking obstructions have been identified.
Lattices, as a mathematical object, have been studied pretty much for the same time as elliptic curves have been, since both arise from the same underlying questions about the circumference of an ellipsis. In this study, certain integrals arise naturally, defining a function that has two periods in the complex plane. In other words, functions that can be seen as defined on the complex numbers modulo a lattice. And the simplest of these functions , obeys a differential equation . In other words, and its derivative define a elliptic curve.
In cryptography, lattices also have been studied about as long as elliptic curve have. First as an attack, due to their mentioned ability to solve Diophantine equations, and soon after as cryptosystem themselves, by increasing the lattice rank to the point that the reduction becomes impossible to compute. The main reason you might not have heard of them before is their generally larger overhead compared to elliptic curves and RSA, making them unappealing in a world where elliptic curves and RSA are unbroken.
But we are not using generic lattices, we are specifically using module lattices. Those are the lattices coming from number field orders. A number field is a field extension of (such as adding the imaginary unit _i_ to the rational numbers), and an order in such a number field is a generalization of the integers (such as adding the imaginary unit _i_ to the integers, to obtain the number field order called the Gaussian integers). These number field orders are canonically lattices themselves, and any finitely generated module (I.e. vector space, but for rings) over them is again a lattice in a canonical way.
If there is a break of ML-KEM or ML-DSA, my money would be on exploiting this additional structure. However, even when it comes to this additional structure, it is very well understood and studied.
Looking at MLWE and NTRU specifically, both problems are deeply related to the p-adic rational reconstruction problem. In the case of MLWE, we need to switch to RLWE, but a number field order can be seen as a module over an order of some subfield, so this doesn’t really change the picture all that much.
So what is the rational reconstruction problem? Recall that, in order to attack LWE, we needed to find such that , which mainly boils down to describing the kernel, the solutions to . For RLWE (or indeed, for NTRU), we need to switch to a number field order, which we mainly do by replacing the capital with a lower case . We can, of course, without much consequence, switch the sign of the error term, and write , for the lattice we need to reduce. With a slight reordering, this is equivalent to . Since and are small in some metric, this means that what we are asking is given a fraction with bounded numerator and denominator, which is only known modulo some ideal (or more generally a number of finite places), find the numerator and denominator.
We all know this problem when we replace the finite places with infinite places, especially over , albeit usually less dressed up in formal mathematics lingo: This is the question of which fraction fits best with some given limited precision decimal expansion, such as the question of whether an output of 1.666 came from an actual result that was 5/3, or 1666/1000.
This problem (over finite places, i.e. modulo a prime) arises relatively naturally when studying number fields, and the only way we know for solving it is lattice reduction.
This is a very common pattern in arithmetic number theory, you usually take problems that arise there and reformulate them until you can express them as a lattice problem, and then proceed to reduce the lattice when the number field is small enough. The opposite, where you can use the number theoretic properties of the number field to say something about a lattice without reducing it on the other hand is very rare.
That being said, we are not using a random number field when it comes to lattice cryptography, but a fairly small set of very specific ones, which have properties that are not usually encountered in many number fields, such as having a class number of 1, and an easy to calculate group of units (up to some finite cofactor easy to calculate, that is, but still this is usually a hard lattice problem for a random number field, but is easy for the cyclotomic fields heavily ramified over 2 that we want for our cryptographic purposes).
That being said, even with these blemishes, when it comes to module lattice cryptography, we are talking about a very well understood and explored part of mathematics, that should be very safe to use for cryptographic purposes.
## 3rd Place: Codes
I know a lot less about codes then I do about lattices, I’ve always considered them as the smaller sibling of lattices. Both schemes fundamentally work via underdetermined linear systems, where the solution has certain special properties. Being small in the case of lattices, and having lots of zeroes (i.e. being small in the Hamming metric) in the case of codes. Their construction has many similarities, to the point that code based cryptography can be attacked with the same lattice reduction techniques that lattice cryptography has to deal with. Compared to lattices, codes are far less central to mathematics, but whether that is a good or a bad thing is hard to say. But really, I haven’t studied codes to any necessary detail to have much of an opinion on them, other than that they are fine, probably, at least as long as lattices are fine. They are also less efficient then lattices in pretty much all of their instantiations, and at least I do not know how to think of them as a more general mathematical problem (akin to the p-adic rational reconstruction problem that governs MLWE/NTRU).
## 4th Place: Isogenies
Now to a bit of a controversial placement: Isogenies. What, even though SIKE was broken? Yeah, well obviously I don’t place SIKE at 4th place, it’s somewhat lower, right above Vigenère ciphers, and only because the attack is more interesting.
SQISign on the other hand is a different story. The main reason to place it ever so slightly above multivariate cryptography in my opinion is that we much better understand the underlying hard problem and how it relates to the scheme itself.
I am not ashamed to admit that I have a bias towards pretty mathematics, and SQISign does some of the most beautiful mathematics I know off. That being said, the scheme is for now too slow to actually be used in practice, and while it can be reduced to the endomorphism problem, we cannot currently rule out that the endomorphism problem ends up being easy, especially given that it is far less central to mathematics then lattices are. It has been studied somewhat extensively, though, but I am somewhat worried that the best experts on the endomorphism problem in algebraic geometry are just now slowly even learning about the existence of isogeny based cryptography. After all, the SIKE attack is based on a theorem discovered in 1997, and yet wasn’t discovered until 2022, showing a huge gap between academic algebraic/arithmetic geometry and cryptographers working on isogeny based crypto.
## 5th Place: Multivariate Cryptography
I’ve written a whole series on Unbalanced Oil and Vinegar, probably the most basic of the multivariate schemes. Since then, a new attack has come out, leveraging wedge products. While the attack is far from catastrophic, it also feels very arbitrary, similar to the Kipnis–Shamir attack on Balanced Oil and Vinegar, it seems to me that we are missing something to really have a full understanding of the space.
Humorously enough, even before the paper, I had tried unsuccessfully to attack UOV using wedge products, more precisely I tried to figure out if there is a structure in the cotangent space that can be exploited, so the fact that wedge products were a meaningful attack vector is not surprising per se, but still, if we want to trust UOV, we need to, in my opinion, have a better understanding of what the hard problem here actually is.
It is easy to point to Gröbner bases here, but in my opinion the gap from generic Gröbner basis computation to the specific UOV problem is quite large. While all NP-complete problems necessarily reduce to each other, reducing to a Gröbner basis computation is one of the easier reductions, just like you can reduce a computer program to a boolean circuits satisfiability problem by literally translating the instructions, you can reduce a problem about polynomials to a Gröbner basis computation.
One thing that particularly stands out to me about Multivariate Cryptography is that variations that have tried to reduce the size of the public key ended up broken quite often. To me, there is something missing about fully understanding what makes this problem hard to fully trust it, but my progress in understanding the problem space better has at least given me a glimpse of why basic UOV should be secure.
That being said, realistically, I should place them above isogenies, mostly because we have had more survived attacks in this space, but this my list, and if it doesn’t contain at least one upsetting placement, it wouldn’t be very subjective now, would it?
## Bonus: Why RSA and Elliptic Curves both fall together
One question that I got asked recently was why RSA and elliptic curves, while looking so different as cryptosystems, are both susceptible to Shor’s attack, when all these other schemes barely spend a word talking about why Shor’s does not apply to them. While it is true that at first glance, RSA and elliptic curves do look very different, they are actually far more related than one might think, some of it is even already visible in classical attacks.
As I described in my post on why elliptic curves are really the only option for discrete logarithm problems, elliptic curves contain the multiplicative discrete logarithm as a subcase (at least if you allow for stable models). And for multiplicative discrete logarithm problems, we already have the same attacks working on RSA and DLOG. From that perspective it might be less surprising that an attack that is polynomial on RSA also solves ECC.
More concretely, the thing that Shor’s algorithm actually solves is the Abelian Hidden Subgroup problem: Given a group , a function is said to hide the subgroup of if is constant on each coset, but different for different cosets. In particular, if is a normal subgroup, this means that is defined and injective on . The hidden subgroup problem is Abelian if the group in question is Abelian. This is a bit of a mouthful, so let’s look at a trivial example first, using as our group and try to hide as a subgroup. A function would hide this subgroup if it has a different value on the cosets, for example, if the function was just the value of the integer modulo 3. For a slightly more interesting function, which actually meaningfully hides something, we can look at the world of variant Sudoko, where we often see the concept of a modular line or modular mirror or similar, which requires certain digits to have the same residue mod 3 (For example this one or that one). Solving these puzzles is usually done by coloring the corresponding digits in one of three colors, indicating the residue class mod 3. Importantly, it is (at least initially), not known which color corresponds to which residue class, which starts to show why the function is considered hiding this subgroup. Of course, even if you just mapped integers to colors, the hidden subgroup would still be pretty easy to find by anyone who can count to three (and importantly, solving the Sudoko has nothing to do with solving the hidden subgroup problem), but you can imagine that for a larger modulus, this becomes an actually hard problem.
While not necessary, it is very useful to know the classification problem for Abelian groups when looking at this question for Abelian groups in particular. All finitely generated Abelian groups can be written as the product , where . Knowing this means we know very well how, at least in theory, any subgroup of an Abelian group looks like, which is going to make the next bits a bit easier to grasp in their generalities.
Knowing that Shor’s algorithms can solve the Abelian Hidden Subgroup problem, and now knowing what the Abelian Hidden Subgroup problem is, all that is left to do is to show where the subgroup is hiding, for both RSA and elliptic curves. As discussed, elliptic curves are more or less the most generic of all DLOG groups, so we don’t really need to concern ourselves with the intrinsics of how elliptic curves work, and can instead just take a generic group G (and as a bonus, this allows me to use multiplicative notation without feeling dirty). In fact, let’s start with DLOG.
So given two elements , we are looking for such that . Instead of working with G as domain, we use two copies of , and define our function as . Since , this is equal to , i.e. it’s a linear transform on followed by a discrete exponentiation.
But the discrete exponentiation is a group isomorphism, so we can basically ignore it for the purposes of hidden groups, since the hidden group definition does not really care about the range of the function to begin with. As a linear function, it is easy to see where maps to the unit, namely exactly for vectors generated by .
Since is a group homomorphism, we can use the group isomorphism theorem to know that is constant on each of the cosets and injective on the quotient, i.e. hides an Abelian subgroup. Applying Shor’s algorithm, and obtaining a generator of this subgroup, we can recover k, since all elements of this subgroup have the from .
Reformulating RSA into an Abelian Hidden Subgroup problem is even easier: The security of RSA is build on the attacker not knowing the order of the group, since the order of is , from which we can recover n’s factors p and q easily. So how is order finding an Abelian Hidden Subgroup Problem? Just take a random element and define as . This function has the same result exactly for all the multiples of the order of a, in other words it hides as a subgroup of . And the order of an element is always a divisor of the order of a group, so we can use this to find factors of n.
Hidden Subgroup Problems are more general than just this, and are mostly just a framework to restate problems to. In fact, we can restate lattice reduction as a hidden dihedral subgroup problem. But importantly, quantum computers are really good at operating on Abelian groups, but have, at least so far, have not shown any success whatsoever on non-Abelian groups. This does make sense, given their construction, and gives us some data on why lattices have withstood quantum cryptanalytic attacks so far.
### Share this:
* Click to share on X (Opens in new window) X
* Click to share on Facebook (Opens in new window) Facebook
*
Like Loading...
