[cryptography] Small speedup of ECDLP?

Samuel Neves sneves at dei.uc.pt
Sun May 29 14:06:40 EDT 2011


On 29-05-2011 18:12, Paul Crowley wrote:
> 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.

Standard birthday attacks on the (EC)DLP use r-adding walks [1] (see
also [2] and [3]), which do not require computing ax + by explicitly,
thus requiring only one group addition per iteration (i.e., t_a).

What you describe looks like a 1-adding walk, although I must have
missed something there. r-adding walks for very small r are not very
random, cf. [2].

Best regards,
Samuel Neves

[1] http://www.springerlink.com/content/y280563355n23466/
[2]
http://www.ams.org/mcom/2001-70-234/S0025-5718-00-01213-8/S0025-5718-00-01213-8.pdf
[3] http://cr.yp.to/elliptic/negation-20110102.pdf



More information about the cryptography mailing list