Shor, Grover and what a quantum computer actually breaks

Why this is a question at all#

Almost every blockchain, browser and messaging app relies on a small number of public-key primitives. Their security rests on mathematical problems believed to be hard for ordinary computers: factoring large integers (RSA) and computing discrete logarithms in finite-field or elliptic-curve groups (Diffie–Hellman, ECDSA, EdDSA, X25519). The best known classical algorithms for those problems take time that grows faster than any polynomial in the key size, so adding bits makes attacks impractical very quickly.

A quantum computer is not a faster classical computer. It manipulates qubits whose joint state can encode interference patterns across many values at once, and a carefully designed algorithm can make the wrong answers cancel out and the right one become likely when measured. For most problems this gives no meaningful advantage. For a few problems with the right algebraic structure, the advantage is dramatic. Two algorithms matter for cryptography: Shor's and Grover's.

Shor's algorithm: the one that breaks things#

In 1994 Peter Shor showed that a quantum computer can find the period of a function efficiently. Factoring an integer and computing a discrete logarithm can both be reduced to period-finding, so both become solvable in polynomial time. The same idea extends to the discrete-logarithm problem on elliptic curves, which is the problem under Ed25519, ECDSA over secp256k1 and secp256r1, and X25519 key agreement.

The consequence is not a slow erosion. If a cryptographically relevant quantum computer (often abbreviated CRQC) exists, then given a public key it can recover the matching private key. Increasing the key size does not restore a comfortable margin, because the attack cost grows only polynomially with key size. That is why the response is to replace these primitives, not to lengthen them.

For a Solana builder the important consequence is concrete. Every Solana account address that belongs to a keypair is an Ed25519 public key, encoded in base58. There is no hash in front of it. Anyone holding a CRQC could take any such address, derive its private key, and sign as that account. Program Derived Addresses are different: they are deliberately chosen to have no private key at all, and are covered in chapter 04.

Grover's algorithm: the one that only dents things#

Grover's algorithm (1996) speeds up unstructured search. Classically, finding one marked item among N candidates takes on the order of N guesses. Grover needs on the order of the square root of N quantum steps. Applied to a 128-bit symmetric key, the naive count drops from about 2^128 to about 2^64 operations.

That sounds alarming until you look at what the count leaves out. Grover's iterations are inherently sequential: splitting the search across many machines reduces the speed-up rather than multiplying it, and each iteration has to evaluate the full cipher or hash inside a fault-tolerant quantum circuit. NIST's post-quantum security categories are defined relative to the cost of attacking AES-128, AES-192 and AES-256 and SHA-2/SHA-3 collisions, which tells you those primitives remain the reference points rather than casualties.

The practical guidance is unglamorous: symmetric ciphers and hash functions at today's common sizes are not the urgent problem. Teams that want extra margin choose AES-256 and 256-bit or larger hash outputs, which is already common practice. SHA-256, which Solana uses widely (for example in Proof of History and when deriving PDAs), is not considered broken by known quantum algorithms.

What does not exist yet#

Running Shor's algorithm against a 255-bit elliptic curve needs a large, error-corrected quantum computer running a long computation without the encoded state collapsing. Published resource estimates vary by orders of magnitude depending on hardware assumptions and error-correction schemes, and they keep moving as both algorithms and engineering improve. Demonstrations to date have factored or solved toy instances far below cryptographic sizes.

Lattice does not publish a date for "Q-day", and you should be suspicious of anyone who does. What can be said with confidence is that standards bodies are already acting: NIST published its first post-quantum standards in August 2024 (FIPS 203, 204 and 205), and its draft transition report, NIST IR 8547, proposes deprecating today's quantum-vulnerable public-key algorithms for US federal use over the following decade. Those are planning signals about migration lead time, not predictions of when an attack will work.

Harvest now, decrypt later vs. forge later#

Quantum risk does not arrive evenly across all uses of cryptography. The difference between encryption and signatures is the single most useful idea in this primer.

Confidentiality is exposed today. If a session key is agreed with X25519, an adversary who records the handshake and the ciphertext can store both and, if a CRQC later exists, recover the session key and read the data. This is called harvest now, decrypt later. Anything that must stay secret for many years (medical data, private messages, long-lived business secrets, encrypted backups) is already at risk if it travels over purely classical key exchange. Chapter 03 covers the fix: hybrid key exchange with ML-KEM.

Authenticity is exposed when the attacker can act. A signature proves something at the moment it is verified. An attacker who records your Ed25519 signatures today gains nothing until they can forge new ones, and on a blockchain, past transactions are already final; forging an old signature does not rewrite history. The danger is forward-looking: once forgery is possible, every key whose public key is known can be impersonated. On Solana that is every keypair account, which is why signature migration needs to be planned well before it is needed even though there is no recording attack.

• Long-lived public keys are the main signature risk: wallet addresses, program upgrade authorities, multisig members, mint and freeze authorities, validator identity keys.
• Pre-signed transactions with long validity, such as those using durable nonces, extend the window in which a signature is useful.
• Ephemeral keys that are used once and discarded carry much less forward risk.

What replaces what#

NIST's three 2024 standards give a direct substitute for each broken role. ML-KEM (FIPS 203) replaces Diffie–Hellman style key agreement. ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) replace signatures. ML-KEM and ML-DSA are based on structured lattice problems (Module-LWE and Module-SIS) for which no efficient quantum algorithm is known; SLH-DSA relies only on the security of a hash function, which makes it the conservative choice at the cost of much larger signatures.

The replacements are larger than what they replace, sometimes by two orders of magnitude, and that is where the engineering pain lives. Chapter 02 puts numbers on it, and chapter 04 shows why those numbers collide with Solana's 1232-byte transaction limit. You can feel the difference directly in the Lab, which signs and verifies with Ed25519, ML-DSA and SLH-DSA in your browser.