Post-quantum cryptography: lattices, codes, and the migration

The threat model that drives the post-quantum migration is not 'a quantum computer can break RSA today.' It is:

An adversary records ciphertexts today. If a fault-tolerant quantum computer of sufficient scale exists at some future time $T$, the recorded ciphertexts can be decrypted retroactively.

Data whose value extends past $T$ is at risk now, regardless of whether the quantum computer exists yet. Examples include long-lived secrets such as:

• Government and diplomatic communications with multi-decade sensitivity.
• Medical records, genetic data, and personal information with lifetime relevance.
• Trade secrets and IP whose value persists over patent lifetimes (20+ years).
• Cryptographic root materials that anchor longer-lived trust chains.

This is the harvest-now, decrypt-later framing. It uncouples the migration timeline from the quantum-hardware timeline: even if useful quantum computers are far away, traffic encrypted with quantum-vulnerable algorithms today exposes data whose confidentiality requirement outlasts the gap.

The migration is therefore treated by major standardization bodies and many enterprises as an immediate operational priority, independent of any specific prediction about when the cryptographic threat materializes.

Recapping the previous lesson with the operational consequences:

Public-key schemes whose security rests on factoring or discrete logarithms are broken by Shor's algorithm at scale:

• RSA — encryption and signatures. Used in TLS certificates, code signing, document signatures.
• DH and ECDH — key exchange. Used in TLS, IPsec, SSH key exchange.
• DSA, ECDSA, EdDSA — signatures. Used in TLS, SSH host keys, code signing, certificate authorities.

Every deployment of these schemes — every TLS handshake, every signed firmware update, every certificate-chain validation — needs to be re-engineered to use a quantum-resistant replacement.

Symmetric primitives require larger sizes but not replacement:

• AES — Grover's algorithm gives quadratic speedup against brute-force key search, so 256-bit keys provide ~128-bit post-quantum security. AES-256 is widely considered post-quantum acceptable; AES-128 is not.
• SHA-2, SHA-3 — Grover's quadratic speedup against preimage/second-preimage attacks similarly. Output sizes of 256 bits provide ~128-bit post-quantum security.

The migration is therefore concentrated in the public-key infrastructure: key exchange, signatures, and the certificate hierarchy that depends on them.

Lattice-based cryptography is the leading family of post-quantum schemes. Its security rests on the assumed hardness of two problems.

Learning With Errors (LWE). Given a secret vector $\vec{s} \in \mathbb{Z}_q^n$ and many pairs $(\vec{a}_i, b_i)$ where

$b_i = \langle \vec{a}_i, \vec{s} \rangle + e_i \pmod{q}$

with $\vec{a}_i$ random and $e_i$ a small random error, recover $\vec{s}$. Without the errors, the system would be a solvable linear system; the errors transform it into a problem whose best known classical algorithms are exponential in $n$.

Ring-LWE (R-LWE) and Module-LWE. Variants of LWE where the linear algebra happens in a polynomial ring (e.g., $\mathbb{Z}_q[x]/(x^n+1)$). The additional algebraic structure enables compact keys and fast operations while preserving the conjectured hardness.

Lattice problems sit at the intersection of two structural reasons for confidence:

• Worst-case to average-case reductions. Solving random LWE instances is at least as hard as solving the worst-case lattice problem in a related family. This is a stronger guarantee than most public-key schemes provide.
• No known quantum speedup. Despite three decades of analysis, the best known quantum algorithms for lattice problems offer only modest polynomial improvements over classical, far from the exponential gap Shor achieves for factoring.

The US National Institute of Standards and Technology (NIST) ran a multi-round public competition starting in 2016 to standardize post-quantum cryptographic algorithms. The process drew submissions from cryptographers worldwide, with public analysis and successive rounds of pruning over six years.

The initial standards published in 2024 cover three primitives:

• ML-KEM (Module-Lattice Key Encapsulation Mechanism) — originally Kyber. A key encapsulation mechanism (KEM) for establishing a shared secret. Used in place of RSA-KEM and DH-style key exchange. Parameter sets ML-KEM-512, -768, -1024 corresponding to roughly AES-128, -192, -256 security levels.
• ML-DSA (Module-Lattice Digital Signature Algorithm) — originally Dilithium. A digital signature scheme. Used in place of RSA and ECDSA signatures. Parameter sets ML-DSA-44, -65, -87.
• SLH-DSA (Stateless Hash-Based Digital Signature Algorithm) — originally SPHINCS+. A hash-based signature scheme with security resting only on hash-function properties. Used where a non-lattice fallback is desired.

