Why the migration is happening

Quantum computers exploit superposition, interference and entanglement to outperform classical machines at a narrow set of problems — simulating nature, for instance, which matters for materials development. They are not general-purpose replacements: at most tasks they perform worse than ordinary computers, and are better understood as specialised accelerators, akin to GPUs.

Breaking the key cryptography in widespread use today happens to fall into that narrow set. Post-quantum cryptography is the answer: algorithms designed to resist quantum attack. Present-day quantum machines are too weak to crack real-world keys, but that is no reason to wait, because encrypted traffic can be harvested now and decrypted later.

If nothing else drives the point home, the deployment numbers do. Nearly two percent of TLS 1.3 connections established with Cloudflare are already secured with post-quantum cryptography, and double-digit adoption is expected by the end of 2024. Apple announced in February 2024 that iMessage will be post-quantum secured before the year is out, and Signal chats already are.

Fraction of TLS 1.3 connections established with Cloudflare that are secured with post-quantum cryptography. At the moment, it’s more than 99% from Chrome.

Fraction of TLS 1.3 connections established with Cloudflare that are secured with post-quantum cryptography.

The field has moved quickly: Kyber has been renamed ML-KEM, new candidates have entered the signatures onramp, and SIKE was catastrophically broken. Material written three years ago is already stale.

Counting qubits tells you little

Annual headlines about record qubit counts are misleading. Quantum computers are analogue devices, and noise always intrudes on the computation, so a raw qubit number says little about capability. The technology matters as much as the count.

Silicon-based machines scale well and execute instructions quickly, but their qubits are noisy. That is not fatal: quantum error correcting codes can turn tens of millions of noisy silicon qubits into a few thousand high-fidelity ones, potentially enough to break RSA. Trapped-ion machines are far quieter but have proven harder to scale; a few hundred thousand of those qubits could conceivably end RSA.

State-of-art in quantum computing measured by qubit count and noise in 2021, 2022, and 2023. Once the shaded gray area hits the left-most red line, we’re in trouble. Red line is expected to move to the left. Compiled by Samuel Jaques of the University of Waterloo.

State-of-art in quantum computing measured by qubit count and noise in 2021, 2022, and 2023. Once the shaded gray area hits the left-most red line, we’re in trouble. Red line is expected to move to the left. Compiled by Samuel Jaques of the University of Waterloo.

Qubit count and noise are only the beginning. On many machines only adjacent qubits can interact — a constraint most estimates ignore. Conversely, an algorithm tailored to one specific machine can beat a generic one by a wide margin. Since nobody knows what a future machine will look like, current estimates are probably off by at least an order of magnitude.

Timelines and the two migrations

When could RSA-2048 fall? In a 2022 survey, more than half of the experts polled considered it more likely than not that a cryptographically relevant quantum computer would exist by 2037. Official plans are similarly aggressive. The NSA intends to finish its own migration before 2033 and will start preferring post-quantum ready vendors for many products in 2025; the US government as a whole aims to be done by 2035.

NSA timeline for migrating third-party software to post-quantum cryptography.

NSA timeline for migrating third-party software to post-quantum cryptography.

Industry conferences on the migration draw notably heavy participation from the automotive sector — unsurprising given a median car age of 14 years, large sums at stake, and cryptography embedded in vehicles that cannot easily be upgraded after sale. Whether the machine arrives in 2034 or 2050, it will be too soon. Cryptography's success means it is now everywhere, from dishwashers to pacemakers to satellites. Most upgrades fit naturally into product lifecycles; a long tail of hard, costly ones will remain.

Symmetric cryptography is already safe

Because difficulty and urgency differ sharply by primitive, most organisations face two migrations: key agreement and signatures/certificates. Start with what needs no work. On a typical website visit, the workhorse is a symmetric cipher such as AES-GCM, where browser and server share a key for encrypting and authenticating messages. AES-GCM is already post-quantum secure.

A common misconception holds that Grover’s algorithm forces us to double symmetric key lengths. Examined closely, the algorithm is not practical. NIST’s definition of its post-quantum security levels is telling: each level requires a scheme to be as hard to break with a classical or quantum computer as a specified existing symmetric cipher.

