Post-quantum cryptography: what actually breaks, and what replaces it

Almost every account of the quantum threat to cryptography collapses into a single sentence: quantum computers will break encryption. It is a bad sentence. It is wrong about the scope of the damage, wrong about which systems are urgent, and wrong about what to do first.

The accurate version is narrower and more useful. Two quantum algorithms matter for cryptography. One of them is catastrophic for a specific family of mathematics that happens to underpin key exchange and digital signatures everywhere. The other is a modest discount on everything else, and a smaller discount in practice than on paper. Which of the two applies to a given system tells you whether you have a decade or whether you are already late.

This article covers the general case. A companion piece applies it to the place where the exposure is most concentrated and the migration hardest — Bitcoin, Ethereum and the digital-asset ecosystem.

Two algorithms, two completely different threats

Shor’s algorithm (1994) solves integer factorisation and the discrete logarithm problem in polynomial time. Those two problems are the entire security foundation of RSA, Diffie–Hellman, ECDH, ECDSA and EdDSA. A quantum computer large enough to run Shor at scale does not weaken these schemes; it eliminates them. The private key is derived from the public key, and the public key is public. There is no residual difficulty to fall back on.

Grover’s algorithm (1996) searches an unstructured space of size N in roughly √N steps. Applied to a symmetric cipher, it halves the effective key length: AES-128 nominally drops to about 64 bits of quantum security, AES-256 to 128. Applied to a hash function, it does the same for preimage resistance.

Read naively, Grover sounds nearly as alarming as Shor. It is not, for three reasons. Grover’s speedup is quadratic rather than exponential, so it is swamped by the constant factors of fault-tolerant execution — every one of those √N steps is a full error-corrected quantum operation, thousands of times slower than the classical operation it replaces. It parallelises badly: running it on k machines buys only a √k improvement, where classical brute force scales linearly. And the search is inherently serial, so the wall-clock time for a meaningful attack runs into geological territory.

Shor is a break. Grover is a discount — and a worse one than the arithmetic suggests.

The practical consequence: AES-256 and SHA-384 are considered fine indefinitely, AES-128 and SHA-256 are widely regarded as acceptable in practice, and the entire symmetric and hash-based world needs, at most, a parameter bump. The problem is concentrated almost entirely in public-key cryptography.

Why you cannot simply use bigger keys

The standard reflex when a cipher weakens is to grow the key. That reflex works against Grover and fails against Shor, and the reason is worth understanding, because it is the reason migration is unavoidable rather than optional.

Against Grover, growing the key helps exponentially: doubling an AES key from 128 to 256 bits squares the classical search space, so the quantum search space grows from 2⁶⁴ to 2¹²⁸. Defence outruns attack.

Against Shor, growing the key barely helps at all, because Shor’s cost grows only polynomially — roughly polylogarithmically in the relevant sense — with the size of the modulus. The 2026 whitepaper from Google Quantum AI, the Ethereum Foundation and Stanford quantifies this precisely for elliptic curves: breaking a standard 256-bit curve needs on the order of 1,200 logical qubits, while quadrupling to a 1,024-bit curve requires roughly five thousand logical qubits and about 64× the runtime.^[8] That is a large jump in engineering terms and an almost irrelevant one in cryptographic terms. The authors’ conclusion is blunt: the security benefits of large elliptic curves are “at best, partial and temporary and, at worst, nearly non-existent.”

Attack cost that scales polynomially against defence cost that also scales polynomially is a losing race. You do not need a bigger key. You need different mathematics.

Encryption and signatures fail on opposite clocks

This is the distinction that should drive any migration plan, and it is the one most often skipped.

Key exchange and encryption: the risk is already running

An adversary can record encrypted traffic today and decrypt it years later, once a cryptographically relevant quantum computer (CRQC) exists. This is harvest now, decrypt later. Nothing needs to be broken today for the damage to be done today — the interception is the attack, and the decryption is merely deferred.

The implication is uncomfortable: for any data whose confidentiality must outlive the arrival of a CRQC, the deadline has already passed. Medical records, state secrets, long-lived intellectual property, and the private keys inside long-lived certificates are all in this category.

