Why we cannot wait for better post-quantum signature algorithms

Post-quantum signatures: the state of play

The cryptographic foundations of the modern Internet—RSA and elliptic-curve signatures—are all vulnerable to sufficiently powerful quantum computers. While those machines don't exist yet, the consensus among researchers is that they're coming sooner rather than later. The good news is that post-quantum replacements are already being deployed: ML-KEM for encryption is now protecting the majority of traffic at Cloudflare, and ML-DSA for signatures was standardized by NIST in 2024 after an eight-year open competition.

But the signature side of the equation is less mature. ML-DSA works, but it has real drawbacks: signatures are much larger than their classical counterparts, and many of the protocol tricks we've built around RSA and ECC simply don't transfer. Better schemes are in the pipeline—NIST recently advanced nine candidates to the third round of its "signatures on-ramp" process, and a draft standard for FN-DSA (formerly Falcon) is expected imminently—but they won't arrive in time for the first migration wave. As Eric Rescorla put it in 2024:

You go to war with the algorithms you have, not the ones you wish you had.

The candidate landscape

The table above compares the third-round candidates with classical algorithms, the already-standardized ML-DSA and SLH-DSA, and FN-DSA, which is close to standardization. For most candidates, we list the variants most relevant to TLS at the 128-bit security level. CPU figures come from the signatures zoo, collected from round two submissions as of June 2026; expect adjustments as candidates refine their designs for round three. FN-DSA and SQIsign signing carry a ⚠️ because both are difficult to implement in a constant-time manner. LMS signing has a similar warning: secure signing requires maintaining state across signatures.

What jumps out immediately is that the classical Ed25519 remains the all-around best performer on nearly every metric—public key size, signature size, and signing speed. It's beaten only on verification time, and even there it's more than fast enough for most applications. That's a stark contrast with the post-quantum roster, which splits into two rough categories: "specialists" that match classical performance on one or two metrics but struggle elsewhere, and "generalists" like ML-DSA that don't dominate any column but have no fatal flaw either.

The specialists: algorithms with narrower roles

Not every post-quantum signature scheme aims to be a general-purpose replacement for RSA or ECDSA. Several candidates in NIST’s additional signature round are specialists — each with a distinctive trade-off profile that makes them appealing only in specific deployment contexts.

SQIsign: tiny signatures, slow signing

Judging purely by byte counts, SQIsign looks like a near-perfect elliptic-curve substitute. Signatures weigh in at 148 bytes and public keys at 65 bytes, both beating RSA-2048. But the trade-offs are steep.

SQIsign is the most complex algorithm under consideration, its signing and verification are comparatively slow, and making signature creation resistant to timing side channels is difficult and further degrades performance. That said, the picture has improved considerably since 2024, when no side-channel-secure implementation existed and verification was 20 times slower than it is today. The scheme has also been simplified, though it remains intricate.

Even with these gains, side-channel-secure signing will likely stay too slow for online use in TLS handshakes. For offline roles — CA signatures, DNSSEC — where verification speed matters more than signing speed, SQIsign may find a place.

Security is the other consideration. SQIsign is based on isogenies, the same mathematical terrain as SIKE, which was badly broken late in the first NIST competition. That history deserves nuance. SIKE’s collapse stemmed from specific concerns about torsion points — concerns that had already raised red flags and led to SIKE being deferred for additional review rather than standardized. SQIsign does not use torsion points and has no equivalent red flag. The best known attacks against SQIsign are generic brute-force, similar to the situation for well-chosen elliptic curves, and unlike RSA, lattices, and multivariate schemes, where attack algorithms have steadily improved. However, isogeny mathematics is rich, and the mathematical attack surface is far larger than for other families. SQIsign still seems more sound than the structured multivariate schemes discussed later.

SQIsign shows tremendous promise, but standardizing it now would be premature. The wishlist for its authors:

• Further reduce verification time, even at the expense of signing speed and signature size — signatures are already small enough.
• Make the timing side-channel-secure implementation the default, especially if signing gets faster and attracts online applications.
• Above all: simplify SQIsign.

UOV: minimal signatures, maximal keys

UOV (unbalanced oil and vinegar) dates to 1999 and delivers signatures of just 96 bytes. The penalty is a 66 kB public key — impractical for a TLS server certificate sent over the wire, but workable where keys are distributed out of band.

The WebPKI illustrates the trade-off. A typical browser trusts roughly one hundred root certificates and 30 certificate transparency logs. With UOV, those public keys sum to about 8 MB.

