The elliptic-curve discrete logarithm problem
Given P and Q = kP, find k. For a well-chosen curve nobody knows a way to do this that is meaningfully faster than a generic collision search, and that one fact sets the size of every elliptic-curve key in use.
- Problem
- Given P of prime order n and a point Q in the group it generates, find k with Q = kP
- Best known attack
- Parallel Pollard rho: about √(πn/4) group operations, using the symmetry P ↔ −P
- Largest public solves
- 114-bit prime-field curve (2017); 113-bit binary curves (2014–2016)
- Quantum
- Polynomial time with Shor's algorithm; about 2,330 logical qubits estimated for P-256
The problem
Fix a curve E over a finite field and a point P on it whose order n is a large prime. The elliptic-curve discrete logarithm problem, the ECDLP, is: given a point Q in the group generated by P, find the integer k, modulo n, such that Q = kP.
On the 103-point curve from the primer, with P = (0, 14) and Q = (24, 30), the answer is k = 77, and a computer finds it instantly by listing multiples of P. Every elliptic-curve key pair is an instance of this problem at a size where listing is impossible: the secret key is k, the public key is kP, and the security of ECDH, ECDSA and EdDSA reduces to, or at least rests on, nobody being able to recover k.
The square-root barrier
A generic algorithm is one that uses the group only through its operations: it can add points and test them for equality, and nothing else. Shoup and, before him, Nechaev proved that any generic algorithm needs on the order of √n operations to solve the discrete logarithm problem in a group of prime order n. Baby-step giant-step meets that bound using √n memory; Pollard's rho meets it using almost none, and parallelises perfectly.
Every curve also has the symmetry P ↔ −P, which lets rho work on pairs {P, −P} and saves a factor of √2. The expected cost for a curve whose group has prime order n is then about √(πn/4) group operations. For standard curves that works out as follows.
| Curve | Field (bits) | Cofactor | Subgroup order n (bits) | Expected rho work |
|---|---|---|---|---|
| P-256 | 256 | 1 | 256 | 2127.8 |
| secp256k1 | 256 | 1 | 256 | 2127.0 |
| Curve25519 | 255 | 8 | 253 | 2125.8 |
| P-384 | 384 | 1 | 384 | 2191.8 |
| Curve448 | 448 | 4 | 446 | 2222.8 |
These are the numbers behind the phrase "128-bit security": expected costs, in group operations, of recovering one key. Many keys on the same curve can be attacked for less than that each, because walks for different keys can share work: Kuhn and Struik analysed the rho method for multiple targets, and Bernstein and Lange showed how a precomputed table speeds up every later logarithm in the same group. At these sizes neither changes the conclusion, since the shared work is itself far beyond reach.
Curves to avoid, and how to check
Beating √n requires using something about the curve. Four properties are known to give attacks, and each can be checked from public data before a curve is used. The last column applies the checks to the 103-point curve from the primer.
| Property | What it enables | The check | Toy curve |
|---|---|---|---|
| The group order has no large prime factor | Pohlig–Hellman: the problem splits into one per prime factor | The order is prime, or a large prime times a small cofactor | 103 is prime |
| Small embedding degree | The MOV and Frey–Rück attacks: a pairing moves the problem into Fpk, where index calculus applies | The smallest k with n dividing pk − 1 is large | k = 51, a 337-bit field |
| Trace one: exactly p points | Smart, Satoh–Araki and Semaev: a p-adic lift solves the problem in polynomial time | #E ≠ p | trace -5 |
| Defined over an extension field | Weil descent and summation polynomials | A prime field, or a prime extension degree that passes the GHS test | a prime field |
The embedding-degree row shows why it is the size of the target that matters, not the existence of the map. The pairing on the toy curve does move its discrete logarithms into a finite field, but into a field of about 2337 elements, where they are much harder than in the 103-element group they came from. For a random curve the embedding degree is about as large as n itself. Pairing-based cryptography deliberately uses curves with small embedding degree, and sizes them so that the field side is hard too.
What real computations cost
The largest discrete logarithms computed in public on elliptic curves are far from cryptographic sizes. The prime-field record is 114 bits, set in 2017 by Kusaka and collaborators on a Barreto–Naehrig curve, with about 2,000 CPU cores over six months. Before that, Bos, Kaihara, Kleinjung, Lenstra and Montgomery solved the 112-bit standard curve secp112r1 in 2009 on a cluster of PlayStation 3 consoles. On binary curves, the 113-bit standard curves sect113r1 and sect113r2 were solved on FPGA clusters in 2015 and 2016.
The next public target is Certicom's ECC2K-130, a Koblitz curve over F2131 with a subgroup of about 2129 points, whose expected cost Bailey and collaborators put at 260.9 iterations. It has been open since 1997, and we are running a distributed attack on it. The distance from there to a 256-bit curve is a factor of about 267 in work.
Beyond generic attacks
For the multiplicative group of a finite field, index calculus gives subexponential attacks, and whether anything like it works on elliptic curves has been studied for decades. Over extension fields it does: Gaudry and Diem, building on Semaev's summation polynomials, gave algorithms that beat rho for curves over Fqn. Over prime fields nobody has found a factor base that yields relations cheaply enough, and no published attack on a prime-field curve improves on generic methods.
Index calculus, end to end runs both the classical algorithm and Gaudry's elliptic version on small examples, and the explainer on three settings compares prime fields, characteristic 2 and Koblitz curves.
Quantum computers
Shor's algorithm solves discrete logarithm problems in polynomial time on a large fault-tolerant quantum computer, and elliptic curves are no exception. Roetteler, Naehrig, Svore and Lauter estimated that a curve over an n-bit prime field needs at most 9n + 2⌈log2 n⌉ + 10 logical qubits: 2,330 for P-256, with about 1.26 × 1011 Toffoli gates. The same paper puts factoring a 3072-bit RSA modulus at 6,146 logical qubits, so the elliptic-curve key falls to a smaller machine than an RSA key of similar classical strength.
No quantum computer of that size exists. The concern is that data encrypted today with elliptic-curve key exchange can be recorded now and decrypted once one does, which is why key exchange is moving first: see ML-KEM, and for signatures ML-DSA.
Primary sources
- V. Shoup, "Lower bounds for discrete logarithms and related problems", EUROCRYPT 1997
- F. Kuhn and R. Struik, "Random walks revisited: extensions of Pollard's rho algorithm for computing multiple discrete logarithms", SAC 2001
- D. J. Bernstein and T. Lange, "Computing small discrete logarithms faster", INDOCRYPT 2012
- A. Menezes, T. Okamoto and S. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field", IEEE Trans. Inf. Theory 39 (1993)
- N. P. Smart, "The discrete logarithm problem on elliptic curves of trace one", Journal of Cryptology 12 (1999)
- S. D. Galbraith and P. Gaudry, "Recent progress on the elliptic curve discrete logarithm problem", Designs, Codes and Cryptography 78 (2016)
- T. Kusaka et al., "Solving 114-bit ECDLP for a Barreto–Naehrig curve", ICISC 2017
- D. V. Bailey et al., "Breaking ECC2K-130" (2009)
- M. Roetteler, M. Naehrig, K. M. Svore and K. Lauter, "Quantum resource estimates for computing elliptic curve discrete logarithms", ASIACRYPT 2017
- D. J. Bernstein and T. Lange, "SafeCurves: choosing safe curves for elliptic-curve cryptography"