Level Definition, as least as hard to break as … Example
1 To recover the key of AES-128 by exhaustive search ML-KEM-512, SLH-DSA-128s
2 To find a collision in SHA256 by exhaustive search ML-DSA-44
3 To recover the key of AES-192 by exhaustive search ML-KEM-768
4 To find a collision in SHA384 by exhaustive search
5 To recover the key of AES-256 by exhaustive search ML-KEM-1024, SLH-DSA-256s

NIST PQC security levels, higher is harder to break (“more secure”). The examples ML-DSA, SLH-DSA and ML-KEM are covered below.

Doubling key lengths is well intentioned. Symmetric scaling is cheap — twice the bits typically costs well under twice the price — so the advice is simple and closes any theoretical gap. But insisting on AES-256 logically pushes you to NIST PQC level 5 for public key cryptography as well, and public key schemes scale badly: moving from level 1 to level 5 typically more than doubles both data usage and CPU cost depending on the scheme. Deploying post-quantum signatures at level 1 is already painful; at level 5 it is problematic. Nor is symmetric migration always easy — where it means replacing hardware, it can be costly — and an organisation that cannot finish migrating in time cannot afford to spend effort on longer keys.

Key agreement: urgent, but tractable

Symmetric ciphers alone cannot bootstrap a shared key with a first-time visitor, since a key sent in the clear is visible to every eavesdropper. Key agreement solves this during the TLS handshake. Almost all traffic today relies on X25519, a Diffie–Hellman-style mechanism whose security Shor’s algorithm destroys outright. Anything secured with Diffie–Hellman today can therefore be stored and decrypted later, which makes upgrading key agreement urgent. The consolation is that post-quantum key agreement is comparatively straightforward to deploy.

Signatures: less urgent, much harder

Key agreement leaves a gap: it does not establish with whom the key was agreed. An attacker in the middle could run separate key agreements with browser and server and re-encrypt the traffic. Authentication closes this. A web server presents a certificate signed by a certification authority vouching that the certificate's public key belongs to the named site, and then signs the handshake and shared key with the matching private key.

RSA and ECDSA are the traditional signature schemes, and Shor’s algorithm lets a quantum attacker forge either. Any connection relying on a signature scheme that is not post-quantum secure can thus be hijacked by a MitM. This is an active attack: a connection is unaffected unless the attacker is present as the handshake happens. That makes the signature migration appear less urgent — everyone need only be migrated by the time the cryptographically relevant machine arrives. In practice, post-quantum signatures are much more difficult to migrate and will demand more time.

Post-quantum cryptography did not begin as a response to quantum computers. Feynman and Manin independently proposed quantum computers around 1980; Shor's algorithm attacking public key cryptography followed in 1994. By then, most of today's post-quantum families were already on the table.

Where the schemes came from

The prominent branches are lattice-based, hash-based, multivariate, code-based and isogeny-based cryptography. Except for the isogeny-based branch, none was conceived as post-quantum cryptography. Early code-based and hash-based schemes are contemporaries of RSA, proposed in the 1970s. The first multivariate scheme dates from 1988. Lattice-based cryptography, the most successful branch, was proposed in 1996, making it Shor's closest contemporary. For comparison, elliptic curve cryptography, widely used today, was first proposed in 1985.

After Shor's publication, cryptographers took stock of what was clearly broken and what might survive. The first annual International Workshop on Post-Quantum Cryptography took place in 2006, and an introductory text prepared from that conference still holds up reasonably well — with the notable caveat of the demise of the Rainbow signature scheme. That same year, X25519 was proposed; it now secures the vast majority of all Internet connections.

NIST's competition and its picks

Ten years later, in 2016, NIST launched a public competition to standardize post-quantum cryptography, following the open format used for AES in 2001 and SHA3 in 2012. Anyone could participate by submitting and evaluating schemes. The original 82 submissions were whittled down over three rounds; eight reached the final round, and in 2022 NIST chose four to standardize first: one KEM for key agreement and three signature schemes.

Old name New name Branch
Kyber ML-KEM (FIPS 203)
Module-lattice based Key-Encapsulation Mechanism Standard
Lattice-based
Dilithium ML-DSA (FIPS 204)
Module-lattice based Digital Signature Standard
Lattice-based
SPHINCS+ SLH-DSA (FIPS 205)
Stateless Hash-Based Digital Signature Standard
Hash-based
Falcon FN-DSA
FFT over NTRU lattices Digital Signature Standard
Lattice-based

