Computational cryptography › Live on mainnet today › Plain curves
Hardness assumption

ECDLP

In plain words

Your public key is your private key "multiplied" by a fixed point on a curve. Going back from the public key to the private key is believed to be infeasible.

The idea: Your private key is a random number x, and your public key is the point you reach by "adding" a fixed curve point G to itself x times, which is fast thanks to repeated doubling. Going back from the public key to x is the hard direction: the best known method needs about 2^128 steps. A signature proves you know x without revealing it, which is all an account needs.

Why it matters: This single puzzle protects every Ethereum account's signatures.

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. Ethereum's 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: best attack: Pollard rho (~128-bit)

Given a public key Q = x·G on an elliptic curve, find the private key x. For secp256k1 the best classical attack, Pollard's rho, needs about 2^128 operations[1, 2], far beyond any computer.

It is the single assumption behind every Ethereum account's signatures. Shor's algorithm breaks it on a large quantum computer[3]. On its own it gives signatures but not key exchange, which needs the stronger Diffie-Hellman assumption.

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 (7 boxes)

References

  1. J. M. Pollard. Monte Carlo Methods for Index Computation (mod p). Mathematics of Computation, 1978. doi:10.2307/2006496
  2. Standards for Efficient Cryptography Group. SEC 2: Recommended Elliptic Curve Domain Parameters. Version 2.0, 2010. secg.org/sec2-v2.pdf
  3. Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 1997. doi:10.1137/S0097539795293172