[cryptography] Small speedup of ECDLP?
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|)
Standard birthday attacks on the (EC)DLP use r-adding walks  (see
also  and ), 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. .
More information about the cryptography