量子コンピュータによる暗号解読リスクに備え、より良い署名アルゴリズムを待てない理由

RSA and ECC, cryptographic algorithms that we’ve all relied on for decades, are vulnerable to the attack of sufficiently advanced quantum computers. Such quantum computers do not exist yet, but they seem to be coming sooner than expected. Luckily, the solution is already available: migrate to ML-KEM encryption and ML-DSA signatures, which are designed to be resistant to quantum attack. They were standardized in 2024 by the U.S. National Institute of Standards and Technology (NIST) after an eight-year open international competition.

The migration to post-quantum cryptography is in full swing now. At the time of writing, the majority of traffic handled by Cloudflare is already using ML-KEM encryption, and is thus secured against the threat to data posed by harvest-now-decrypt-later attacks. But encryption is only one part of the equation: to be fully secure against quantum computers capable of breaking classical cryptography, we aim to deploy post-quantum signatures to protect authentication systems from unauthorized access. We are targeting 2029 for Cloudflare to be fully post-quantum secure.

ML-DSA, the best all-around post-quantum signature scheme standardized today, has its downsides: it’s much larger on the wire, and many tricks we were able to perform with RSA and ECC simply cannot be done with ML-DSA. There are better post-quantum signature schemes on the horizon: last month, NIST announced that it is advancing nine post-quantum signature schemes to the third round of the “signatures on-ramp”. And a draft standard for FN-DSA (née Falcon), which was picked from the previous competition, is expected imminently.

We have been very interested in advances in post-quantum signature algorithms, and wrote about the progress in 2021, 2022, 2024, and 2025. In this blog post we’ll treat you to the latest developments in great detail.

But first we have to deal with the elephant in the room: These new signature algorithms will not be ready in time for the PQ transition — not even close, as we will see later on. The problem is arriving too soon for us to wait. ML-DSA is available today, and it will have to do for the first migration. As Eric Rescorla wrote in 2024:

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

Nonetheless, the search for better post-quantum signature algorithms is crucial for several reasons, and we firmly believe it is still the best use of NIST’s limited resources.

Let’s have a look at the signature algorithms in detail. After that we’ll look at the timeline for their availability, and the reasons why we still need them.

The signature algorithms

In the table below, we compare the candidate signature algorithms that progressed to the third round (marked by 🤔), with classical algorithms vulnerable to quantum attack (marked by ❌), and the post-quantum algorithms that are already standardized ( ✅) or soon will be (📝). Each candidate proposes several variants. We list the most relevant variants to TLS, the protocol used to secure connections on the Internet. To explore all variants, check out Thom Wigger’s signatures zoo.

Sizes (bytes)

CPU time (lower is better)

Family

Name variant

A

Public key

Signature

Signing

Verification

Elliptic curves

Ed25519

❌

32

64

0.15

1.3

Factoring

RSA 2048

❌

272

256

80

0.4

Lattices

ML-DSA 44

✅

1,312

2,420

1 (baseline)

1 (baseline)

Symmetric

SLH-DSA 128s

✅

32

7,856

14,000

40

SLH-DSA 128f

✅

32

17,088

720

110

SLH-DSA 128-24

📝

32

3,856

7,000,000 ⚠️

4

LMS M24_H20_W8

✅

48

1,112

2.9 ⚠️

8.4

Lattices

FN-DSA 512

📝

897

666

3 ⚠️

0.7

Lattices

HAWK 512

🤔

1,024

555

0.25

1.2

Proof of knowledge

MQOM L1-gf16-fast-5r

🤔

60

3,280

8

20

SDitH SDitH2-L1-gf2-fast

🤔

70

4,484

15

40

FAEST EM-128f

🤔

32

5,060

4.2

9

Isogeny

SQIsign I

🤔

65

148

300 ⚠️

50

Multivariate

MAYO one

🤔

1,420

454

2.1

0.4

MAYO two

🤔

4,912

186

1.1

0.8

QR-UOV

I-(127 156 54 3)

🤔

24,225

200

9.3

20

SNOVA (24,5,4)

🤔

1,016

248

1.2

1.7

SNOVA (25,8,3)

🤔

2,320

165

1

1.5

SNOVA (37,17,2)

🤔

9,842

124

0.8

1.3

UOV Is-pkc

🤔

66,576

96

0.3

2.4

UOV Ip-pkc

🤔

43,576

128

0.3

2

A few more remarks on this table: Most candidates have multiple variants in every security level. We show the most relevant variants for TLS at the 128-bit security level, the gold standard for security. CPU times are taken from the signatures zoo in June 2026, which collected them from the round two submission documents and later advances. Candidates are allowed to make changes for the third round, which will influence these numbers. Some will improve (both in compute and size), whereas others will regress to counter new attacks. Check out the zoo for the latest numbers. We marked FN-DSA and SQIsign signing with a  ⚠️️, as both are hard to implement in a fast and timing side-channel secure manner. LMS signing has a ⚠️, as secure LMS signing requires keeping state across signatures, and the listed signing time assumes a 32MB cache. The 128-24 variant of SLH-DSA is marked with a ⚠️️ as it’s meant to create fewer than 224 signatures.

