[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/



More information about the cryptography mailing list