ML-KEM is the only post-quantum key agreement close to standardization, and despite occasional difficulty with its larger key sizes, it often allows a drop-in upgrade.

Signatures are different: it is telling that NIST chose to standardize three, and more are set to follow. None of the proposed signatures is close to ideal — all have much larger keys and signatures than we are used to. SLH-DSA is the most conservative choice from a security standpoint, but the worst performer. FN-DSA has the best public key and signature sizes of the group, but is difficult to implement safely because of its floating-point arithmetic. That leaves ML-DSA as the default pick. More in-depth comparisons are included below.

Name changes

Kyber is undoubtedly the most familiar name, since a preliminary version has already been deployed by Chrome and Cloudflare among others to counter store-now/decrypt-later. That will change: just as Rijndael is best known as AES and Keccak as SHA3, ML-KEM is set to become the new moniker for Kyber.

Standards status

In August 2023, NIST released three draft standards for the first three algorithms, with minor changes, and solicited public feedback. FN-DSA is delayed, as it is more difficult to standardize and deploy securely.

Timely adopters should note that feedback on the first three drafts could lead to small tweaks before the final standards appear. The changes will be minor, but final versions could well be incompatible on the wire with the current drafts. They only require a small update and do not meaningfully affect the bulk of migration work — organizational engagement, inventory and testing. Waiting for the finals before shipping can still be sensible: support for preliminary versions is not widespread, and supporting both drafts and finals may be costly. Even so, many organizations have not started at all, citing the lack of standards — a situation that has been called crypto procrastination. There is no set timeline, but the first three standards are expected around mid-2024.

Protocol and software support

Final NIST standards are only one step. The algorithms must then be standardized within higher-level protocols. For key agreement in TLS this amounts to assigning an identifier to the new algorithms; for something like DNSSEC it requires more thought. Many IETF working groups have prepared for years, and many protocol integrations are expected before the end of 2024.

Software support follows, and ecosystems move at different speeds. Several major open ecosystems are expected to have post-quantum cryptography and TLS support available in early 2025, if not earlier. Again, key agreement and signatures differ substantially.

For key agreement, client and server can add and enable support independently; once both sides enable it, TLS negotiation uses post-quantum key agreement. If a product simply uses TLS, the store-now/decrypt-later problem could be solved by a software update of the TLS library.

Post-quantum TLS certificates are more of a hassle. Unless you control both ends, two certificates are needed: a post-quantum one for new clients and a traditional one for old clients. TLS lets the client signal which signature schemes it supports, so the server can serve a post-quantum certificate only to clients that support it. Almost all TLS libraries support configuring multiple certificates, but not all servers expose that configuration, and most cases will still require a configuration change. Automated issuance is worth investigating if you are not using it already.

CAs also need time before they can issue post-quantum certificates. Their HSMs first need hardware support, which must then be audited, and the CA/Browser forum must approve use of the new algorithms. Audits are likely the bottleneck, given the volume of submissions expected after the NIST standards publish. A CA-issued post-quantum certificate before 2026 is unlikely. Come 2026, we may therefore find ourselves in an interesting in-between period: almost all Internet traffic protected by post-quantum key agreement, but not a single public post-quantum certificate in use.

Beyond the first four

NIST has two more efforts running: round 4 and the signatures onramp.

Round 4

NIST is still considering standardizing one or more of the code-based key agreements BIKE, HQC and Classic McEliece. BIKE and HQC perform much worse than ML-KEM in both key sizes and computational efficiency. NIST is considering one as a backup KEM in case of a cryptanalytic breakthrough against lattice-based cryptography. Classic McEliece is not a general-purpose competitor: its public keys are very large (268kB), but its ciphertexts are very small for a post-quantum KEM (128 bytes). That makes it attractive where the public key can be distributed in advance, such as securing a software update mechanism.

The signatures onramp

In late 2022, after announcing the first four picks, NIST called a new competition for additional signature schemes with two goals: hedging against cryptanalytic breakthroughs by standardizing a signature that outperforms SLH-DSA without relying on lattices, and finding schemes that do well in use cases where the current roster does not. In July 2023, NIST posted the 40 submissions received for a first round of public review. As is normal for a first round, by the time of writing (February 2024) the community had completely broken 10 submissions and drastically weakened a couple of others. Thom Wiggers maintains a website comparing the submissions, and some are very promising; we touch on them briefly later. Like the main competition, selection will take many years, and none of these schemes is likely to be standardized before 2027 — if it is not broken first.

