[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