A fourth lattice-based signature, FALCON, was selected for standardization in a separate track.

NIST also continues evaluating additional KEMs (HQC, BIKE — code-based) and signatures (CROSS, LESS, others) in ongoing rounds, partly to maintain algorithm diversity in case future cryptanalysis weakens one family.

Post-quantum schemes generally have larger keys and ciphertexts than RSA or ECC, with different speed profiles. Rough numbers for security levels comparable to AES-128:

The key-and-ciphertext-size differences propagate through every protocol. TLS handshakes carrying ML-KEM keys add roughly 2 KB per handshake compared to ECDH; signed certificate chains using ML-DSA add several KB per signature. Most networks handle the additional bytes; some constrained environments (IoT, embedded, satellite links) require careful engineering or alternate algorithm choices.

The lesson: post-quantum schemes are operationally viable for most deployments, but each is a different shape than RSA/ECC. Migration is not a drop-in replacement; it is a re-engineering of protocols around new key and message sizes.

The standard transition strategy is hybrid mode: a deployed system uses both a classical (RSA/ECC) and a post-quantum (ML-KEM, ML-DSA) algorithm simultaneously, deriving the session key from the combination.

For key exchange:

$K_{\text{session}} = \text{KDF}(K_{\text{ECDH}} \| K_{\text{ML-KEM}})$

The session is secure as long as at least one of the two algorithms remains unbroken. This hedges against:

• A future quantum computer breaking ECDH but not ML-KEM (the primary motivation).
• A future cryptanalytic advance breaking ML-KEM but not ECDH (the secondary motivation; new schemes are less battle-tested).

Major deployments — TLS in browsers (Chrome, Firefox), CDNs (Cloudflare), VPN providers, SSH servers — have rolled out hybrid X25519+ML-KEM key exchange in stages from 2023 onward.

For signatures, hybrid is operationally more complex (each signature adds size; certificate chains get longer; verification adds cost). Several drafts propose hybrid certificate formats; others propose phased migration where leaf certificates migrate before root authorities, or vice versa.

The migration is multi-year by design. Major TLS deployments expect to retain hybrid mode for an extended period before deprecating classical algorithms outright, to give the ecosystem time to adapt and to gain confidence in the post-quantum components.

A second-order lesson from the post-quantum migration is the value of crypto agility — the ability of a deployed system to change its cryptographic primitives without re-architecting the surrounding system.

Properties of crypto-agile systems:

• Algorithm identifiers in protocols and certificates — schemes are negotiated, not hardcoded.
• Negotiation that survives mixed-algorithm peers — clients and servers can fall back gracefully when one side does not support a primitive.
• Modular cryptographic libraries — the API does not assume key sizes, message sizes, or specific operation latencies.
• Key rotation and re-issuance pipelines — certificate authorities, key-management systems, and rotation tooling can issue keys in the new format without manual intervention.
• Inventory of deployed cryptographic primitives — operators know what algorithms are used where, so migration can be targeted.

Many legacy systems lack one or more of these properties. The TLS protocol is highly agile (suite negotiation has been a feature since SSL 3.0); some application-layer cryptography (signed firmware, document signatures, custom protocols) is much less agile and may require system redesign rather than a parameter swap.

The post-quantum migration is a test of crypto agility at industry scale. Systems whose crypto choices were embedded into protocol layers, embedded firmware, or third-party libraries with limited update channels face the largest engineering effort.

Pulling the cursus together. The structural picture as of the migration:

• The threat is bounded in scope. Shor breaks public-key schemes based on factoring and discrete logarithms; AES and SHA-2 with appropriate sizes remain. The migration is concentrated in public-key infrastructure, not symmetric cryptography.
• The replacements exist and are standardized. ML-KEM, ML-DSA, SLH-DSA, and FALCON cover key exchange and signatures. Their security rests on lattice and hash assumptions that are believed hard for quantum but should be treated with the usual cryptographic caution about new schemes.
• The migration is operationally significant but feasible. Larger keys and messages propagate through every layer that touches cryptography, but most modern protocols (TLS, SSH, IPsec) have negotiation mechanisms that accommodate the transition.
• Crypto agility is the long-run lesson. A system built to swap algorithms cleanly handles this migration and the next one; a system with hardcoded primitives requires engineering effort each time.

The quantum-computing field as a whole — six lessons in — has been described mostly in terms of structure: the math of qubits, the engineering trade-offs of hardware, the overhead arithmetic of error correction, the algorithmic conditions for speedup, the operational mechanics of cryptographic migration. The numbers that fit into this structure will continue to change; the structure itself is what supports reasoning about the field as it evolves.