Post-Quantum Cryptographic Migration

1.1 The Threat Matrix and Quantum Timelines

Public-key cryptography rests on problems that are hard for classical computers. RSA rests on integer factoring. Diffie-Hellman and elliptic curve cryptography rest on the discrete logarithm problem. Both are believed hard classically, and neither is hard for a quantum computer that runs Shor's algorithm.

What Shor's algorithm does

Shor's algorithm turns factoring into period finding. To factor N, pick a random a and consider the function a to the power x, modulo N. That function is periodic, and its period r leads directly to a factor of N by elementary arithmetic. Finding r classically is as hard as factoring. Finding r on a quantum computer is not.

The quantum part is the quantum Fourier transform. The algorithm prepares a superposition over x, computes the function into a second register, and then applies the Fourier transform to the first register. Measuring it yields a value concentrated near multiples of the reciprocal of the period, and a continued-fraction expansion recovers r. The whole procedure runs in time polynomial in the number of bits.

The same machinery solves discrete logarithms, which is why elliptic curve cryptography falls with RSA rather than surviving it. Elliptic curves fall somewhat sooner in resource terms, because a 256-bit curve needs fewer logical qubits than a 2048-bit modulus.

Nothing about this is a speedup on a classical algorithm. It is a different algorithm that only a quantum computer can execute, and it reduces an exponential problem to a polynomial one.

What Grover's algorithm does, and does not

Grover's algorithm searches an unstructured space of N items in about the square root of N steps. Applied to a symmetric key, it halves the effective key length in the exponent: a 128-bit key needs about 2 to the power 64 quantum operations instead of 2 to the power 128 classical ones.

That sounds alarming and it is much less serious than Shor, for three reasons. The speedup is quadratic rather than exponential, so doubling the key length restores the original margin. Grover's algorithm is inherently sequential and parallelizes poorly, so a thousand quantum machines give roughly a factor of thirty rather than a factor of a thousand. And the 2 to the power 64 operations are coherent quantum operations, each far more expensive than a classical AES evaluation.

The practical guidance follows directly. Move symmetric encryption to 256-bit keys where the cost allows, which mostly means AES-256 rather than AES-128. Hash functions need less change than people assume: preimage resistance takes the same square-root hit, and collision resistance is already the binding constraint and gains little from a quantum attack that needs enormous memory. SHA-256 remains acceptable and SHA-384 is the conservative choice.

The resource question, and why the estimate keeps falling

A quantum computer that runs Shor on RSA-2048 needs perhaps a few thousand logical qubits and on the order of a billion logical gate operations. Physical qubits are noisy, so each logical qubit costs many physical ones through error correction, and the multiplier is the number that decides feasibility.

Published estimates have fallen sharply, and the direction matters more than any single figure. A widely cited 2019 analysis put RSA-2048 at roughly 20 million noisy physical qubits running for about eight hours. A 2025 revision by the same author cut that to under one million physical qubits running for under a week, through better error correction, better arithmetic, and better magic-state handling.

Nothing in that revision involved new hardware. The estimate fell because the algorithms and the error correction improved, and there is no reason to assume that the process stopped. Any plan that assumes a fixed resource requirement is planning against a number that engineers are actively reducing.

Where hardware stands in 2026 is a separate question, and Chapter 7 covers it properly. The short version is that the field is in a late noisy era with early fault-tolerant components. Demonstrations in 2025 and 2026 reached tens of logical qubits at short code distances, which proves the error-correction principle and does not run a billion-gate circuit. Credible roadmaps put cryptographically relevant machines in the early 2030s, with wide error bars in both directions.

Harvest now, decrypt later

The threat that requires action today does not require a quantum computer today. An adversary records encrypted traffic now and stores it. When a sufficiently large quantum computer exists, the adversary decrypts the archive. The session key was protected by an elliptic curve exchange that Shor breaks, so the recording becomes plaintext retroactively.

