The Quantum Threat to Current Cryptography
Why Today's Encryption Is Vulnerable
The security of most asymmetric cryptography rests on problems that are computationally hard classically — chiefly integer factorisation (RSA) and the discrete logarithm problem (Diffie-Hellman, elliptic curve). Shor's algorithm solves both in polynomial time on a quantum computer.
Symmetric algorithms (AES) and hash functions (SHA) are less severely affected — Grover's algorithm provides only a quadratic speedup, effectively halving the security level. Doubling key sizes (e.g. AES-256 instead of AES-128) is sufficient mitigation.
Timeline urgency: Even though cryptographically capable quantum computers are likely years or decades away, the threat is present tense due to "harvest now, decrypt later" attacks: adversaries are recording encrypted traffic today to decrypt it once quantum hardware matures. Sensitive long-lived secrets must be protected now.
Quantum Threat Assessment
Lattice-Based Cryptography
Learning With Errors (LWE)
The hard problem: Given many equations of the form b = ⟨a, s⟩ + e (mod q), where a is a public random vector, s is a secret vector, and e is a small random error — recover s. Even with access to arbitrarily many such equations, no known classical or quantum algorithm solves this efficiently for appropriate parameters.
Why it's quantum-resistant: LWE is reducible in the worst case to hard lattice problems (CVP, SVP). Grover's algorithm provides only a quadratic speedup over brute-force search — insufficient to break well-parameterised LWE schemes. No structure analogous to the periodicity exploited by Shor's algorithm is known.
CRYSTALS-Kyber (ML-KEM): A key encapsulation mechanism based on Module-LWE. Selected by NIST as FIPS 203 (August 2024) — the primary standard for quantum-safe key exchange.
CRYSTALS-Dilithium (ML-DSA): A digital signature scheme based on Module-LWE and Module-SIS. Standardised as FIPS 204. Provides authentication and non-repudiation.
Post-Quantum Algorithm Families
Lattice-Based
The dominant family. Hard problems: LWE, NTRU, SIS. Standards: Kyber (KEM), Dilithium and FALCON (signatures). Good performance and compact key sizes relative to other PQC families.
Hash-Based
Security depends only on hash function collision resistance — one of the most battle-tested assumptions in cryptography. SPHINCS+ (FIPS 205) is stateless; XMSS and LMS (NIST SP 800-208) are stateful with smaller signatures.
Code-Based
Based on the hardness of decoding random linear error-correcting codes. McEliece (1978) is the oldest PQC proposal. Very fast decryption but very large public keys (hundreds of kilobytes to megabytes). Classic McEliece is an alternate NIST standard.
Cautionary Examples
Rainbow (multivariate) was broken in 2022 by a classical attack. SIKE (isogeny-based) was broken in 2022 by a classical algorithm on a laptop. These demonstrate that PQC security assumptions must be actively tested — new schemes should be treated with caution.
NIST PQC Standardisation (2024)
The First Post-Quantum Standards
After a seven-year international evaluation process involving hundreds of submissions and thousands of cryptanalysts, NIST published its first post-quantum cryptography standards in August 2024. These are drop-in replacements for RSA and ECDSA in TLS, code signing, and other protocols.
Deployment Considerations