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.