The Internet has run this kind of migration before. TLS 1.3 work began around 2014, with the stated aim of discarding accumulated cruft in favor of a clean, performant transport protocol. By September 2016 support was announced; by December 2017, a follow-up post was titled "Why TLS 1.3 isn't in browsers yet."

Adoption of TLS 1.3 in December 2017: less than 0.06%.

At that point adoption sat below 0.06%. Revision 11 of the TLS 1.3 draft proved completely undeployable, breaking a few percent of all users. The culprit was protocol ossification. TLS had been designed so a client advertises the versions it supports and the connection upgrades smoothly to the newest crypto — but joints that never move rust. Plenty of server software and middleware simply crashed on seeing an unknown version; others ignored the version number and parsed the messages as TLS 1.2 regardless. Version negotiation, in practice, was broken.

The remedy arrived in revision 22: make TLS 1.3 look like TLS 1.2 on the wire, advertising itself as TLS 1.2 through the normal negotiation and padding the ClientHello with unneeded fields to appease middleboxes that inspect it. A server without TLS 1.3 support never sees that a negotiation was attempted. A sneaky new extension carries a second version negotiation mechanism. Today TLS 1.3 handles more than 93% of connections.

TLS 1.3 adoption in February 2024. QUIC uses TLS 1.3 under the hood.

To limit ossification going forward, new protocols such as TLS 1.3 and QUIC rely on GREASE: clients deliberately send unknown identifiers, including cryptographic algorithm identifiers, so that similar bugs surface and flexibility survives.

ML-KEM and the case for hybrids

NIST's first and so far only post-quantum key agreement is ML-KEM, submitted as CRYSTALS-Kyber, with designers drawn from industry and academia across France, Switzerland, the Netherlands, Belgium, Germany, Canada and the United States. Most clients today use X25519, so that is the natural comparison point.

Keyshares size(in bytes) Ops/sec (higher is better)
Algorithm PQ Client Server Client Server
ML-KEM-512 ✅ 800 768 45,000 70,000
ML-KEM-768 ✅ 1,184 1,088 29,000 45,000
ML-KEM-1024 ✅ 1,568 1,568 20,000 30,000
X25519 ❌ 32 32 19,000 19,000

ML-KEM-512, -768 and -1024 target resistance comparable to AES-128, -192 and -256 respectively. Even at the AES-128 level ML-KEM is far larger: 1,568 bytes over the wire against a mere 64 for X25519. In exchange, even ML-KEM-1024 is typically significantly faster than X25519, though this varies by platform.

Early adopters, Cloudflare included, deploy a hybrid combining X25519 with a preliminary version of ML-KEM-768 rather than banking on the speed. The apparent mismatch — 128-bit security paired with 192-bit — hedges against future improvements in lattice cryptanalysis; matching AES-128 suffices today, but a margin is worth keeping over the coming decades.

Keeping X25519 has two rationales. The remote chance of a breakthrough that breaks all ML-KEM variants leaves X25519 providing non post-quantum security, so the migration never leaves things worse than before. More importantly, the concern extends beyond the algorithm to the implementation. KyberSlash, a timing attack affecting many Kyber implementations including Cloudflare's own, did not affect Kyber as used in TLS. An equivalent implementation flaw that did affect TLS would likely need an active attacker, whose goal would not be decrypting data decades hence but stealing a cookie or token, or injecting a payload. X25519 forecloses that.

Deployment experience

What the browser experiments showed

Google ran a first post-quantum experiment in 2016, the year NIST began its competition, followed by a larger joint experiment with Cloudflare in 2018. Two hybrids were tested: CECPQ2, combining lattice-based NTRU-HRSS with X25519, and CECPQ2b, combining isogeny-based SIKE with X25519. NTRU-HRSS is close to ML-KEM in size but computationally heavier on the client; SIKE has very small keys, is computationally very expensive, and was completely broken in 2022. On handshake times, X25519+NTRU-HRSS was hard to distinguish by eye from control connections.

Handshake times compared between X25519 (blue), X25519+SIKE (green) and X25519+NTRU-HRSS (orange).