Bulk recording at national scale is a documented capability. Storage is cheap and falling. The only question is whether any particular data is worth the storage cost, and for diplomatic traffic, health records, source code, genetic data, and long-lived business secrets the answer is clearly yes.

Mosca's inequality states the planning rule in one line. Let X be the number of years the data must stay confidential, Y the number of years the migration takes, and Z the number of years until a cryptographically relevant quantum computer exists. If X plus Y exceeds Z, then you are already too late and data being transmitted today will be exposed.

  today                                                          Z (CRQC)
    |------------------------------------------------------------|
                                                          ~2032, wide error

  SESSION DATA, X = 0 (no confidentiality after the session)
    |Y=2|  migration done, nothing exposed.  X + Y = 2 < Z.  SAFE

  BUSINESS RECORDS, X = 7
    |Y=3|.......X=7.......|            X + Y = 10 > Z.  AT RISK
    Everything transmitted from today until migration completes is
    exposed, because the recording outlives the algorithm.

  HEALTH AND IDENTITY DATA, X = 40
    |Y=3|.................................X=40.............>
    X + Y = 43, far past Z. Already too late for data sent today.
    The only mitigation is to migrate the transport now and to
    re-encrypt the archive later.

The inequality reorders priorities in a way that surprises teams. A payment authorization with a two-second useful life is not urgent, however sensitive it feels. A patient record transmitted today is urgent, because it must stay confidential for decades.

Signatures sit on the other side of the line. A signature has no confidentiality to harvest, so there is no retroactive attack on a signature made today. A quantum computer forges future signatures, not past ones. That is why key establishment migrates first and signatures migrate second, and it is the reason the deadlines differ by a year.

The one exception is a long-lived trust anchor. A root certificate authority key, a firmware signing key, or a code signing key that must stay valid into the 2040s needs post-quantum protection sooner, because the artifacts it signs will be checked long after the algorithm falls.

1.2 The NIST Standardized Algorithms

NIST published three standards in August 2024. Each replaces a specific classical primitive, and each carries a different cost profile.

ML-KEM, FIPS 203

Module-Lattice Key Encapsulation, derived from CRYSTALS-Kyber, replaces Diffie-Hellman key agreement. It is a key encapsulation mechanism rather than a key exchange, and the distinction matters for how it is used.

A key exchange has both sides contribute to a shared value. A KEM has three operations instead. Key generation produces an encapsulation key and a decapsulation key. Encapsulation takes the public encapsulation key, generates a random shared secret, and returns that secret along with a ciphertext. Decapsulation takes the ciphertext and the private key and recovers the same secret.

The hardness assumption is Module Learning With Errors. Informally, given a matrix A and a vector b equal to A times s plus a small error e, recovering s is hard. The lattice structure makes the arithmetic fast, because it reduces to polynomial multiplication that a number-theoretic transform performs quickly.

ML-KEM uses the Fujisaki-Okamoto transform to reach the strong security notion that TLS needs, which is security against an attacker who can submit chosen ciphertexts. The transform makes decapsulation re-encrypt and compare, and it gives implicit rejection: a malformed ciphertext returns a pseudorandom secret rather than an error. That behavior is deliberate, because an error message leaks information about the private key.

ML-KEM-768 is the general-purpose choice and the one that the deployed hybrid uses. Speed is not the problem: on a modern core, key generation, encapsulation, and decapsulation each take tens of microseconds, which is comparable to or faster than X25519. Size is the problem, and the whole deployment story in Section 1.3 follows from the 1,184 and 1,088 byte figures.

ML-DSA, FIPS 204

Module-Lattice Digital Signature Algorithm, derived from CRYSTALS-Dilithium, replaces ECDSA and Ed25519. It uses the Fiat-Shamir with aborts construction: a signer produces a candidate signature, tests whether it leaks information about the private key, and restarts if it does. The rejection loop is why signing time varies between attempts.