Michele Mosca’s inequality states this cleanly. If x is how long your data must stay secret, y is how long your migration takes, and z is the time until a CRQC exists, then you are already too late whenever x + y > z. Most organisations have never measured x or y, and argue exclusively about z.

Signatures: nothing to harvest, everything to forge

Signatures behave in the opposite way. There is no point recording a signature to break later; a signature is already public and already verified. Its purpose is authenticity at a moment in time, not secrecy.

Instead the risk arrives all at once. On the day a CRQC exists, every ECDSA key whose public key is known becomes forgeable, and the attacker can impersonate its owner going forward. Until that day, the scheme is fine.

That makes signatures look like the more relaxed problem, and for software updates and TLS certificates — where keys rotate on a timescale of months — they broadly are. But the comfort disappears wherever a public key is permanently published and permanently controls something valuable. That is precisely the situation on every public blockchain, and it is why the digital-asset ecosystem is the sharpest edge of the whole problem. A published, never-rotated public key is not harvest-now-decrypt-later. It is harvest-now-forge-later, and the harvesting has been done for you.

What replaces it

After an eight-year public competition beginning in 2016, NIST published the first three post-quantum standards on 13 August 2024.^[1][2][3] A fourth is still in draft, and a backup key-establishment mechanism was selected in March 2025.

Two things about this table are worth dwelling on.

FIPS 206 is still not final, more than eighteen months after its three siblings. The delay is instructive rather than bureaucratic: Falcon’s signing procedure uses floating-point arithmetic in a Gaussian sampler, which is difficult to implement without opening a side channel. NIST has been working through implementation guidance before locking the standard, and until it does, parameter encodings and object identifiers can still change.^[5] Anyone planning to depend on FN-DSA today is planning on a moving target.

There is deliberate redundancy. ML-DSA and SLH-DSA both sign, and NIST standardised both anyway, because they rest on unrelated assumptions — if lattices fall, hashes remain. HQC exists for the same reason next to ML-KEM. This is not indecision; it is a direct response to what happened to SIKE, an isogeny-based finalist that was destroyed in 2022 by a classical attack running on a single core in about an hour. Post-quantum schemes are younger and less battle-tested than RSA, and the standards bodies have priced that in. It is a reason to deploy them alongside classical cryptography rather than a reason to wait.

The price: everything gets bigger

ECDSA is a remarkably economical scheme: a 32-byte private key, a 33-byte compressed public key, a 64-byte signature. Nothing in the post-quantum world comes close, and that gap — not the mathematics — is what makes migration expensive.

The trade-off is legible in the table. SLH-DSA has the most conservative security story in the entire lineup — it assumes nothing but the strength of a hash function — and it pays for that with signatures over a hundred times larger than ECDSA. FN-DSA is the compact option, which is exactly why the ecosystem wants it, and exactly why its finalisation is taking so long. ML-DSA sits in the middle and is, for most purposes, the default.

For key establishment the story is milder but the same shape: ML-KEM-768 uses a 1,184-byte public key and a 1,088-byte ciphertext, against 32 bytes for X25519.

Where bandwidth is free, this is an annoyance. Where every byte is replicated across thousands of nodes and stored forever — a blockchain — it is the central political problem of the migration.

The objection that is mostly a myth: CPU time

A recurring objection is that post-quantum algorithms are slow to compute. For the scheme most people will actually deploy, this is close to backwards, and the numbers are worth knowing because they redirect the argument to where the real cost sits. Cloudflare’s benchmarks, normalised so that ML-DSA-44 is 1:^[7]

Read the ML-DSA row against the two schemes it replaces. It signs about seven times slower than Ed25519 — and eighty times faster than RSA-2048, which nobody has ever called unusably slow. Its verification is quicker than Ed25519’s outright. ML-DSA sits comfortably inside the performance envelope of cryptography already deployed at internet scale.

That asymmetry matters more than it first looks, because signing and verification are not performed equally often. A signature is produced once and verified everywhere, forever — every TLS client, every node validating a block, every device checking a firmware update. Verification is the operation that scales with the size of the network, and it is precisely the one where ML-DSA is already competitive.