Yet a small but significant fraction of clients broke with NTRU-HRSS, because of keyshare size. A ClientHello almost always fit in a single network packet, and although the TLS specification permits a larger one, nobody exercised that allowance. Middleboxes, load-balancers and other software tacitly assumed the packet boundary — ossification again. Chrome kept its experiment at a very low rate for years and worked with vendors whose products were incompatible; absent those compatibility problems, post-quantum key agreement would likely have ramped up five years earlier.

The picture is better now. Chrome has enabled post-quantum key agreement for 10% of users, roughly 1.8% of TLS 1.3 connections to Cloudflare, over 99% of them from Chrome. Further rollout may still hit performance and compatibility problems, but it is more probable than not that Chrome widens enablement this year.

Fraction of TLS 1.3 connections established with Cloudflare that are secured with post-quantum cryptography. At the moment, it’s more than 99% from Chrome.

Firefox and Chromium derivatives

Firefox landed post-quantum key agreement support in nightly in January 2024, and it will likely reach Firefox proper later in 2024. Chrome-derived browsers such as Edge and Brave can piggyback on Chrome's work and may follow once the feature is on by default there. Browser-to-server connections are not the only ones that matter, however.

Connections to customer origins

Since September 2023 customers can enable post-quantum key agreement on connections from Cloudflare to their origins — connection (3) in the diagram below — by either a fast or a slow but safer route, falling back to traditional key agreement if the origin does not support it. The fast route sends the post-quantum keyshare immediately; the safe route lets the origin request it via a HelloRetryRequest. Chrome deploys the fast way.

Typical connection flow when a visitor requests an uncached page.

Regular testing of customer origins found that all support the safe, slow method. The fast method broke 0.34% of connections — higher than the failure rates browsers saw. Many failures look like the familiar large-ClientHello problem, but the majority stem from servers implementing HelloRetryRequest incorrectly; Cloudflare has contacted customers to pin down causes and is working through the data.

Outlook

Despite ossification, post-quantum key agreement is relatively straightforward to deploy, and the trajectory suggests double-digit client support later this year. The second migration is the harder one.

Working out which signature scheme goes where

Whether a public key travels with the signature changes what you should optimize. The root signature on the intermediate certificate and the SCTs never transmit a public key during the handshake, so schemes with small signatures but larger public keys — MAYO or UOV — fit those slots particularly well. Everywhere else the public key is sent alongside, so the combined public key plus signature size is what matters.

Signing frequency matters too. The handshake signature is the only one produced online and is created and verified exactly once; all other signatures are made ahead of time and verified many times by different clients. For the handshake signature, a balance between signing and verification time is preferable since both sit in the hot path. Elsewhere it pays to trade slower signing for faster verification — the advantage RSA still holds over elliptic curve signatures today.

Mixing schemes has costs. Every additional algorithm widens the attack surface: a single algorithmic or implementation flaw compromises the whole. It also forces the ecosystem to implement and optimize more algorithms than one.

The post-quantum signature landscape

At the AES-128 security level there are ML-DSA-44, FN-DSA-512, and the two SLH-DSA variants, compared here with Ed25519 and RSA-2048 and a sample of five candidates from the NIST onramp.

Sizes (bytes) CPU time (lower is better)
PQ Public key Signature Signing Verification
Standardized Ed25519 ❌ 32 64 1 (baseline) 1 (baseline)
RSA-2048 ❌ 256 256 70 0.3
NIST drafts ML-DSA-44 ✅ 1,312 2,420 4.8 0.5
FN-DSA-512 ✅ 897 666 8 ⚠️ 0.5
SLH-DSA-128s ✅ 32 7,856 8,000 2.8
SLH-DSA-128f ✅ 32 17,088 550 7
Sample from signatures onramp MAYOone ✅ 1,168 321 4.7 0.3
MAYOtwo ✅ 5,488 180 5 0.2
SQISign I ✅ 64 177 60,000 500
UOV Is-pkc ✅ 66,576 96 2.5 2
HAWK512 ✅ 1,024 555 2 1

None of the post-quantum options is close to a drop-in replacement for Ed25519, which is comparable to ECDSA P-256; most signatures are simply much larger. SQISign, MAYO and UOV come closest on size, but each carries a catch: MAYO and UOV have large public keys, and SQISign demands an immense amount of computation.

SLH-DSA: when the security guarantee is worth the cost

