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, [email protected]
/\__/ http://www.ciphergoth.org/
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