ML-DSA needs no floating-point arithmetic, which makes constant-time implementation straightforward across platforms. That property is the main practical advantage over the alternative lattice signature, and it is why ML-DSA is the general-purpose recommendation.

A certificate carries a public key and a signature. Replacing Ed25519 with ML-DSA-65 grows one certificate by roughly 5 kilobytes, and a chain with a leaf and an intermediate by roughly 10. Section 1.3 covers what that does to a handshake.

SLH-DSA, FIPS 205

Stateless Hash-Based Digital Signature Algorithm, derived from SPHINCS+, rests on nothing but the security of a hash function. It uses no lattices, no number theory, and no new assumptions. A mathematical breakthrough against every lattice scheme leaves SLH-DSA standing.

The construction is a hypertree of one-time signature keys. A few-time signature scheme signs the message, a tree of one-time signatures authenticates that key, and the root is the public key. Statelessness comes from choosing the leaf pseudorandomly from the message, which removes the catastrophic failure mode of stateful hash-based schemes where reusing a one-time key destroys security.

The cost is size and speed. Signatures run from about 7.9 kilobytes to about 30, and signing is slow.

The "s" variants optimize for a small signature and the "f" variants for fast signing, and the difference between them is roughly a factor of two in size and an order of magnitude in speed.

The 32 byte public key is the feature that makes SLH-DSA attractive for a specific job. A root of trust burned into hardware needs a tiny public key, is used rarely, signs few things, and must remain trustworthy for decades. Every one of those properties matches SLH-DSA, and none of them matches ML-DSA.

What is still in progress

Two further pieces are worth tracking.

HQC was selected in March 2025 as a backup key encapsulation mechanism. It is code-based rather than lattice-based, so its security rests on the hardness of decoding a random linear code. The point is diversity: a breakthrough against lattices breaks ML-KEM and leaves HQC standing. Its standard is in development, and its keys and ciphertexts are larger than ML-KEM's.

A lattice signature with much smaller signatures than ML-DSA is also in standardization. Its appeal is the size, and its difficulty is that its signing procedure uses floating-point arithmetic, which makes a constant-time implementation hard to get right across platforms.

Choosing

1.3 Post-Quantum TLS 1.3 Negotiation

Key exchange migrated first because the harvest-now threat applies to it and because the change is a configuration rather than a public key infrastructure project.

The hybrid construction

A hybrid key exchange runs a classical exchange and a post-quantum one, and derives the session key from both. The session stays secure unless both break.

That property is the whole argument. The lattice schemes are new, and new cryptography has a history of being broken by cryptanalysis rather than by quantum computers. Hybrid means that a flaw in ML-KEM costs nothing today, because X25519 still protects the session against classical attack, and a quantum computer costs nothing either, because ML-KEM still protects it.

The combination must be done correctly. The two shared secrets are concatenated and fed into the key derivation function together, rather than combined by exclusive-or or used in sequence. The concatenation is what makes the result at least as strong as the stronger component.

  CLIENT                                             SERVER
  ClientHello
    key_share: group 0x11EC (X25519MLKEM768)
      +-------------------------+----------------+
      | ML-KEM-768 encaps key   | X25519 pubkey  |   1,216 bytes
      |        1,184 B          |      32 B      |
      +-------------------------+----------------+
                      --------->
                                        ML-KEM encapsulate -> (ct, ss1)
                                        X25519 agree       -> ss2
                                 ServerHello
                                   key_share: group 0x11EC
      +-------------------------+----------------+
      | ML-KEM-768 ciphertext   | X25519 pubkey  |   1,120 bytes
      |        1,088 B          |      32 B      |
      +-------------------------+----------------+
                      <---------
  ML-KEM decapsulate -> ss1
  X25519 agree       -> ss2

  shared secret fed to HKDF = ss1 || ss2        (concatenated, in order)

  The ClientHello grows from about 300 bytes to about 1,500, which is
  at or past the usual 1,500 byte path MTU. That is where deployments
  break, and Section 1.3 covers why.