Root certificates are delivered out of band, so UOV could sign them. But cross-signing, where a root is used as an intermediate, becomes unwieldy with such large keys — and cross-signing becomes less attractive with any bigger post-quantum signature anyway. That pushes toward bundling more root certificates directly into clients, which favors UOV only up to a point. If the root set grows past a thousand, key material exceeds 66 MB — a substantial share of a browser download (Firefox 151, for reference, is about 90 MB).

Multivariate security history

Many UOV variants have tried adding mathematical structure to shrink the public key. These structured multivariate schemes — Rainbow and GeMMS among them — have been broken badly. UOV itself has a much better, though not spotless, security record.

The scheme’s early years included growing pains. The “U” in UOV stands for unbalanced — a fix to the 1997 oil-and-vinegar scheme where an equal number of oil and vinegar variables permitted an attack. The name descends from the quadratic system’s structure: terms are vinegar × vinegar and oil × vinegar, with no oil × oil products. From 2005 to 2020, no new attacks appeared against typical UOV parameters. That changed with the 2020 intersection attack, which removed about 30 bits of security from a then-proposed 128-bit parameter set — not fatal, since adjusted parameters fully mitigate it at a minor cost in key and signature size.

A larger shock came in 2025 with the idea of using wedges to attack multivariate schemes. The initial effect on UOV was only a few bits, but the concern was that the technique came from left field with unclear limits. That worry proved partially justified: follow-on attacks built on wedges reduced security by roughly 15 bits. It later became clear, though, that the wedges attack and its generalizations are special cases of existing attacks over truncated rings, making them more familiar than initially feared. Again, parameter adjustments mitigate the attacks with modest size increases.

This history is not unusual. Lattices experienced larger security reductions over 25 years before calming down — and lattice deployments today use conservative parameters well above 128 bits as hedges. UOV deserves the same treatment. Its signature size grows only linearly with the security level — 260 bytes even at 256-bit security. Public key size is cubic, reaching 446 kB at 256 bits. UOV, like most multivariate schemes, offers considerable flexibility in intermediate parameter sets.

UOV is a foundational scheme with narrow but real applications. A parameter set with margin above 128 bits — around 160 bits — would provide a reasonable hedge against future cryptanalytic advances.

QR-UOV: structure with modest gains

QR-UOV is a structured multivariate variant — like SNOVA and MAYO, it adds structure to UOV’s public key to reduce size. The gains are modest: at best 12 kB keys, though that parameter set has impractically slow verification, and realistic sets start at 24 kB.

Security-wise, QR-UOV is the only multivariate scheme that did not need to adjust its original round-one parameters after new attacks emerged. That is surprising, since any attack on UOV also applies to QR-UOV — but the natural QR-UOV parameters happen to blunt those attacks. On the other hand, several attacks already exploit QR-UOV’s specific added structure, and for some parameter sets these structure-specific attacks are the best known. That contrasts with MAYO, where no attack targets the added structure. QR-UOV’s signing and verification improved substantially since the last round but remain comparatively slow. All told, QR-UOV is a harder sell: it introduces exploitable structure without driving key sizes down to broadly useful dimensions.

Hash-based signatures

Stateful hash-based schemes

The first standardized post-quantum signature algorithms were the stateful hash-based LMS, HSS, and XMSS(MT). They have very small public keys and, for many parameter sets, signatures far smaller than ML-DSA-44. Their security rests on hashes — well understood and already a cryptographic cornerstone — making them a highly conservative choice that needs no extra security margin.

The catch is twofold. First is the state itself. These schemes build signatures from one-time keys collected into Merkle trees. The signer must track which one-time keys have been used, often just a counter. Reuse the same one-time key for a different message, and anyone with both signatures can likely forge signatures on arbitrary messages. Managing state correctly demands care: storage updates before releasing a signature, avoiding restoration of old state from backups, and agreeing on state handling when exporting or importing private keys. As Adam Langley noted years ago, the state is a serious foot-cannon.

Second, the most competitive parameter sets limit the number of signatures. The 1,112-byte signatures listed above support only about a million signatures. The trade-offs between signature size, speed, and signer capacity can be explored with a purpose-built calculator.

Together these constraints leave stateful hash-based signatures with a small niche: signers that can maintain state, where signature size matters, and a hard signing limit is acceptable.

SLH-DSA: conservative, but large and slow

