Pollard's rho and the parallel collision search

Rho is the attack a 256-bit curve is sized against. It needs no structure at all — only the ability to add points and compare them — which is exactly why it sets the floor, and why beating it requires finding structure the group was chosen not to have.

Problem
Discrete logarithm in a cyclic group of prime order n
Expected cost
√(πn/2) ≈ 1.25√n group operations
Memory
Negligible per worker; distinguished-point storage when parallelised
Largest published solves
114-bit prime-field curve (2017, a curve with extra automorphisms); sect113r2, a 113-bit binary curve (2016)
Relevance to 256-bit curves
None. 2128 operations is not reachable.

The problem instance

Let G = ⟨P⟩ be a cyclic group of prime order n, written additively because the target is usually an elliptic curve. The attacker is given P and Q = kP, and must recover k ∈ ℤ/nℤ. The attacker can add group elements and test two elements for equality. Nothing else is assumed — no factorisation of the group order beyond primality, no embedding, no special curve shape.

That restriction is the point. Shoup proved that any algorithm confined to these operations needs Ω(√p) of them, where p is the largest prime factor of n. So an attack that beats rho on a specific curve is necessarily an attack that used something about that curve. Finding out whether such a thing exists is the whole business of elliptic-curve cryptanalysis.

The mechanism

Define a pseudorandom iteration on group elements that keeps track of how each element was built. Every point reached is written Xi = aiP + biQ, and the step function Xi+1 = f(Xi) updates ai and bi alongside the point — typically by partitioning the group into r buckets by a hash of the point and adding a fixed precomputed multiple per bucket.

The walk is a function on a finite set, so it must eventually repeat, tracing the shape that gives the method its name: a tail leading into a cycle. A repeat means

aiP + biQ = ajP + bjQ  ⇒  k ≡ (ai − aj)(bj − bi)−1 (mod n) The collision solves the instance, provided bi ≠ bj

By the birthday bound, a walk behaving like a random map collides after about √(πn/2) ≈ 1.25√n steps. Floyd's or Brent's cycle-finding turns that into constant memory for a single walk; in practice nobody runs a single walk.

Making it parallel

The version that actually gets run is van Oorschot and Wiener's parallel collision search. Declare a point distinguished if it satisfies a cheap, rare predicate — say, its x-coordinate has 30 leading zero bits. Each of m independent workers walks from its own random start, reports only distinguished points with their (a, b) coefficients to a central server, and restarts. Two workers that ever step onto the same point follow the same trail from there and report the same distinguished point, which the server detects.

  1. Workers exchange no messages with each other and need no shared state.
  2. Wall-clock time falls to √(πn/2)/m, a genuinely linear speedup in the number of workers.
  3. Storage is bounded by the distinguished-point rate, which is a tunable parameter, not by √n.
  4. Interrupted work is not lost: the reported points remain valid.

This is why rho is the right benchmark rather than baby-step giant-step: BSGS also runs in √n time but needs √n memory, and memory does not parallelise for free. Rho has no such handicap, so the attacker's cost is honestly a time–hardware product with no hidden ceiling.

The constant factors that matter

Against a real curve the exponent is fixed and the fight is entirely over constants. Three of them are worth knowing.

  • The negation map. On an elliptic curve, −(x, y) = (x, −y), so a walk defined on x-coordinates alone searches a space of size n/2 and gains a factor of √2. Realising the gain requires handling fruitless cycles, where the walk oscillates between a point and its negative.
  • Efficient endomorphisms. A Koblitz curve over F2m has the Frobenius endomorphism acting freely on classes of size m, giving a further √m speedup — a real, quantifiable reason to price Koblitz curves differently from random binary curves.
  • The cost of one step. Inversion-free coordinates, batched inversions across many simultaneous walks, and field arithmetic tuned to the hardware decide the per-step cost, and that is what separates a feasible computation from an infeasible one at a fixed exponent.

What record computations have cost

Published ECDLP records are the honest calibration data. A 112-bit prime-field instance, the standard curve secp112r1, was solved in 2009 by Bos, Kaihara, Kleinjung, Lenstra and Montgomery on a cluster of PlayStation 3 consoles, at an expected cost of about 65 years of a single console. The prime-field record has since moved to 114 bits: Kusaka and collaborators solved a Barreto–Naehrig curve in 2017 with about 2,000 CPU cores over six months, using the curve's extra automorphisms to shorten the walk. On binary curves, Wenger and Wolfger solved a 113-bit Koblitz curve on an FPGA cluster in 2014 and the standard curve sect113r1 in 2015, and Bernstein and collaborators solved sect113r2 in 2016. The 131-bit Certicom challenge ECC2K-130, analysed by Bailey and collaborators in 2009 at an expected 260.9 iterations, is still unsolved.

The boundary

Rho is optimal among generic algorithms, so anything that beats it is a statement about the specific group. The attacks that do beat it all work by leaving the generic model:

  • A composite group order with only small prime factors — see Pohlig–Hellman, which is why cofactors and subgroup orders are checked.
  • A small embedding degree, where the MOV/Frey–Rück pairing transfers the problem into a finite field with subexponential index calculus.
  • Trace one (anomalous curves), where the Smart–Satoh–Araki lift solves the instance in linear time.
  • Definition over an extension field, where the point decomposition of summation polynomials or Weil descent becomes available.
  • An implementation that leaks — where the hidden number problem makes the group order irrelevant.

A standard prime-field curve such as P-256 or secp256k1 is chosen to have none of the first four properties. Which leaves the fifth, and that is where deployed systems actually break.

Primary sources

  1. J. M. Pollard, "Monte Carlo methods for index computation (mod p)", Mathematics of Computation 32 (1978)
  2. P. C. van Oorschot and M. J. Wiener, "Parallel collision search with cryptanalytic applications", Journal of Cryptology 12 (1999)
  3. V. Shoup, "Lower bounds for discrete logarithms and related problems", EUROCRYPT 1997
  4. R. Gallant, R. Lambert and S. Vanstone, "Improving the parallelized Pollard lambda search on anomalous binary curves", Mathematics of Computation 69 (2000)
  5. J. W. Bos, M. E. Kaihara, T. Kleinjung, A. K. Lenstra and P. L. Montgomery, "Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction", IJACT 2 (2012)
  6. E. Wenger and P. Wolfger, "Solving the discrete logarithm of a 113-bit Koblitz curve with an FPGA cluster", SAC 2014
  7. D. J. Bernstein, T. Lange and P. Schwabe, "On the correct use of the negation map in the Pollard rho method", PKC 2011
  8. T. Kusaka, S. Joichi, K. Ikuta, M. A.-A. Khandaker, Y. Nogami, S. Uehara, N. Yamai and S. Duquesne, "Solving 114-bit ECDLP for a Barreto–Naehrig curve", ICISC 2017
  9. E. Wenger and P. Wolfger, "Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs", Journal of Cryptographic Engineering 6 (2016)
  10. D. J. Bernstein, S. Engels, T. Lange, R. Niederhagen, C. Paar, P. Schwabe and R. Zimmermann, "Faster elliptic-curve discrete logarithms on FPGAs" (2016)
  11. D. V. Bailey et al., "Breaking ECC2K-130" (2009)