[curves] Choosing an extra-strength curve

[Samuel Neves]

On 05/06/2014 04:56 PM, Trevor Perrin wrote:
> Bernstein and Lange don't seem to think that's important [1]:
> "Special primes help index calculus, but the point of ECC has always
> been to avoid index calculus. All of the SafeCurves requirements can
> be met by special primes."
>
> Mike agrees that random primes might protect against future
> cryptanalysis, but points out they bring a substantial cost [2]: "a
> random field would be at least twice as slow".
>
> If that's true, I think you'd expect a random-prime curve to be about
> the same speed as a curve 1.3x the size (2 ^ 1/2.6).  So a 384-bit
> random-prime curve would be about as slow as a fast-prime 500-bit
> curve, but would have a nominal security level of 192 bits instead of
> 250.
>
> So I guess this is a tradeoff between different strategies for adding
> margin against cryptanalysis?

I do not think random primes are worth it. Looking at the past, the SNFS is not *that* great of an improvement. Of
course it matters in practice, and special >1024-bit numbers are factored whereas the best general result is RSA-768.
However, it (asymptotically) 'only' shaves around 20 bits of security off of RSA-2048 (~112-bit security), and 50 bits
off of RSA-15360 (~256-bit security).

Suppose there is indeed some similar speedup for prime-field elliptic curves, along with some index-calculus type
attack. Firstly, if the attack is subexponential, current sizes are dead regardless of the parameters. Secondly, as
Trevor mentions, how many extra bits in the prime field could we buy with the 2x slowdown of random primes? 64? 128? It
seems to me that a slightly bigger special prime would be a better tradeoff than a random one, all things considered.

There are also other kinds of structure to consider beyond the primes (which seem to presently be very low-risk). One
example of structure could be small even cofactors, which are known to speed up index calculus over extension fields in
some cases [1]. None of this affects elliptic curves over prime fields, but it still seems more realistic of a threat
than special primes.

[1] http://hal.archives-ouvertes.fr/hal-00700555