SLH-DSA is a hash-based scheme that avoids the signing limit and the state problem. Instead of tracking one-time keys, it makes the pool of possible keys so vast that random selection makes collisions vanishingly unlikely. It also substitutes few-time-signature keys for one-time keys, degrading gracefully under occasional reuse. The cost is substantial: the size-optimized variant produces 8 kB signatures, and the signing-optimized variant is even slower than SQIsign.

A smaller SLH-DSA variant

NIST has proposed standardizing an additional SLH-DSA parameter set with much smaller signatures — 3.8 kB — still larger than ML-DSA-44, though combined public key and signature size is close. That parameter set can create only about 16 million signatures before security degrades. It is tuned for fast verification at the expense of very slow signing.

Why choose SLH-DSA?

The argument for SLH-DSA is conservative security. For a long-lived key that is hard to replace, the choice may make sense if the application tolerates the large signatures and slow verification (or the very slow signing of the new parameter set). Two caveats apply. First, systems should design around replaceable key algorithms rather than burning in one scheme. Second, most use cases — TLS, for example — need key agreement, not just signatures. There is no hash-based key agreement; at some point lattice-based assumptions will be needed regardless.

FN-DSA: attractive numbers, subtle signing

FN-DSA-512 (formerly Falcon) beats ML-DSA-44 on most metrics: faster verification, smaller public keys, and far smaller signatures at 666 bytes. Signing is three times slower, but still 25 times faster than RSA-2048, and FN-DSA is already selected as FIPS 206. Why is it not a general-purpose choice?

The difficulty lies in secure signing. FN-DSA is most naturally implemented with hardware-accelerated floating-point arithmetic — a first for a cryptographic standard. Side-channel-safe floating-point code is subtle and not robust: an FPU-based implementation that is safe on one processor may not be on another. Emulating floating-point operations avoids that risk but is about 20 times slower, on par with RSA-2048. Recent work on fixed-point arithmetic offers a safer alternative that is far faster than emulation. But that presumes implementations will actually take that path — and anecdotally, every conference talk comparing FN-DSA benchmarks so far has failed to clarify whether floating-point emulation was in play.

Floating-point also complicates test vectors. a+(b+c) and (a+b)+c are only approximately equal, so the specification must pin down exact operation ordering to produce meaningful vectors. Similarly, a*b+c can be computed as two operations or with fused-multiply-add, which rounds once instead of twice — faster but slightly different in result, and compilers typically use FMA automatically where supported. Even the reference implementation computes a norm via Parseval’s theorem, mathematically exact but slightly off in floating-point. Test vectors remain the most reliable bug catcher in practice, and their utility depends on implementation determinism.

There is a deeper problem: two deterministic signatures from slightly different implementations of the same private key can leak parts of that key. FN-DSA avoids deterministic signatures by adding a randomizer — but this creates tension with testing, which requires a deterministic interface that should not be used for real signatures.

How NIST handles this specification wiggle room will be a point of debate. One possible silver lining: if NIST generates CAVP test vectors from the fixed-point implementation, the riskier floating-point paths would fail those vectors, steering implementations toward safer choices. Other sharp edges are documented elsewhere, but the core point is that FN-DSA is complex. NIST needed years just to draft the standard, and finalization plus library support will take longer still. FN-DSA is further from production than its byte counts suggest.

For those still tempted, one last concern: FN-DSA-512 targets 128-bit security, while ML-DSA-44 offers 160 bits. If lattice cryptanalysis improves, there is no intermediate step — the next level is FN-DSA-1024 at 256 bits, with double the key sizes, signature sizes, and runtimes. Even so, an FN-DSA-1024 signature is still half the size of an ML-DSA-44 one, and combined public-key-plus-signature size differs by only 20%.

It bears repeating that all of FN-DSA’s complexity sits on the signing side; verification is entirely straightforward.

General-purpose candidates: security and flexibility

Beyond the specialized designs, there is a broader category of algorithms intended as drop-in replacements for ML-DSA. These candidates split into two philosophical camps: those built around a single, well-scrutinized hard problem, and those that add mathematical structure to speed things up at the cost of additional security assumptions.

HAWK and the problem of new assumptions

