Post-quantum cryptography

On 13 August 2024 NIST issued its first three post-quantum standards. ML-KEM (key encapsulation) derives from CRYSTALS-Kyber; ML-DSA (signatures) from CRYSTALS-Dilithium; SLH-DSA (stateless hash-based signatures) from SPHINCS+. They are the algorithms the rest of this section assumes you will migrate to.

On 11 March 2025 NIST selected HQC, a code-based key-encapsulation scheme, as a backup to ML-KEM — deliberately not lattice-based, so a future break of lattice assumptions would not take down both. ML-KEM remains the primary recommendation.

NIST's transition roadmap (initial public draft, November 2024) sets two dates: algorithms providing ~112 bits of security — RSA-2048, ECDSA/ECDH on P-256 — are deprecated after 2030 (no new use), and all quantum-vulnerable public-key algorithms are disallowed after 2035. The window between is the intended migration runway. Note: the document is an initial public draft; the dates are NIST's stated plan.

Michele Mosca's framing (IEEE Security & Privacy, 2018): let X be how long your data must stay secret, Y how long your migration to quantum-safe cryptography takes, and Z how long until a cryptographically relevant quantum computer exists. If X + Y > Z, some data you protect today will be exposed. Because Z is uncertain and X can be decades for medical, legal or state secrets, the rational move is to shrink Y now.

An adversary can record encrypted traffic today and decrypt it when a capable machine arrives. Key exchange (RSA, ECDH) is the exposure: anything whose confidentiality must outlast the arrival of such a machine is at risk the moment it crosses the wire under classical public-key protection. This is the threat model NIST's 2030/2035 dates are built around, and why migration of key exchange is prioritized over signatures.

Only public-key cryptography is exposed to Shor's algorithm. Symmetric ciphers and hashes face at most Grover's quadratic speedup, which must run serially to realize; NIST's own FAQ states it is 'quite likely that Grover's algorithm will provide little or no advantage in attacking AES, and AES 128 will remain secure' — NIST even uses AES-128 as the security baseline for its post-quantum categories. Migration effort belongs on key exchange and signatures.

The foundational surface-code resource analysis. Its order-of-magnitude figure of roughly a billion physical qubits became the baseline that framed the urgency of NIST's 2016 call for post-quantum algorithms.

Assuming a planar superconducting grid, 10⁻³ physical error rate, 1 µs surface-code cycle: ~20 million physical qubits, ~2.7 billion Toffoli gates, ~8 hours. A roughly 50× reduction from the 2012 baseline.

The lowest published estimate as of this page's check date: a 20× reduction in qubits from the 2021 figure, at the cost of a longer runtime, using approximate residue arithmetic and yoked surface codes. A preprint; the direction of travel — down, fast — is the point.