Quantum computers and post-quantum cryptography
The paper will be linked here when it is posted to IACR ePrint.
A large enough quantum computer would break every elliptic-curve and RSA key in use. Nobody can say when one will exist, but data encrypted today can be recorded and decrypted later, and replacing the cryptography in deployed systems takes years. So the deadline that matters is set by the migration, not by the machine.
- Breaks
- RSA, finite-field Diffie–Hellman, and every elliptic-curve scheme (ECDH, ECDSA, EdDSA, Schnorr), with Shor's algorithm
- Weakens
- Symmetric ciphers and hashes, at most by a square root with Grover's algorithm; doubling the key length restores the margin
- Resources needed for P-256
- About 2,330 logical qubits for the discrete logarithm on P-256 (Roetteler et al., 2017)
- Replacements
- ML-KEM (FIPS 203), ML-DSA (FIPS 204) and SLH-DSA (FIPS 205), published by NIST in August 2024
What a quantum computer changes
Public-key cryptography rests on problems that are easy to set and hard to undo: multiplying two primes but not factoring the product, or computing Q = kP on an elliptic curve but not recovering k from Q. For a classical computer, the best known attack on a well-chosen 256-bit curve is a collision search costing about 2128 group operations, which is far out of reach.
In 1994 Peter Shor showed that a quantum computer could solve both factoring and discrete logarithms in polynomial time. The algorithm finds the period of a function, and both problems reduce to period finding. On an elliptic curve the speed-up is total: the work goes from exponential in the key size to a small polynomial. No choice of curve or key length avoids it, because the attack uses only the group structure that every elliptic-curve scheme needs in order to work.
What it does not break
Symmetric ciphers such as AES and hash functions such as SHA-256 have no hidden period to find. The best known quantum attack on them is Grover's search, which at most square-roots the cost of a brute-force key search, and it parallelises badly: splitting the search across many machines reduces the speed-up. Using 256-bit keys keeps a large margin, so symmetric cryptography needs larger parameters rather than replacement.
Nor does a quantum computer break every public-key system. Schemes built on other problems, such as lattices, hash functions, and isogenies between elliptic curves, have no known efficient quantum attack. These are what post-quantum cryptography means: cryptography that runs on ordinary computers and is designed to resist attackers who have a quantum one.
Why it is a problem now
An attacker does not need a quantum computer today to benefit from one later. Encrypted traffic can be recorded now and stored until it can be decrypted. Anything sent today under an elliptic-curve key exchange that still needs to be secret when a large quantum computer exists is already exposed.
Michele Mosca put the arithmetic simply. Let x be how long the data must stay secret, y how long it takes to migrate the systems that protect it, and z how long until a quantum computer can break the current keys. If x + y > z, the data will be readable while it still matters, and nothing done after the fact can change that.
Nobody can date z, and published estimates of what Shor's algorithm needs keep falling. In 2019 Gidney and Ekerå estimated that factoring a 2048-bit RSA modulus would take about 20 million noisy physical qubits running for eight hours; in 2025 Gidney revised that to under a million, running for under a week. y, on the other hand, is known to be long: replacing the cryptography in protocols, hardware, certificates and long-lived devices has historically taken a decade or more. NIST's transition plan proposes deprecating elliptic-curve and RSA keys at the 112-bit security level after 2030 and disallowing all of them after 2035.
Key exchange is the urgent part, because recorded ciphertext can be attacked later. A signature only has to resist forgery for as long as it is relied on, so signatures can move second, except where they protect something that lasts, such as firmware or a root certificate.
The replacements
In August 2024 NIST published its first three post-quantum standards: ML-KEM for key establishment and ML-DSA for signatures, both built on module lattices, and SLH-DSA, a signature that relies only on the security of a hash function. Deployments are adopting them first as hybrids, alongside X25519 or ECDSA, so that a connection stays secure as long as either half holds.
The new schemes are larger. An ML-KEM-768 public key is 1,184 bytes against 32 for X25519, and an ML-DSA signature is a few kilobytes against 64 bytes for Ed25519. Their security levels are estimates of the cost of the best known attacks, made by the same method as the estimates for elliptic curves, and they will need re-examining in the same way. The catalogue of schemes lists what each one rests on and what it costs.
Where isogenies fit
Isogeny-based cryptography is a post-quantum family, not one of the systems that quantum computers break. It works with maps between elliptic curves rather than with points on one curve, and recovering a secret isogeny is not a period-finding problem, so Shor's algorithm does not apply. Its appeal is size: SQIsign has the smallest keys and signatures of any post-quantum signature candidate.
The family also shows why estimates have to be checked. SIDH, an isogeny-based key exchange whose encapsulation form SIKE was an alternate candidate in the fourth round of NIST's process, was broken in 2022 by Castryck and Decru with a classical attack that recovered a level-1 key in about an hour on a single core; the torsion-point attacks page explains how. CSIDH resists that attack but has a commutative structure that gives quantum computers a subexponential attack through Kuperberg's algorithm, and how large its parameters must be is still disputed. SQIsign is affected by neither, though a classical attack published in 2026 forced its parameters up.
Primary sources
- P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM Journal on Computing 26 (1997)
- M. Roetteler, M. Naehrig, K. M. Svore and K. Lauter, "Quantum resource estimates for computing elliptic curve discrete logarithms", ASIACRYPT 2017
- C. Gidney and M. Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 5 (2021)
- C. Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits" (2025)
- M. Mosca, "Cybersecurity in an era with quantum computers: will we be ready?", IEEE Security & Privacy 16 (2018)
- NIST, FIPS 203, 204 and 205: ML-KEM, ML-DSA and SLH-DSA (August 2024)
- NIST IR 8547 (initial public draft), "Transition to post-quantum cryptography standards" (November 2024)
- W. Castryck and T. Decru, "An efficient key recovery attack on SIDH", EUROCRYPT 2023
Related
- The elliptic-curve discrete logarithm problem
- Isogenies and the supersingular graph
- SQIsign
- Kuperberg's algorithm and CSIDH
The paper will be linked here when it is posted to IACR ePrint.