Computational cryptography › Public-key encryption and key exchange › Classical number theory › Elliptic-curve discrete log
Hardness assumption

ECDLP

In plain words

On an elliptic curve, jumping x steps from a starting point is easy, but working out x from where you landed is extremely hard.

The idea: Points on an elliptic curve can be "added" with a geometric rule, and adding a point to itself x times is fast even for astronomically large x, by repeated doubling. Going back, from the start point and the landing point to the number of steps x, is the hard direction. Your private key is x, your public key is the landing point, and a signature proves you know x without showing it. Curves give the same security as the finite-field version with far smaller numbers, which is why they took over.

Why it matters: Behind most modern signatures and key exchanges, from your browser to Bitcoin.

Adding points on a curve
PQthird pointP + QflipGall 78 points of y² = x³ + 7, counting mod 67
6·G = (11, 20)
The curve: the addition rule. Draw the line through P and Q. It meets the curve at one more point. Flip it over the horizontal axis to get P + Q. Adding a point to itself works the same way, with the tangent line. The dots: the same rule with whole numbers, counting modulo 67. Bitcoin's and Ethereum's curve, secp256k1, uses this same equation, but modulo a 78-digit prime instead of 67. Press play: each jump adds G once more, and the landing spots scatter with no visible pattern, so seeing where you landed tells you nothing about how many jumps it took. Here you could check all 78 possibilities. On the real curve there are about 1077.

The details

On the map: P-256, Curve25519, ... best attack: Pollard rho

Given points P and Q = xP on an elliptic curve, find x. For well-chosen curves no faster-than-generic classical attack is known: the best is Pollard's rho[1], about the square root of the group size, so a 256-bit curve gives about 128-bit security.

Common curves: P-256 (NIST), Curve25519 and secp256k1 (Bitcoin, Ethereum)[2, 3]. Shor's algorithm breaks it, and needs fewer qubits for elliptic curves than for RSA[4].

ECDLP alone gives signatures (ECDSA, Schnorr). Key exchange needs the stronger Diffie-Hellman assumptions, which is why this node has no KE tag.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (23 boxes)

References

  1. J. M. Pollard. Monte Carlo Methods for Index Computation (mod p). Mathematics of Computation, 1978. doi:10.2307/2006496
  2. Daniel J. Bernstein. Curve25519: New Diffie-Hellman Speed Records. Public Key Cryptography - PKC 2006. doi:10.1007/11745853_14
  3. Standards for Efficient Cryptography Group. SEC 2: Recommended Elliptic Curve Domain Parameters. Version 2.0, 2010. secg.org/sec2-v2.pdf
  4. Martin Roetteler, Michael Naehrig, Krysta M. Svore and Kristin Lauter. Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. Advances in Cryptology – ASIACRYPT 2017. doi:10.1007/978-3-319-70697-9_9