HAWK is a structured-lattice hash-then-sign scheme similar to FN-DSA in many respects, with comparable signature and public key sizes, and like FN-DSA it skips a middle security level. Its main selling point is fast signing that avoids floating-point arithmetic. The catch is that HAWK rests on a new security assumption, the lattice isomorphism problem (LIP). Since HAWK's introduction in 2024, the outlook for LIP has darkened: first an attack on totally real number fields (not used in HAWK), then an extension to a broader class of fields in 2025. A June 2026 paper suggests the attack might extend further to HAWK itself, though an error in that paper makes its impact unclear. The trend is nonetheless worrying. Even without the attacks, HAWK's extra assumption keeps it from displacing FN-DSA, while its practical edge—especially without a middle security level—does not match the structured multivariate candidates. It also adds little diversity in security assumptions, which NIST is actively seeking.

Proof-of-knowledge designs: FAEST, MQOM, and SDitH

FAEST, MQOM, and SDitH share a common blueprint: the public key is an instance of a hard problem, the secret key is the solution, and a signature is a zero-knowledge proof that the signer knows that solution while binding the message into the proof.

• FAEST uses AES as the hard problem: the public key is the AES encryption of a known plaintext under a secret key.
• MQOM relies on the Multivariate Quadratic problem, which is more conservative than the hidden-structure assumptions behind the multivariate signature schemes. Its public key is a system of quadratic equations, the secret key a solution.
• SDitH uses Syndrome Decoding for random linear codes, a problem related to code-based schemes that were eliminated in the third round of the original NIST competition.

Most signature schemes are zero-knowledge proofs underneath—ML-DSA, SQIsign, and Ed25519 qualify—but those proofs are not general-purpose. ML-DSA's proof uses the specific algebraic structure of the LWE problem in its key and cannot prove arbitrary statements without resorting to entirely different proof systems that produce signatures on the order of 50kB. FAEST, MQOM, and SDitH do not have this limitation. Their proof systems are modular: FAEST can swap in MQ as the hard problem to produce KuMQuat, a more efficient hybrid, and MQOM can just as easily use AES.

That flexibility is valuable for two reasons. First, it decouples the signature scheme from the structure of the underlying problem. Designers can choose a very conservative assumption, like the hardness of AES, or a problem like MQ that is NP-hard and free of the hidden subspaces that make UOV variants vulnerable to intersection and wedge attacks. Second, a general zero-knowledge proof system enables more than plain signatures—blind signatures and anonymous credentials become possible.

There is a trade-off: proof size grows linearly with the statement being proved. These schemes are not succinct in the way STARKs or LaBRADOR are, and for large statements those asymptotically better tools win easily. It is another case where a non-optimal asymptotic approach is the better practical choice.

