Post-Quantum Cryptography

Core Idea

Shor's quantum algorithm solves factoring and discrete logarithms in polynomial time, breaking RSA, DH, ECDH, and ECDSA. Post-quantum cryptography (PQC) develops replacements based on problems believed resistant to quantum attack: lattices (ML-KEM, ML-DSA), hash functions (SPHINCS+/SLH-DSA), codes (Classic McEliece), and multivariate polynomials. NIST standardized ML-KEM and ML-DSA in 2024, based on Module-LWE/Module-SIS. The "harvest now, decrypt later" threat (adversaries store encrypted traffic for future quantum decryption) motivates immediate transition, even before large quantum computers exist. Hybrid approaches pair PQC with classical algorithms during the migration.

Explainer

Post-quantum cryptography (PQC) is the urgent project of replacing the public-key algorithms (RSA, DH, ECDH, ECDSA) that secure the internet with alternatives that resist quantum computers. The threat is specific and devastating: Shor's algorithm solves integer factoring and discrete logarithms in polynomial time on a quantum computer, completely breaking RSA (factoring), Diffie-Hellman (discrete logs in multiplicative groups), and elliptic curve cryptography (discrete logs in elliptic curve groups). A sufficiently large quantum computer would break every HTTPS connection, every digital signature, and every encrypted email that relies on these algorithms.

The urgency comes from the "harvest now, decrypt later" threat model. State-level adversaries are believed to be recording encrypted internet traffic today, storing it for future decryption once quantum computers mature. Data that must remain confidential for 20+ years (classified information, medical records, long-term business secrets) is already at risk if encrypted with quantum-vulnerable algorithms. The migration timeline compounds the urgency: replacing cryptographic algorithms across global infrastructure — browsers, servers, hardware security modules, embedded systems, satellites — takes years. Starting the transition after quantum computers arrive means years of additional vulnerability.

NIST finalized its first PQC standards in 2024 after an 8-year evaluation process. ML-KEM (Module-Lattice Key Encapsulation Mechanism, based on Kyber) replaces ECDH for key exchange, with public keys around 800-1500 bytes and encapsulation times under a millisecond. ML-DSA (Module-Lattice Digital Signature Algorithm, based on Dilithium) replaces ECDSA for signatures, with ~2.4 KB signatures. Both are based on Module-LWE/Module-SIS, lattice problems believed to resist quantum attacks. SLH-DSA (Stateless Hash-based Digital Signature Algorithm, based on SPHINCS+) provides an alternative signature scheme relying only on hash function security — larger signatures (8-50 KB) but based on the most conservative assumptions. The devastating 2022 break of SIDH/SIKE (an isogeny-based finalist that fell to a polynomial-time attack after a decade of study) reinforced the importance of this algorithmic diversity.

The transition strategy involves hybrid approaches: pairing classical algorithms with PQC counterparts so that security holds if either algorithm survives. Chrome and Firefox already support hybrid TLS key exchange (X25519 + ML-KEM). The combined key is derived from both algorithms' outputs, ensuring that a break in ML-KEM (if lattice assumptions fail) leaves ECDH protection intact, while a quantum attack on ECDH leaves ML-KEM protection intact. This belt-and-suspenders approach will likely persist for years as the cryptographic community builds confidence in the new standards. The PQC transition is the largest coordinated change in deployed cryptographic infrastructure since the adoption of public-key cryptography itself, touching every system that establishes secure connections or verifies digital signatures.