[curves] Choosing an extra-strength curve

[Johannes Merkle]

> 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.

Yes, the specific speed-up provided by the SNFS over the GNFS might compensate the increase in bit length suggested by
Trevor. But I referred to the SNFS just to illustrate that special primes can in principle help to improve or to
leverage attacks, i.e. it was a qualitative comparison, not a quantitative. Nobody knows if and how much a certain
structure might help attacks, and extrapolations from finite field DL or integer factorization to ECDL are hardly possible.

That said, let me make clear that I do not think that future attacks on special prime curves are at all likely to occur.
Still, they are conceivable, at least for me.

> 
> 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.
> 

I agree that this aspect should also be considered. However, I don't dare to assess which threat is more realistic.

We should try to avoid any unnecessary structure for a conservative set of curves.


-- 
Johannes