X25519MLKEM768 is the combination that browsers ship and that content delivery networks enable by default, and measurement studies through 2026 put roughly half of surveyed domains on a hybrid exchange. Curve-based variants pairing ML-KEM with NIST P-curves exist for deployments with a FIPS requirement on the classical half.

What the extra bytes cost

The client hello grows by about 1.2 kilobytes and the server hello by about 1.1. Neither is large in absolute terms, and both cross thresholds that matter.

The first threshold is the path MTU. A ClientHello that exceeds about 1,500 bytes spans two TCP segments. That is legal and ordinary, and a small number of middleboxes handle it badly, dropping or mangling a hello that does not fit one packet. The failure looks like an intermittent connection reset from one network and works everywhere else, which makes it expensive to diagnose.

The second threshold is the initial congestion window, which is commonly ten packets or about 14 kilobytes. A larger hello alone does not exceed it. A larger hello plus a post-quantum certificate chain does, and then the handshake takes an extra round trip while the server waits for an acknowledgement.

The third cost is the record layer. QUIC has an amplification limit before address validation: a server must not send more than three times the bytes it received. A larger client hello raises that budget, which is one of the few places where the extra size helps.

The table shows why the two halves of the migration have different timetables. Key exchange adds about 2.3 kilobytes and is deployable now. Signatures add about 10 to 13 kilobytes across a chain, which pushes most handshakes past the initial congestion window and costs a round trip.

Certificates and the harder half

A post-quantum certificate chain needs every link changed: the leaf key, the leaf signature, the intermediate signature, and the root signature. Every relying party needs to understand the new algorithms before a server can present them, which is the coordination problem that made the last two certificate migrations take years each.

Three techniques reduce the size problem rather than eliminating it. Certificate compression, which TLS 1.3 supports, cuts a chain by a substantial fraction because certificates share structure. Trust anchor negotiation lets a client tell the server which roots it holds, so the server omits what the client already has. And a shorter chain helps directly, which argues for issuing from a root with no intermediate where the deployment allows.

Two transitional formats appear in practice. A dual chain presents both a classical and a post-quantum chain and lets the client pick, which works and doubles the bytes. A composite certificate carries both keys and both signatures in one structure, which is atomic and which requires every relying party to parse the new format.

1.4 Crypto-Agility and Legacy Modernization

The migration now underway will not be the last one. HQC is coming as a diversity option, the lattice signature landscape is unsettled, and any of the new algorithms can be weakened by cryptanalysis. A system that can change algorithm once, painfully, will face the same pain again.

Crypto-agility is the property of changing algorithm without changing application code. It is an architecture property rather than a library feature, and it has four parts.

Know what you have

No migration starts without an inventory, and almost no organization has one. The inventory must record, for every use of public-key cryptography: the algorithm and parameters, the key lifetime, the confidentiality lifetime of the protected data, the code path that uses it, and the owner.

Four discovery techniques together give reasonable coverage. Static analysis finds algorithm names and library calls in source. Binary scanning finds them in dependencies that ship without source. Network scanning finds what endpoints actually negotiate, which often differs from what configuration says. And a certificate inventory from the certificate transparency logs and internal certificate authorities finds what is issued.

Prioritize by the confidentiality lifetime of the data rather than by the sensitivity label, because Mosca's inequality operates on lifetime. A long-lived archive and a root key outrank a high-sensitivity session that expires in seconds.

Abstract the primitive, not the algorithm

Application code must never name an algorithm. It names a purpose, and a policy layer resolves the purpose to an algorithm.

# Wrong: the algorithm is a build-time constant scattered through the code.
signature = ed25519_sign(private_key, message)
shared    = x25519_agree(my_private, their_public)