No "all-star" algorithm

One thing that stands out immediately is that the quantum-vulnerable elliptic curves signature algorithm Ed25519 is by far the best all-around choice (ignoring its quantum vulnerability): it has the best numbers in almost every single metric, including public key size, signature size, and signing time. It’s only beaten on verification time, but it’s more than fast enough for the vast majority of applications.

This is quite different than the roster of post-quantum algorithms. Instead of a single "all-star" algorithm, we have roughly two categories of schemes: the "specialists" that approach our trusty elliptic curve signatures on some metrics, but are problematic on others, which make them great in the right deployment scenario. Then there are the “generalists”, such as ML-DSA, which don’t perform as well as elliptic curves on all metrics, but so far as downsides go, are pretty balanced.

Specialists

Let’s start with the specialists.

SQIsign: small signatures / slow signing

If you just look at the bytes on the wire, then SQIsign looks like an almost perfect drop-in replacement for elliptic curve cryptography. With signatures of 148 bytes and public keys of 65 bytes, it beats RSA-2048. Unfortunately there is no free lunch: SQIsign has three weak points. First, it’s the most complex algorithm on the docket. Secondly, its signature creation and verification is quite slow. Finally, it’s difficult to implement signature creation in a timing side-channel secure way and doing so comes with a performance penalty to boot.

That doesn’t sound great so far, but it was much worse: when we had a look back in 2024, there was not yet any timing side-channel secure implementation and signature verification was 20x slower. Furthermore there has been welcome progress on simplifying the scheme.

Despite these dramatic improvements, it is unlikely (side-channel secure) signing will be fast enough in the foreseeable future to be used in typical online cases such as the TLS handshake. However, for offline cases, such as CA signatures or DNSSEC, where it’s the verification time that’s more important than the signing time, SQIsign might have an application.

But the topic we should really discuss is security. SQIsign is based on isogenies. Rather famously, SIKE, another algorithm based on isogenies, got broken badly in a late stage of the first NIST PQC competition that standardized ML-DSA. SIKE is often brought up as a cautionary example showing that post-quantum cryptography could break suddenly. This requires some nuance. First, there were already concerns about SIKE’s security, and in particular the torsion points that led to the break. Because of these concerns, SIKE was not selected for standardization, but deferred to an additional round of evaluation before it was broken. (Indeed, this is an example of the NIST process working well.) SQIsign doesn’t use torsion points, and there is no similar concern as there was for SIKE.

One other notable security property is that the best known attacks on SQIsign are generic brute force, just like with classical attacks on well-selected elliptic curves. This is quite different from RSA, lattices, and multivariate where the attack algorithms have been slowly improving, pushing the parameters towards bigger signatures. Nonetheless, the mathematics behind isogenies is very rich, and compared to the other  algorithms, there is a lot of mathematical attack surface. Still, its security seems more sound than the structured multivariate algorithms we’ll discuss later.

SQIsign is an algorithm with tremendous potential. It’d be a shame to standardize it too early. To the authors, we’d like to share the following wishlist:

Ideally verification time is decreased even further, even if this trades off against signing time and signature size: SQIsign signatures are already small enough, and offline signing time has some slack anyway.

The timing side-channel secure implementation should be the default, especially if signing time is decreased further, which would tempt some online signing applications.

But above all, our wish is for SQIsign to be simplified.

UOV: tiny signatures / huge public keys

UOV (unbalanced oil and vinegar) is a classic multivariate signature algorithm originally proposed in 1999. It has tiny signatures: only 96 bytes. The trade-off? A huge public key: 66kB. That wouldn’t help for a TLS server certificate, whose public key is transmitted over the wire when setting up a connection, but it would be a help for cases where the public key is predistributed.

Let’s take the WebPKI as an example. A typical browser trusts about a hundred root certificates and 30 certificate transparency logs, whose public keys would add up to about 8MB when using UOV.

image

The public keys and signatures in a typical TLS connection.

Since the root certificate is transmitted to clients out of band, one idea is to use a UOV signature there. But this is not a slam dunk; because of its size, a UOV root certificate would be impractical to be cross-signed where the root is used as an intermediate. At the same time, cross signs and intermediates become less attractive anyway with any larger post-quantum signatures. This encourages more root certificates to be included directly with clients. This would again favor UOV, but to a point: if the number of root certificates grows above a thousand, we’d be dealing with more than 66MB of key material, which would make up a substantial portion of the browsers’ download size (e.g., 90MB for Firefox 151.)

Multivariate security

What about the security? Over the years, many variants of UOV have been proposed that use some extra mathematical structure to reduce the size of the public key. These structured multivariate schemes have had a spotty track record with schemes such as Rainbow and GeMMS being broken quite badly. It is important to distinguish thes