Only drafts for SLH-DSA and ML-DSA exist today, and ML-DSA beats SLH-DSA handily on every relevant performance metric. Even SLH-DSA's small public keys earn no advantage: an ML-DSA public key bundled with its signature is still smaller than an SLH-DSA signature, and the short hash of the ML-DSA public key can then serve as a short public key.

What SLH-DSA offers is confidence. Forging one requires breaking the underlying hash function badly — breaking collision resistance alone, as was done with SHA-1 and MD5, is insufficient. As of February 2024, an SHA-1-based SLH-DSA would still be considered secure. SLH-DSA actually uses SHA2 and SHA3, against which no practical attack is known. If you can shoulder the cost, it gives the best security guarantee, which can be crucial for long-lasting signatures or deployments where upgrades are impossible.

FN-DSA: the best of the worst, with a catch

FN-DSA-512 looks the strongest of the current options: signatures and public key together total only 1,563 bytes, and signing time is somewhat reasonable. Its achilles heel is fast floating-point arithmetic. Without it signing is about 20 times slower, and speed alone is not sufficient — the arithmetic must run in constant time, or the private key can be recovered through timing of signature creation. Safe implementations have proved challenging to write, which makes FN-DSA dangerous wherever signatures are generated on the fly, as in a TLS handshake. This affects signing only: verification needs no floating-point arithmetic, and no private key exists on that side to leak.

Why a single connection carries so many signatures

A first visit to a site can involve six signatures and two public keys. Three belong to the certificate chain: the CA signs the intermediate, the intermediate signs the leaf, and the leaf signs the TLS transcript to prove server authenticity.

Two more support certificate transparency. Independent parties operate CT logs that publicly record every issued certificate so misissuance can be detected after the fact. Before issuing, a CA submits the certificate to at least two logs, and each returns an SCT — the log's signature acting as a receipt that the certificate was logged.

The last is an OCSP staple, proving the leaf certificate has not been revoked in the last few days.

Candidate combinations

With today's drafts

Switching every signature to ML-DSA-44 adds 17kB transmitted from server to client during the handshake. Replacing everything but the handshake signature with FN-DSA-512 brings that down to 8kB — much better, but again, implementing FN-DSA-512 signing safely against timing side channels is hard, and carelessness here is likely to backfire.

Stateful hash-based schemes

Beyond symmetric cryptography, LMS/HSS and XMSS(MT) are already standardized. Like SLH-DSA they are hash-based and algorithmically conservative, but they require remembering state: a keypair prepares a fixed number of one-time slots and the signer must track which are used. Reusing a slot once lets anyone forge with the two signatures. Distributing the state across servers changes the signature flow substantially, and regulators may not permit it, since state is typically considered part of the private key. Restoring a server from backup illustrates the hazard.

Performance depends heavily on parameter choices, which can be explored interactively. Standardized variants with security parameter n=24 beat ML-DSA-44 on wire data for offline signatures but not FN-DSA-512. The unstandardized n=16 setting is competitive with FN-DSA-512 and can even undercut it on size, but adds another footgun: the signer can produce a single signature valid for two different messages, so there is no non-repudiation. Both FN-DSA-512 and stateful hash-based signatures offer a similar, clear performance gain over ML-DSA-44 while being hard to use safely.

Onramp candidates

UOV (unbalanced oil and vinegar) is an old multivariate scheme: 66.5kB public keys, 96-byte signatures. Using UOV for the root and SCTs alongside ML-DSA-44 elsewhere lands at only 10kB, close to FN-DSA-512. Decades of attempts to add structure to UOV public keys for a better size balance — Rainbow and GeMMS among them — have been broken.

MAYO is the newest structured multivariate proposal, from the cryptographer who broke Rainbow, so its security needs careful scrutiny even as its utility looks appealing. It allows a fine-grained signature/public-key tradeoff; the submission proposes MAYOone (321-byte signatures, 1.1kB public keys) and MAYOtwo (180-byte signatures, 5.4kB public keys). Verification is excellent, signing somewhat slower than ECDSA but far better than RSA. Combining both variants in the obvious way gives 3.3kB.

SQISign I wins on size alone, beating even RSA-2048, but signing and especially verification cost far too much computation. It may suit niche applications, but general adoption needs verification times to improve significantly, even at the price of larger signatures.

HAWK512 is lattice-based like FN-DSA-512 but needs no floating-point arithmetic, making it an appealing alternative. NIST has repeatedly said the onramp's main purpose is to standardize a non-lattice scheme — a description HAWK does not fit, though some HAWK innovations may appear in the final FN-DSA and might address its implementation concerns.

