Physics

What Shor’s algorithm actually breaks

Peter Shor published his quantum algorithm in 1994. It solves two problems in polynomial time on a quantum computer: integer factorisation (the hardness assumption behind RSA) and the discrete logarithm problem (the hardness assumption behind Diffie-Hellman and elliptic-curve cryptography). These are the two mathematical foundations that underpin essentially all classical public-key cryptography in production today. A quantum computer running Shor’s algorithm at scale changes RSA-2048 from a GNFS-classical factoring problem estimated around 2^110-2^117 operations (~10^33-10^35) into a polynomial-time quantum computation.

Grover’s algorithm provides a quadratic speedup for brute-force key search, which reduces the effective security of symmetric algorithms. AES-256 retains roughly 128-bit post-quantum security under Grover, which remains acceptable. The asymmetric algorithms — RSA, ECC, DH — have no equivalent mitigation at their current key sizes and must be replaced entirely.

Module-LWE: the problem quantum computers cannot solve efficiently

The Learning With Errors (LWE) problem asks: given a set of linear equations over a finite field with small random errors added to each equation, recover the secret vector. In the module variant (Module-LWE), the equations are structured as polynomial matrices, which gives much more compact key representations while preserving the hardness guarantee. Unlike integer factorisation, no one has found a quantum algorithm that solves Module-LWE faster than the best classical algorithms — and the problem has been studied intensively since Regev introduced LWE in 2005.

This is not an absence of effort: NIST’s PQC competition ran from 2016 to 2024 and involved hundreds of cryptanalysts attacking the candidate algorithms. ML-KEM and ML-DSA emerged from that process with no meaningful structural attacks against their Module-LWE foundation. The Kyber round-3 analysis lists Kyber1024 at 232-bit quantum core-SVP hardness — a margin no foreseeable quantum hardware could reach.

IND-CCA2 security and what it guarantees

IND-CCA2 (indistinguishability under adaptive chosen-ciphertext attack) is the standard security model for key encapsulation mechanisms. It means an adversary who can submit arbitrary ciphertexts for decapsulation and observe the result still cannot distinguish a real encapsulated key from a random one. This is the relevant property for TLS-style handshakes where a network adversary can send crafted messages to probe for oracle behavior.

ML-KEM achieves IND-CCA2 security through the Fujisaki-Okamoto transform applied to an IND-CPA-secure public-key encryption scheme built on Module-LWE. The security reduction is tight in the quantum random oracle model (QROM), meaning the proof holds against quantum adversaries making superposition queries to hash functions. This is important: many earlier post-quantum proposals had classical security proofs that did not extend cleanly to the quantum setting.

Security estimates in practice

ML-KEM-1024 is the category-5 ML-KEM parameter set in FIPS 203. In the Kyber round-3 concrete security analysis, Kyber1024 is listed at 256 classical and 232 quantum core-SVP hardness. Those estimates are derived from the best known lattice reduction algorithms and remain the right way to discuss Kyber1024 security margins.

For engineering teams: the practical difference between a 232-bit quantum core-SVP estimate and a 256-bit classical estimate is negligible against any foreseeable attacker. The binding constraint on PQC adoption is operational — certificate lifecycle, HSM throughput, handshake latency — not the margin of safety in the underlying math. Talk to our security team if you want to walk through the security proof and implementation details for your specific deployment context.