Apart from the chosen hard problem and the security of the hash function, these three schemes rely on no additional assumptions, making FAEST about as conservative as SLH-DSA. The differences between them have narrowed over time. MQOM's proof system is simpler than FAEST's but performs worse—KuMQuat (FAEST's proof system with MQ) outperforms MQOM outright. Against SLH-DSA, all three have variants that beat any standardized SLH-DSA parameter set by a wide margin, though SLH-DSA's verification is easier to implement.

Comparing with ML-DSA-44 is more nuanced. These schemes offer a smooth trade-off between runtime and signature size. KuMQuat, for instance, can be tuned for signatures somewhat smaller than ML-DSA-44 at the cost of substantially longer signing and verification, or it can match ML-DSA-44's speed with larger signatures while keeping the public key plus signature size broadly comparable.

Further performance gains are likely, but these schemes will not beat ML-DSA as dramatically as some other categories. Their appeal is conservative security and, above all, extensibility to applications like anonymous credentials. To highlight that flexibility, each scheme in this category should publish benchmarks using a different underlying hard problem.

MAYO versus SNOVA: two paths to structured multivariate

MAYO and SNOVA both add structure to UOV's public key to shrink it, but they diverge in philosophy. SNOVA makes aggressive structural bets to maximize performance; MAYO is deliberately conservative.

SNOVA's headline numbers are impressive: a 248-byte signature (smaller than RSA-2048) with a 1kB public key, the best public key plus signature size of any post-quantum candidate except SQIsign, and strong runtime. MAYO is competitive in its own right. MAYOone has the fastest verification of the group and 454-byte signatures that beat FN-DSA-512, HAWK-512, and RSA-4096, though combined with its 1,420-byte public key it trails FN-DSA and HAWK slightly. MAYO regains the lead when security margin is the priority: FN-DSA and HAWK must jump from their missing middle level all the way to 256-bit security, whereas MAYO adds incremental security with only small size increases.

Both schemes allow a signature/public key size trade-off, letting users shrink signatures further when public keys can be transmitted in advance. Pushed to the extreme, MAYO degenerates into UOV.

The security picture separates the two sharply. MAYO layers a "whipping" structure on UOV, so any attack on UOV also applies, but no attack has been found against the whipping structure itself. The worst case so far is that some UOV attacks have impacted certain MAYO parameter sets more heavily than typical UOV configurations, because of the UOV parameter choices natural to MAYO.

SNOVA's record is different. Its specific structure has been broken repeatedly, and each time the team has responded not by adjusting parameters but by redesigning the structure—each iteration getting faster. That pattern has continued since last year's analysis, while MAYO's design has stayed stable. Compounding the concern, SNOVA's structure can be viewed as a special case of MAYO's whipping map, meaning any MAYO-specific attack would also apply to SNOVA, but not the reverse. Given the ongoing progress in multivariate cryptanalysis, NIST's expectation of an additional round before standardizing a multivariate scheme seems prudent. Whether SNOVA would be ready then is unclear; MAYO's design, so far, has matured well.

What the Timeline Looks Like

Looking at how long it took ML-DSA to go from selection to deployment gives a sense of what lies ahead for the new candidates.

After NIST selected Dilithium to become ML-DSA, drafting the proposal took a year, and the final standard another year beyond that. Protocol integration added another year for certificates. Software support followed, though implementation work did start before the standard was final. The TLS integration is done, but the RFC won't be out for a couple of months; OpenSSL even added ML-DSA support before the IANA codepoints were assigned. What's still missing is agreement on hybrid signatures in TLS, for which no IANA codepoints exist yet.

Projected Availability

If the FN-DSA draft is released today and progresses at the same rate as ML-DSA, early software support might appear in 2029, but not significant deployment. Given how long the draft standard has taken, wide availability before 2033 is unlikely.

The cryptanalysis progress on multivariate schemes gave NIST pause, with an expectation of another two-year round. Since multivariate schemes are relatively easy to implement, a NIST standard might appear in 2031, with product availability no earlier than 2034.

NIST is more confident in SQIsign than multivariate, but the scheme is difficult to standardize and implement. Large changes seem likely for the third round, possibly requiring a fourth. Wide availability before 2035 is unlikely either way.

HAWK sits awkwardly between FN-DSA and structured multivariate candidates. Standardization seemed unlikely even before the recent cryptanalysis progress; product availability before 2034 isn't expected.

The proof of knowledge candidates — MQOM, SDitH, and FAEST — have seen dramatic improvements across rounds. If that rate of change holds, another round will be needed. If the schemes are stable, a proof of knowledge algorithm could be the first new NIST standard in 2030, though it likely won't outperform ML-DSA dramatically. It would still be valuable for anonymous credentials and other primitives beyond signatures.

Waiting Is Not an Option

Cloudflare's migration goal is 2029, and none of these signatures will be ready in time. Regulator deadlines, ranging from 2030 to 2035, didn't account for recent progress and will likely be adjusted, as seen with the June 2026 US executive order setting a 2031 deadline.

Even without changed deadlines, waiting wouldn't make sense. Deploying post-quantum signatures in 2034 to beat a 2035 deadline isn't enough — you can't upgrade a large system all at once. A transition period with both post-quantum and traditional signatures creates downgrade attack surface. The straightforward fix, disabling classical cryptography, takes time and isn't even feasible for distributed systems like the WebPKI.

Why These Algorithms Still Matter

Public key cryptography has been woven into digital society for 50 years, and the migration window is short. Most upgrades are straightforward: drop in post-quantum cryptography. But some cases are fundamentally harder. ML-DSA's size is a problem in certain contexts, and while the post-quantum WebPKI is being re-engineered to perform better than today's version, that won't happen for every system in time. Some will accept performance costs; others will need compensating controls like restricted access, tunneling, or monitoring. Smaller post-quantum signatures would let those controls be removed.

The NIST competition has also advanced post-quantum cryptography beyond basic primitives. Anonymous credentials, PAKEs, and threshold signatures lack readily available post-quantum variants. FAEST is the clearest example: its underlying VOLEitH machinery can be combined with a multivariate scheme like MAYO to build efficient post-quantum anonymous credentials. Without the signatures competition, that technology wouldn't be as developed and vetted.

Many candidates hint at uses beyond signatures. Those indirect applications deserve more attention — but first, the immediate task is staying secure during the migration itself.