Quantum computers do not break all cryptography. They break specific cryptography — the public-key systems built on the difficulty of factoring integers and computing discrete logarithms. Understanding precisely what is threatened, what is not, and what replaces the threatened algorithms is essential for building systems that must remain secure for decades.
Shor’s algorithm efficiently solves two mathematical problems that underpin most deployed public-key cryptography:
Integer factorization: RSA’s security rests on the difficulty of factoring the product of two large primes. A sufficiently powerful quantum computer running Shor’s algorithm factors an n-bit integer in polynomial time, breaking RSA at any key size. Doubling the key size does not help — the speedup is exponential over classical algorithms.
Discrete logarithms: Diffie-Hellman key exchange and ECDSA signatures rely on the hardness of the discrete logarithm problem in finite fields and elliptic curve groups. Shor’s algorithm solves discrete logarithms with the same polynomial speedup, breaking ECDH, ECDSA, and EdDSA regardless of curve or parameter choice.
Every TLS handshake today uses ECDHE for key exchange and ECDSA or RSA for authentication. Both are vulnerable to a cryptographically relevant quantum computer (CRQC).
As of the mid-2020s, the largest quantum computers have thousands of noisy qubits — far short of the estimated millions of error-corrected logical qubits needed to break RSA-2048 or P-256. Estimates for achieving this range from 10 to 30 years. The uncertainty matters less than it appears: systems deployed today that must protect data for decades (medical records, national security, financial archives) are already within the threat window. This is the “harvest now, decrypt later” problem.
Symmetric cryptography: Grover’s algorithm provides a quadratic speedup for brute-force search, effectively halving the security level of symmetric keys. AES-128 drops to 64-bit security (breakable); AES-256 drops to 128-bit security (still secure). The fix is straightforward: use 256-bit symmetric keys.
Hash functions: Grover’s algorithm also applies to hash preimage search, halving the effective security. SHA-256 retains 128-bit preimage resistance against quantum attackers — still well beyond feasible attack range. Hash-based signatures (like SPHINCS+) remain secure because they rely only on hash function properties.
Symmetric MACs: HMAC-SHA-256 and similar constructions retain adequate security with standard-length keys.
The practical consequence: only the asymmetric components of cryptographic systems need replacement. Symmetric encryption, hashing, and MACs continue to work — just ensure key sizes provide adequate post-quantum margin.
Grover’s quadratic speedup sounds dramatic but is far less impactful than Shor’s exponential speedup. Breaking AES-128 classically requires 2^128 operations. Grover’s reduces this to 2^64 — which is feasible but expensive. Breaking AES-256 requires 2^256 operations classically and 2^128 with Grover’s — which is as hard as breaking AES-128 classically. Furthermore, Grover’s algorithm is difficult to parallelize: running it on k quantum computers only provides a factor-of-k speedup, not the k-squared speedup that classical parallelism offers for brute-force search. The quantum threat to symmetric crypto is real but manageable.
After an eight-year evaluation process, NIST standardized three post-quantum algorithms in 2024:
ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism), originally known as CRYSTALS-Kyber, replaces ECDH for key exchange. It is a key encapsulation mechanism (KEM) — the sender encapsulates a shared secret using the recipient’s public key, and the recipient decapsulates it with their private key. ML-KEM-768 provides roughly 128-bit post-quantum security with public keys of about 1,184 bytes and ciphertexts of about 1,088 bytes.
ML-DSA (Module-Lattice-Based Digital Signature Algorithm), originally CRYSTALS-Dilithium, replaces ECDSA and EdDSA for digital signatures. ML-DSA-65 provides roughly 128-bit post-quantum security with public keys of about 1,952 bytes and signatures of about 3,293 bytes.
SLH-DSA (Stateless Hash-Based Digital Signature Algorithm), originally SPHINCS+, is a hash-based signature scheme that relies only on the security of hash functions — no lattice assumptions. Signatures are larger (up to tens of kilobytes) but the security assumption is more conservative. SLH-DSA serves as a fallback if lattice-based schemes are broken.
All ML-KEM and ML-DSA constructions are based on the hardness of problems in structured lattices — specifically, the Module Learning With Errors (MLWE) problem. Given a system of “noisy” linear equations over a ring, recover the secret vector. The noise makes the problem hard even for quantum computers — no quantum algorithm provides a significant speedup over classical attacks. Lattice problems have been studied for decades, and the best known algorithms (both classical and quantum) run in exponential time. The structured variant (using polynomial rings) enables compact keys and fast operations compared to unstructured lattice schemes.
An adversary records encrypted traffic today — TLS sessions, VPN tunnels, encrypted emails. The ciphertext is stored, perhaps for years. When a sufficiently powerful quantum computer becomes available, the adversary decrypts all stored traffic retroactively.
This threat is real and active. Intelligence agencies have the storage capacity and the motivation. Data with a long secrecy requirement — state secrets, medical records, corporate intellectual property, attorney-client communications — is at risk today, even though the quantum computer that will decrypt it does not yet exist.
The implication: the deadline for migrating to post-quantum key exchange is not when quantum computers arrive. It is when the data’s required secrecy period exceeds the time until quantum computers arrive. For data that must remain confidential for 25 years, and quantum computers estimated in 15 years, the migration deadline was 10 years ago.
Harvest-now-decrypt-later affects confidentiality (encryption) but not authentication (signatures). A digital signature verified today is not threatened by a future quantum computer — the signature has already served its purpose. But a key exchange performed today protects data that may still be sensitive when quantum computers arrive. This asymmetry is why post-quantum key exchange (ML-KEM) is more urgent than post-quantum signatures (ML-DSA). Migrate key exchange first.
The post-quantum algorithms are newer and less battle-tested than RSA and ECDSA, which have decades of cryptanalysis behind them. A hybrid approach combines a classical algorithm with a post-quantum algorithm — an attacker must break both to compromise the system.
Hybrid key exchange: the TLS handshake performs both an ECDHE key exchange (X25519) and an ML-KEM encapsulation. The session key is derived from both shared secrets. If ML-KEM is broken by a future classical attack, X25519 still protects the session. If a quantum computer breaks X25519, ML-KEM still protects the session.
Hybrid signatures: a certificate contains both a classical signature (ECDSA) and a post-quantum signature (ML-DSA). Verifiers check both. This is more complex to deploy because certificate formats and validation logic must support dual signatures.
Chrome and other browsers have already deployed hybrid key exchange (X25519Kyber768) in TLS. The performance cost is modest — ML-KEM adds roughly 2 KB to the handshake and negligible computation time.
NIST recommends deprecating RSA-2048 and 128-bit elliptic curve keys by 2030 and disallowing them by 2035. Organizations should begin post-quantum migration now: inventory all systems using public-key cryptography, prioritize systems handling long-lived confidential data, deploy hybrid key exchange in TLS and VPN, and plan for post-quantum certificate chains. The migration is comparable in scope to the SHA-1-to-SHA-2 transition, but the consequences of delay are more severe — there is no “SHA-1 is weakened but still usable” phase for quantum-vulnerable algorithms. When a CRQC arrives, RSA and ECC break completely, not gradually.
This lesson establishes:
Next: Cryptographic Failures