# [cryptography] Small speedup of ECDLP?

Paul Crowley paul at ciphergoth.org
Sun May 29 13:12:26 EDT 2011

```I doubt this is original, but I'd be interested to know who thought of
it first.  Given a group G with generator g and a point y in the group,
suppose you're using the standard parallelized Pollard rho attack to
find x such that ax = y.  If the time t_a it takes you to add g to an
arbitrary point on an elliptic curve p is much less than the time t_p it
takes you to find ag + by for arbitrary a, b then I think I see a way to
speed up Pollard-Rho by around sqrt(t_p/4t_a).

A standard birthday attack requires that sqrt(2 ln(2) N) to find a
collision in a random-ish function with a range of size N, so the
standard Pollard rho attack generates about sqrt(2 ln(2) |G|) such
points for a 50% probability of success, taking time sqrt(2 ln(2) |G|) t_p.

To get the speedup, we need a set D of easily identified "distinguished
points" in G, perhaps by examining least significant bits, such that |D|
/ |G| ≅ t_a / t_p.  Then for each a, b, we find the least non-negative c
such that (a + c)g + by ∈ D; we do this just by starting with ag + by
and adding g repeatedly until we end up with a point in D.  Assuming
this behaves like a Poisson distribution, this will take on average
around |G|/|D| steps.  We then look for collisions in D.

Each point now takes around t_p + (|G|/|D|)t_a ≅ 2t_p to generate, but
because we now need a collision in D, we now only need to generate
sqrt(2 ln(2) |D|) such points.  Since we're generating t_a/t_p fewer
points but each takes twice as long, we get our speedup of sqrt(t_p/4t_a).

I think it's very unlikely that the people who do this sort of thing
have missed this trick, but I'd be interested to know if it's already
been written up - can anyone point me to any references? Thanks!
--
__
\/ o\ Paul Crowley, paul at ciphergoth.org
/\__/ http://www.ciphergoth.org/

```