The rho method
The rho method breaks ECDLP using, on average, approximately 0.886 sqrt(ℓ) additions. The following table shows 0.886 sqrt(ℓ) for various curves:
Can rho finish sooner?
Yes, but its success probability after m additions is only about m^2/ℓ (gradually degrading as m increases). Recommended practice is to choose ℓ so that m^2/ℓ is negligible for any feasible value of m.
For example, if ℓ is around 2^200, then the success probability is around 1/2^20 after 2^90 additions. Performing 2^90 additions in a year with state-of-the-art chip technology (as of 2013) would require hundreds of gigawatts of power. SafeCurves requires ℓ to be at least 2^200.
Does SafeCurves recommend against larger values of ℓ?
No. There are several reasons to use larger ℓ: chip technology can be expected to advance; 1/2^20 is not an acceptable risk level for some users; very few ECC applications will notice the cost of increasing ℓ to, e.g., 2^250.
Does rho become cheaper against multiple targets?
Yes. There is a square-root effect for multiple targets: breaking 1000000 keys with the rho method costs only about 1000 times as much as breaking a single key, not 1000000 times as much. See 2001 Kuhn–Struik, 2004 Hitchcock–Montague–Carter–Dawson, 2011 Lee–Cheon–Hong, and 2012 Bernstein–Lange.
ANSI X9.62 stated in 1997 that "the computation of a single elliptic curve discrete logarithm has the effect of revealing a single user’s private key. The same effort must be repeated in order to determine another user’s private key." The second sentence is incorrect: the effort is reduced for each subsequent key.
For comparison, with secret-key ciphers there is a much worse effect for multiple targets. Breaking a single AES key costs about 2^128 computations; breaking 1000000 AES keys costs, in total, about 2^128 computations.
Does rho become faster against the first of multiple targets?
No. The probability of finding any keys within m additions is still only about m^2/ℓ. The first key found will still cost approximately 0.886 sqrt(ℓ) additions on average.
For comparison, if there are 1000000 AES keys to break, then some key will be found after only 2^128/1000000 computations.
What is this 0.886? What exactly are the additions?
The 0.886 is actually sqrt(pi/4). The additions are "batched affine" short-Weierstrass elliptic-curve additions, each consisting of 5 multiplications mod p, 1 squaring mod p, and an asymptotically negligible amount of extra work. (Short Weierstrass curves are the fastest known curve shapes for batched affine additions. This does not mean that other curves are harder to attack: the attacker converts other curves to short Weierstrass form.) The algorithm can be efficiently parallelized and vectorized.
How stable is the security story for rho?
1971 Shanks introduced square-root DLP attacks. The number of additions used by 1971 Shanks is within a factor of 2 of the number of additions used by state-of-the-art ECDLP attacks. There are three main themes of research since 1971:
X9.62 stated sqrt(pi/2) sqrt(ℓ) in 1997. Brainpool in 2005 repeated sqrt(pi/2) sqrt(ℓ), failing to take the negation speedup into account.
Version: This is version 2013.10.13 of the rho.html web page.