Further candidates include SNOVA, similar to MAYO, and TUOV, similar to UOV.

Weighing the signature overhead

Moving to ML-DSA-44 adds 17kB to the handshake, which is substantial next to a typical handshake today but modest next to the JavaScript and images many pages serve. The distinction matters because this cost lands on every TLS connection without exception, whether it carries a heavy web page or a latency-sensitive API call. Nor is the penalty limited to slightly longer waits: on weak cellular coverage the extra bytes can decide whether a page loads at all or the connection times out. Separately, measurements show many apps perform a surprisingly high number of TLS handshakes.

As with key agreement, success rates matter as much as speed. In 2021 an experiment artificially inflated certificate chains to imitate larger post-quantum certificates. The plan to run it on a small sample of regular traffic failed because large chains broke some connections; to avoid harming customers, the test moved to background connections launched from challenge pages, pairing a live connection with an enlarged chain against a control connection.

Missing requests when artificially inflating certificate chain size to simulate post-quantum certificates.

Missing requests when artificially inflating certificate chain size to simulate post-quantum certificates.

The missing control/live pairs jump around 10kB and 30kB, pointing to clients or middleboxes that fail once chains grow past those thresholds. That does not rule out an ML-DSA-44-only deployment: browsers can enable post-quantum certificate support gradually, and broken middleboxes can be fixed with vendors. Servers must be able to serve either a small traditional chain or a larger post-quantum one.

These failures do, however, undermine the single-certificate migration strategy, in which a traditional certificate carries a post-quantum certificate in a non-critical extension that unaware clients ignore. Installing that single certificate would instantly break every client with compatibility problems, making the approach a non-starter.

Handshake timing and congestion

On performance, the added handshake time looks like this:

A graph of TLS handshake time against kB of dummy data added.

Performance when artificially inflating certificate chain size to simulate post-quantum certificates.

The step near 40kB comes from an extra round-trip once the full congestion window is used. Cloudflare's proximity to clients means a larger congestion window than usual; at a typical window the step would land near 10kB, and it would be bigger given typical round-trip times. Adding 9kB therefore costs roughly 15%, while crossing 10kB likely triggers an extra round-trip and a slowdown that could exceed 60% — more than negating TLS 1.3's performance advantage over TLS 1.2, and too much to enable by default.

Is 9kB too much? Post-quantum key agreement was not free either, but it was cheaper and delivers a tangible security benefit today. Treating signatures the same way is risky: waiting too long to enable post-quantum certificates by default could leave us out of time when a quantum computer arrives.

Plans and signature-count reduction

Over the coming years the work will be to test post-quantum authentication in TLS with browsers, adding support for post-quantum certificates when they arrive (probably around 2026) without enabling them by default. In parallel, several ideas aim to cut the number of signatures.

Dropping intermediate certificates

CAs list their intermediates in the CCADB, and most browsers ship the set of intermediates belonging to trusted CAs, so a browser can complete a chain even if a server omits it. Three proposals compete. Martin Thomson's 2019 draft has the browser send a single bit indicating it holds an up-to-date intermediate list, after which the server skips the intermediates; this works in most cases but can cause hard-to-debug corner cases, since not all intermediates appear in the CCADB — including some from non-custom CAs — the browser may wrongly believe it is current, and it may reconstruct a different chain than the server intended.

Dennis Jackson's 2023 draft is more robust: each year a fixed list of intermediates is compiled from the CCADB, the browser sends the named lists it holds, and the server replaces matching intermediates with their sequence number in the list. His survey of popular sites found that omitting intermediates alone saves more than 2kB versus certificate compression for half of them, even with today's certificates — which are indeed somewhat bloated. The broader TLS trust expressions draft lets a browser signal in finer detail which CAs and intermediates it trusts. Some form of intermediate suppression is likely within a few years, bringing an ML-DSA-44-only deployment below 13kB.

KEMTLS

KEMTLS (AuthKEM at the IETF) takes a more invasive route: the leaf certificate's signature algorithm is replaced by a KEM, and the server proves control of the leaf certificate by decrypting a client challenge — not unlike older TLS versions encrypting a shared key to an RSA certificate. It adds real complexity to TLS 1.3, which was designed to simplify TLS 1.2, though the TLS 1.3 machine-checked proof has been extended to KEMTLS. Adopting it is a significant engineering effort that must pay off.

