A CISO Introduction to Quantum: Why RSA and Elliptic Curves Fall and Lattices Replace Them

A quantum computer threatens today's public-key encryption for one reason. The mathematics underneath has a shape, and a quantum computer can see a shape that a classical computer has to trace one step at a time.

The analogy: a bus route and a grid

Today's encryption follows a route, like a bus line winding through an old city. RSA and elliptic curves are hard to guess at street level and obvious from above. A quantum computer has the map view, where the shape gives the route away.

A lattice replaces the old city with a strict modern grid. Every street corner looks like every other, so the view from above reveals nothing about which corner holds the secret. The bigger the grid, the harder the guess.

Two isometric city blocks side by side under the heading “A quantum computer has the map view.” On the left, labelled RSA and elliptic curves, an orange bus route winds through an irregular old city and is drawn again on a plane above it: hard to guess at street level, obvious from above. On the right, labelled Lattice, identical blocks stand on a strict grid and the plane above shows a uniform grid of points: every corner looks like every other, and the bigger the grid, the harder the guess.

The picture is a simplification. The sections below state what stands behind each half of it.

What Shor's algorithm exploits in RSA and elliptic curves

Peter Shor showed in 1994 that a quantum computer can factor integers and compute discrete logarithms in polynomial time. RSA rests on factoring. Elliptic curve cryptography rests on a discrete logarithm. Both problems reduce to finding a hidden period, a pattern that repeats across the whole problem, and period finding is the task where a quantum computer outperforms every known classical method.

That period is the bus route. A classical attacker rides it one stop at a time and runs out of time. A quantum attacker sees the whole loop at once. The hardware to run the attack at cryptographic key sizes has yet to be built, and 256-bit elliptic curves fall sooner than RSA-2048 on the same hardware.

What the Aaronson-Ambainis proof adds

Physical Superintelligence announced a proof of the Aaronson-Ambainis conjecture on November 6, 2026. The conjecture comes from a 2009 paper by Scott Aaronson and Andris Ambainis titled The Need for Structure in Quantum Speedups. Its consequence for yes-or-no problems: on an input with no hidden pattern, a quantum algorithm can beat a classical one by a polynomial factor at most, measured by how much of the input each has to read.

An AI research system produced the proof, and the Lean proof assistant checked it. Aaronson has written that he believes it is correct, citing the machine check and review by human experts. Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, who proved a special case in August, have published an exposition of the proof. The paper has yet to go through journal review.

For a security audience the result puts a theorem behind one sentence: an exponential quantum advantage requires structure. The map view helps where there is a route to see. The scope is narrow. The theorem counts reads of the input and covers decision problems on most inputs. It makes no statement about any specific cryptosystem.

Why lattices are the replacement

ML-KEM, standardized as FIPS 203, rests on the Module Learning with Errors problem: recovering a secret from equations over a high-dimensional lattice after small errors have been added. Nobody has found a hidden period there for Shor's method to use, and no other efficient quantum algorithm for the problem is known.

That hardness is a conjecture. It rests on decades of failed attacks, including a quantum claim that was refuted in August. The Aaronson-Ambainis proof leaves that status unchanged. It explains why the quantum threat concentrates on RSA and elliptic curves, and lattice security continues to rest on its own evidence.

What this means for migration order

Key exchange moves first. Traffic recorded today can be decrypted once a capable quantum computer exists, so the exposure begins at the moment of capture. The deployed answer is hybrid key exchange. RFC 10024 defines X25519MLKEM768, which runs the elliptic curve and the lattice together so that the session stays secure while either one holds.

Signatures follow, because forging one requires a quantum computer at the time of the attack. ML-DSA is final and its certificate path is specified, and the case for starting with leaf certificates is made separately.

Both steps begin with an inventory of the endpoints that still negotiate a curve alone. [PQ]probe reports the key exchange groups and signature algorithms each endpoint negotiates, which gives the migration a list of hosts to work from.

Sources:

All [PQ]files