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