Discrete Logarithms & Elliptic Curves
Why ECC falls too, and with fewer qubits.
Elliptic-curve keys are about twelve times shorter than RSA keys of the same classical strength, because the best classical attacks on a good curve are generic. Shor's other algorithm ignores that distinction: it computes discrete logarithms in any group where you can compute, and its cost scales with the key length. Shorter keys mean a smaller quantum computer.
What you’ll learn
- State the discrete logarithm problem, its cryptographic uses, and the classical attacks that set key sizes.
- Derive Shor's discrete-log algorithm as Fourier sampling on and recover from one sample.
- Explain what changes for elliptic curves (reversible point addition, unique representations) and why the logical-qubit count is lower than for RSA at equal security.
- Describe short-discrete-log variants (Ekerå–Håstad) and which public-key systems survive.
The discrete logarithm problem
Generic algorithms, which only multiply and compare group elements, need operations: Pollard's rho method achieves this, and Shoup (1997) proved it optimal in the generic-group model. In , index calculus and the number field sieve exploit the arithmetic of integers and run in subexponential time, so must be thousands of bits long. For well-chosen elliptic curves no attack substantially better than generic is known, so a 256-bit curve already gives about 128-bit security.
| Classical security | RSA modulus or finite-field | Elliptic-curve group order |
|---|---|---|
| 128 bits | 3072 bits | 256 bits |
| 192 bits | 7680 bits | 384 bits |
| 256 bits | 15360 bits | 512 bits |
Shor's discrete-log algorithm
Define by . Then iff , so hides the subgroup of order : a two-dimensional period-finding problem, solved by abelian Fourier sampling.
Two uniform registers and one evaluation of , i.e. two exponentiations in .
Measuring the third register gives some and leaves the coset of .
The sum over vanishes unless : the outcome is uniform on .
If , a single sample determines . For prime , the cryptographic case, this fails only when , with probability .
In the same group (, unknown) you measure . What is ?
Show the answer
B.
because . So , consistent with .
If is not a power of two, can be approximated efficiently (Kitaev 1995), or one uses registers of size with Shor's original, slightly more involved post-processing; if is unknown, order finding supplies it. Boneh and Lipton (1995) extended the method to "black-box" groups, in which elements have unique encodings and the group operation is efficiently computable, covering both and elliptic curves.
Elliptic curves: same algorithm, different arithmetic
On an elliptic curve over , the points form an abelian group under the chord-and-tangent law, with a large prime-order subgroup . The secret is with . Shor's circuit computes by double-and-add: the multiples and are classical constants, so the circuit is a sequence of about controlled additions of a fixed point to a quantum point.
Evaluate for a 256-bit curve such as P-256.
Show the answer
2330
, , plus 10: 2330 logical qubits, compared with for RSA-3072 with the circuits of Häner, Roetteler & Svore (2017).
| Target (about 128-bit classical security) | Key size | Logical qubits (2017 circuits) |
|---|---|---|
| RSA-3072 | 3072 | |
| ECC P-256 | 256 |
Short logarithms, tradeoffs and what survives
When the logarithm is known to be short, with much smaller than , Ekerå and Håstad (2017) showed how to size the exponent registers by rather than by , with a tradeoff parameter : fewer qubits and gates per run in exchange for about runs combined by lattice-based post-processing. RSA fits this mold. For and a random , because , so , an integer of about bits, is a short discrete logarithm; and then follow from and by solving a quadratic. The Gidney–Ekerå RSA estimates use this formulation.
Shor's algorithms break every public-key system whose security reduces to factoring or to discrete logarithms in an abelian group: RSA, finite-field and elliptic-curve Diffie–Hellman, DSA, ECDSA. They do not apply to schemes built on lattices, codes, hash functions or multivariate equations, for which no polynomial-time quantum attacks are known; NIST standardized lattice-based ML-KEM and ML-DSA and hash-based SLH-DSA in 2024 (FIPS 203–205). Isogeny-based schemes sit in between: CSIDH rests on an abelian group action, which Kuperberg-type algorithms attack in subexponential time, while SIDH/SIKE fell in 2022 to a purely classical attack (Castryck & Decru), a reminder that post-quantum schemes must also be classically secure.
Key takeaways
- Discrete logs: generic attacks need (Pollard rho, Shoup's lower bound), admits subexponential attacks, good curves only generic ones, so 256-bit ECC gives about 128-bit security.
- Shor's algorithm: hides ; Fourier sampling returns , and . It works in any black-box abelian group with unique encodings.
- Elliptic curves need controlled additions of fixed points, affine coordinates and reversible inversion: logical qubits for , versus about 6100 for RSA-3072.
- Short logarithms (Ekerå–Håstad) need registers sized by the logarithm's length; RSA factoring is a short discrete log of .
- Lattice, code, hash and multivariate schemes survive (NIST FIPS 203–205, 2024); isogeny group actions face subexponential attacks, and SIDH fell classically.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
The function with hides which subgroup of ?
- The trivial subgroup
Show the answer
C.
is unchanged by adding : shifts by . The level sets are exactly the cosets of .
Why does ECC-256 need fewer logical qubits to break than RSA-3072, although both give about 128-bit classical security?
- Shor's cost grows with key length, and ECC keys are short because only generic classical attacks are known for good curves
- Elliptic-curve groups have smooth order
- ECC uses a non-abelian group, which is easier for Fourier sampling
- Point addition is cheaper than modular multiplication
Show the answer
A. Shor's cost grows with key length, and ECC keys are short because only generic classical attacks are known for good curves
Roughly logical qubits with versus roughly with . Each ECC operation is costlier, but the problem is twelve times smaller.
Why do quantum elliptic-curve circuits use affine coordinates despite the cost of modular inversion?
- Because projective coordinates need more qubits per point
- Because inversion is cheap on a quantum computer
- Because Shor's algorithm only works over prime fields
- Because each point must have a unique encoding: with projective coordinates, equal points would differ across branches, would not be constant on cosets, and interference would be lost
Show the answer
D. Because each point must have a unique encoding: with projective coordinates, equal points would differ across branches, would not be constant on cosets, and interference would be lost
Classically, redundant representations are harmless. Quantumly, the register contents must depend only on the group element, otherwise the branches that should interfere carry different labels.
Which scheme is, as far as is known, not broken by Shor's algorithms?
- ECDSA
- ML-KEM (lattice-based)
- Finite-field Diffie–Hellman
- RSA-OAEP
Show the answer
B. ML-KEM (lattice-based)
ML-KEM relies on module lattice problems, for which no efficient quantum algorithm is known. The other three reduce to factoring or abelian discrete logarithms.
Further reading
- P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM J. Comput. 26, 1484 (1997); conference version in Proc. 35th IEEE FOCS (1994).
- J. Proos & C. Zalka, "Shor's discrete logarithm quantum algorithm for elliptic curves", Quantum Inf. Comput. 3, 317 (2003).
- M. Roetteler, M. Naehrig, K. M. Svore & K. Lauter, "Quantum resource estimates for computing elliptic curve discrete logarithms", ASIACRYPT 2017.
- M. Ekerå & J. Håstad, "Quantum algorithms for computing short discrete logarithms and factoring RSA integers", PQCrypto 2017.
- D. Boneh & R. J. Lipton, "Quantum cryptanalysis of hidden linear functions", CRYPTO '95.