# Right: the code names a purpose, and policy resolves it.
#   - the algorithm identifier travels with every artifact
#   - the policy can change without touching this code
#   - two algorithms can be active at once during a migration

sig = crypto.sign(purpose="document.attestation", message=message)
#  -> returns {alg: "ML-DSA-65", key_id: "kms:sig-2026-03", sig: b"..."}

ok = crypto.verify(purpose="document.attestation", message=message,
                   signature=sig)
#  -> resolves the algorithm from sig.alg, checks it against the policy's
#     accepted set, and rejects an algorithm the policy retired

secret = crypto.establish(purpose="session.transport", peer=peer_hello)
#  -> negotiates from the policy's ordered preference list

Three properties make that interface work. Every artifact records which algorithm produced it, so a reader does not have to guess. Every buffer is variable-length, because a fixed 64 byte signature field is a migration blocker. And the policy holds an ordered preference list plus a separately configured accepted set, so that an algorithm can be removed from production use before it is removed from acceptance.

Push the key operation behind a boundary

A hardware security module or a cloud key management service performs the operation and never releases the key. That gives an audit trail and a containment boundary, and it also gives an agility boundary: the caller asks for a signature over a purpose, and what algorithm the module uses is the module's business.

Two cautions apply to post-quantum specifically. Hardware module support for the new algorithms arrives at firmware speed, which is slower than software, so confirm the algorithms and parameter sets that your modules actually support before designing around them. And key sizes grew, so a module with a fixed key slot size or a fixed object store holds fewer post-quantum keys than classical ones.

Plan the deprecation, not only the adoption

Most migrations add the new algorithm and never remove the old one. The result is a system that supports both indefinitely, which gives an attacker a downgrade target and gives the operator no benefit.

A deprecation roadmap has five stages, and each needs a measurable exit condition rather than a date alone.

1. Inventory and instrument. Every cryptographic operation emits its algorithm as telemetry. Exit when coverage is complete.
2. Add the new algorithm alongside the old. Both are accepted, the old one is preferred. Exit when the new path is proven in production.
3. Flip the preference. The new algorithm is preferred and the old is still accepted. Exit when the telemetry shows the old algorithm below a threshold.
4. Remove the old algorithm from the accepted set, behind a per-client exception list. Exit when the exception list is empty.
5. Remove the code path entirely. Exit when the artifacts signed under the old algorithm have all expired or been re-signed.

The telemetry in stage one is what makes stages three and four possible. An organization that cannot answer "how many connections still negotiate the old group, and which clients are they" cannot safely remove anything, and so it removes nothing.

What to do about data already at rest

Transport migration protects future traffic. It does nothing for an encrypted archive whose key was wrapped with RSA, and nothing for data already recorded by an adversary.

For the archive, re-wrap. Envelope encryption makes this a metadata operation. Each object has a data encryption key wrapped by a key encryption key, so re-wrapping the small keys under a post-quantum key leaves the bulk data untouched. An archive designed that way migrates in hours. An archive that encrypted each object directly under an asymmetric key must be fully re-encrypted, which is why the envelope pattern is worth adopting before it is needed.

For data already recorded by an adversary, there is no technical remedy. The recording exists and the algorithm will fall. The response is a risk assessment: what was transmitted, over what period, under what protection, and what is the consequence when it becomes readable. That assessment belongs in the migration plan, because it is the only part of the problem that engineering cannot fix.

Sources and further reading

FIPS 203, FIPS 204, and FIPS 205 from NIST, and the NIST post-quantum cryptography project pages for HQC and for the additional signature standardization. NIST SP 1800-38 on migration to post-quantum cryptography. Peter Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", 1997. Craig Gidney and Martin Ekera on factoring resource estimates, and Gidney's 2025 revision. Michele Mosca on the timeline inequality. RFC 8446 for TLS 1.3 and the IETF drafts on ML-KEM hybrid key agreement and on post-quantum recommendations for TLS applications. The CNSA 2.0 advisory from the NSA.