Replacing an ML-DSA-44 handshake signature of 2,420 bytes with KEMTLS using ML-KEM-512 saves 852 bytes in total bytes transmitted and 1,620 bytes on the server side. Against 17kB, 1.6kB is unimpressive, and KEMTLS offers little when small post-quantum signatures like MAYOone are available. Its value appears when those 1.6kB bring the server inside the congestion window — for instance when UOV covers everything except the handshake and leaf signature — and, especially on embedded devices, when one KEM for key agreement also replaces the signature scheme otherwise needed only for the handshake signature. It is not the lowest-hanging fruit, but depending on which signature schemes are standardized and which other protocol changes land, it could come into its own.

Merkle tree certificates

The most ambitious proposal, Merkle tree certificates (MTC), replaces all signatures except the handshake signature with a short certificate under 800 bytes. The catch is that MTC does not fit every situation, and those cases must fall back to X.509 and certificate transparency. It assumes no direct certificate issuance — a Merkle tree certificate must be requested and then waits at least a day before use — and that clients (relying parties) keep up with a transparency service; browsers have update mechanisms for this, but a browser unused for a while may be stale. MTC is best viewed as an optimisation for the vast majority of cases.

Mechanically, a CA issues assertions in batches at a fixed rhythm, say hourly. An assertion is a certificate without the signature — for example, that a given P-256 public key can be trusted for example.com. A subscriber sends an assertion to the CA, which vets it and queues it for issuance.

An overview of a Merkle Tree certificate deployment

An overview of a Merkle Tree certificate deployment

For each batch the CA computes a Merkle tree, hashing pairwise until a single root summarizes the batch, so membership can be proven to anyone holding only the root by revealing a few hashes up the tree — the Merkle tree certificate. Each assertion is valid for a fixed number of batches, say 336 batches for two weeks, known as the validity window; when issuing a batch the CA publishes the assertions plus a signature on the roots of all currently valid batches, the signed validity window.

After issuance the subscriber can pull the Merkle tree certificate, install it alongside its X.509 certificate, and wait until it becomes useful. Each hour, transparency services — including browser vendors' — pull new assertions and the signed validity window from trusted CAs, check consistency against the previous window, and republish them. Each hour, browsers download the latest roots from their trusted transparency service. When connecting, the client advertises which CAs it trusts and the sequence number of the latest batch whose roots it holds; the server then sends a new MTC, an older MTC if the client is somewhat stale, or falls back to X.509.

Outlook

Post-quantum key agreement and post-quantum authentication are in very different positions. Expect the first Internet-wide use of post-quantum authentication around 2026, but with few deployments enabling it by default. Unless its performance comes much closer to today's schemes, most operators will leave it switched off unless regulation pushes them to act.

Migration beyond TLS

Even TLS has only partly been covered here: Encrypted ClientHello did not fit into this post. And TLS is not the only protocol that matters for Internet security. DNSSEC, which secures the resolution of domain names, is one of the challenges we can only flag without going into detail.

Advanced cryptography still lacks replacements

Key agreement and signatures are the most widely used primitives, but over the past few years more esoteric schemes have been adopted for advanced use cases: unlinkable tokens via Privacy Pass / PAT, anonymous credentials, and attribute-based encryption, to name a few. For most of these advanced schemes, no practical post-quantum alternative is known yet.

What you can do today

For most organizations the bulk of the effort is preparation. You need to establish where cryptography is used in the first place, whether it sits in software libraries or hardware, what the timelines of your vendors are, whether you need to hire expertise, and what is at risk and how it should be prioritized. Before all those questions can be answered, start by creating engagement within the organization. None of this has to wait for NIST to finish its standards or for software to ship with post-quantum cryptography.

Testing can also start now, because the performance characteristics of the final standards will not be meaningfully different from the preliminary implementations available today. If a preliminary version works in your test environment, the final standard will most likely work in production. A collection of software and forks that already support preliminary post-quantum key agreement, together with instructions for enabling it in your browser today, is available at the linked research page; for Chrome, the flag is enable-tls13-kyber in chrome://flags.

Cloudflare customers can find guidance on enabling post-quantum key agreement to their origin, and on the products that are already secured against store-now/decrypt-later. Issues encountered during migration can be raised at [email protected].