What breaks, what bends: Shor, Grover and your keys

Public-key cryptography rests on a few mathematical problems that are easy to set up and hard to undo. Multiplying two primes is quick; recovering them from the product is not. Multiplying a curve point by a secret number is quick; recovering the number from the result is not. Every Solana keypair, every TLS handshake and every hardware wallet depends on one of these one-way problems.

Symmetric cryptography works differently. AES and SHA-256 have no hidden algebraic structure to exploit. Their security comes from the absence of any shortcut better than trying keys or inputs one by one.

A quantum computer is not a faster general-purpose computer. It is very good at a narrow class of problems with a particular periodic structure, and the public-key problems above happen to have exactly that structure. That is why the threat is lopsided.

In 1994 Peter Shor showed that factoring and discrete logarithms both reduce to finding the period of a function, and that a quantum computer can find that period efficiently with the quantum Fourier transform. The same approach works on the group of points of an elliptic curve. The practical result is simple: given a public key, recover the private key.

Making the key bigger does not buy much. The attack scales polynomially with key size, so doubling a key only makes the attacker's job somewhat more expensive. These primitives have to be replaced, not resized.

On Solana this lands harder than on some other chains. A wallet address is its Ed25519 public key, written in base58. Nothing hides the key behind a hash, so every funded wallet already publishes exactly what Shor's algorithm needs. Program Derived Addresses are the exception: they are deliberately chosen off the curve, have no private key at all, and are controlled by their program. Chapter 04 goes into this.

Lov Grover's 1996 algorithm searches an unstructured space of N possibilities in roughly √N steps. Applied to a k-bit key, the textbook cost falls from 2^k to about 2^k/2. That sounds dramatic until you look at the details. Grover's steps must run one after another; spreading the search over M machines only cuts the time by √M, not M. And each step on an error-corrected machine is slow and expensive.

NIST defines its post-quantum security categories against exactly these costs. Category 1 means at least as hard as finding an AES-128 key, category 3 as hard as AES-192, category 5 as hard as AES-256, with categories 2 and 4 tied to SHA-256 and SHA-384 collisions.

The practical advice is short. Hashes and symmetric ciphers do not need replacing. Prefer 256-bit keys where data must stay protected for a long time. SHA-256, which Solana uses for Proof of History and to derive PDAs, is not the weak point.

Running Shor against real key sizes needs a large, fault-tolerant quantum computer: many physical qubits per logical qubit, corrected continuously over a long computation. Published resource estimates have fallen steadily. A 2025 estimate by Craig Gidney put 2048-bit RSA at under a million noisy qubits running for about a week. Earlier work by Roetteler and colleagues found that 256-bit elliptic-curve keys need fewer logical qubits than RSA-2048. Today's largest machines are far from either figure, and no cryptographic-size key has been broken.

Trellis does not publish a Q-day estimate, and you should be wary of anyone who sells one. The useful signals are institutional. NIST finalised FIPS 203, 204 and 205 in August 2024. Its draft transition report, NIST IR 8547, proposes deprecating quantum-vulnerable public-key algorithms after 2030 and disallowing them after 2035 for US federal systems. Vendors tend to follow those dates.

Secrecy is exposed now. If X25519 set up a session key, anyone who records the handshake and the encrypted traffic can decrypt it once X25519 breaks. This is “store now, decrypt later”. Data that must stay private for ten years is already at risk if it crosses the network under classical key exchange today. Chapter 03 covers the fix.

Signatures are exposed later, but wider. A forged signature only matters once someone can produce one, so nothing you sign today is forged today. The catch is that blockchain keys live a long time. When a capable machine appears, every key still controlling funds or authority becomes forgeable at once, and recorded history cannot be re-signed.

• Long-lived keys are the main signature risk: treasury wallets, program upgrade authorities, mint and freeze authorities, multisig members and validator withdraw keys.
• Pre-signed transactions, such as those built on durable nonces, stay valid until used, which stretches the window.
• Short-lived keys that sign once and are thrown away carry far less risk.

The 2024 NIST standards give one replacement per broken role. ML-KEM replaces Diffie–Hellman-style key exchange. ML-DSA is the default replacement for signatures. SLH-DSA is a slower, larger signature whose security depends only on hash functions, for cases where conservatism matters more than size.

The replacements are bigger than what they replace, often by one or two orders of magnitude, and that is where the engineering pain sits. Chapter 02 puts numbers on it. The Lab lets you watch the difference on your own machine.