Where compute genuinely does explode is the conservative option. SLH-DSA-128s signs fourteen thousand times slower than ML-DSA, and its faster variant only gets that down to 720× by doubling the signature to 17 KB. So the price of SLH-DSA’s hash-only security story is not just a hundred-fold in bytes — it is bytes and time, together. That is the real reason it is a backup rather than a default.

FN-DSA’s problem is different again, and it is the same problem that is holding up FIPS 206. The 3× signing cost assumes hardware floating-point arithmetic; emulate the floating point and it degrades to roughly RSA-2048 signing speed, surrendering the advantage entirely. Worse, floating-point addition is not associative — a+(b+c) and (a+b)+c are only guaranteed to be close — which makes cross-platform test vectors genuinely hard and means an implementation that is side-channel-safe on one processor’s FPU may not be on another’s. Cloudflare’s estimate is that FN-DSA will not be meaningfully deployed before 2033.

The post-quantum migration is a bandwidth and storage problem wearing a CPU problem’s clothes.

What ML-DSA does cost is versatility. As Cloudflare puts it, many tricks that RSA and ECC make easy simply cannot be done with it — and those tricks are load-bearing in places like blockchain consensus, where thousands of signatures are aggregated into a few dozen. Losing them is a design problem, not a throughput problem. Their verdict on deploying ML-DSA anyway, quoting Eric Rescorla, is the right note: “You go to war with the algorithms you have, not the ones you wish you had.”

Hybrid: use both, on purpose

The standard deployment pattern is not to replace classical cryptography but to run both, combining a classical and a post-quantum scheme so that the result is secure if either holds. This costs the bandwidth of both, and it buys protection against the two failure modes that actually worry practitioners: a quantum break of the old scheme, and an undiscovered classical break of the new one.

This is no longer theoretical. Hybrid key exchange combining X25519 with ML-KEM-768 is deployed by default in mainstream browsers and across large parts of the TLS ecosystem; Signal’s PQXDH and Apple’s iMessage PQ3 both shipped hybrid post-quantum key agreement in 2023–2024. The mathematics is settled and the software exists. What remains is inventory and coordination.

1. Inventory — find every use of RSA, ECDH, ECDSA and EdDSA, including the ones inside vendor products, firmware and hardware roots of trust.
2. Classify by clock — separate confidentiality (harvest-now-decrypt-later, already urgent) from authenticity (breaks on Q-Day, urgent where keys cannot rotate).
3. Measure x and y — how long must this stay secret, and how long would replacing it actually take?
4. Build crypto-agility — the ability to change algorithm without re-architecting is worth more than any single algorithm choice.
5. Deploy hybrid — classical + PQC together, starting with the longest-lived secrets.

The timelines everyone is working to

No CRQC exists. The largest devices available in 2026 offer on the order of a thousand physical qubits with error rates far above what a cryptographic attack requires, and the gap between that and a machine running Shor at scale is measured in orders of magnitude, not increments. We have written separately about why that gap is an error-correction problem rather than a qubit-count problem, and about how sharply the resource estimates have been falling.

The falling estimates are the reason the deadlines are firming up regardless. NIST’s transition guidance deprecates 112-bit-strength classical public-key cryptography after 2030 and disallows it after 2035.^[6] Germany’s BSI has recommended PQC migration for high-assurance systems for several years. Google has stated an internal migration target of 2029.

Note what these dates are not. They are not predictions that a quantum computer will exist in 2030. They are statements about how long a migration takes, working backwards from an uncertain arrival with Mosca’s inequality in hand. The date is set by y, not z.

What this means

The mathematics of post-quantum cryptography is, at this point, the easy part. The algorithms are standardised, implemented, and running in production on billions of devices. The hard parts are finding where the old cryptography is hiding, absorbing an order of magnitude more bytes, and coordinating a change across systems that were never designed to change.

Those difficulties scale with how distributed the system is and how immovable its keys are. Which is why the hardest instance of this problem is not in a bank or a government — it is on public blockchains, where the keys are published by design, cannot be rotated, are worth trillions, and no one is in charge of the upgrade.