SafeCurves:
choosing safe curves for elliptic-curve cryptography

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:

Curve	Cost for rho above 2^100?	Cost for rho
Anomalous	True✔	2^101.6
M-221	True✔	2^108.8
E-222	True✔	2^109.8
NIST P-224	True✔	2^111.8
Curve1174	True✔	2^124.3
Curve25519	True✔	2^125.8
BN(2,254)	True✔	2^126.4
brainpoolP256t1	True✔	2^127.5
ANSSI FRP256v1	True✔	2^127.8
NIST P-256	True✔	2^127.8
secp256k1	True✔	2^127.8
E-382	True✔	2^189.8
M-383	True✔	2^189.8
Curve383187	True✔	2^189.8
brainpoolP384t1	True✔	2^191.4
NIST P-384	True✔	2^191.8
Curve41417	True✔	2^205.3
Ed448-Goldilocks	True✔	2^222.8
M-511	True✔	2^253.8
E-521	True✔	2^259.3

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:

• Optimizing the number of additions. The largest change was a sqrt(2) "negation" speedup, replacing sqrt(pi/2) ≈ 1.253 with sqrt(pi/4) ≈ 0.886. See 1998 Wiener–Zuccherato, 1998 Escott, and 1999 Duursma–Gaudry–Morain; for further analysis see 2010 Bos–Kleinjung–Lenstra and 2011 Bernstein–Lange–Schwabe.
• Optimizing the cost of the additions. See, for example, the ECC2K-130 project.
• Showing that there are no bottlenecks other than the arithmetic required for the additions: in particular, no serious memory use, no serialization, no serious communication, and no serious branching. 1978 Pollard introduced the rho method, showing that square-root DLP attacks do not need much memory. 1999 van Oorschot–Wiener (drafts published as early as 1994) showed that a variant of the rho method is parallelizable, with negligible communication costs. 2011 Bernstein–Lange–Schwabe showed that a negating variant of the rho method is vectorizable.

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.