[curves] Choosing an extra-strength curve

[Trevor Perrin]

On Tue, May 6, 2014 at 5:28 AM, Johannes Merkle
<johannes.merkle at secunet.com> wrote:
>
> To be more specific: If a new attack emerges on curves defined over Pseudo-Mersenne (or other special) primes, having 32
> bits of extra security against Pollard's Rho might not buy us much. Admittedly, there is no indication of such attacks,
> but since we don't have any clue about what attacks might evolve, the most conservative choice is to avoid simplified
> structures, in particular, if these structures had already been exploited by attacks in other circumstances (yes, I'm
> talking about the specialized NFS).

Hi Johannes,

I'm not qualified to assess this, so I'll look to people like
Bernstein, Lange, Hamburg, etc.

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?

Do you think 2x slower is accurate?  (Or do you have performance
numbers on Brainpool or similar curves I could add to the spreadsheet
[3])?

Trevor

[1] http://safecurves.cr.yp.to/field.html
[2] http://www.ietf.org/mail-archive/web/cfrg/current/msg03961.html
[3] https://docs.google.com/a/trevp.net/spreadsheet/ccc?key=0Aiexaz_YjIpddFJuWlNZaDBvVTRFSjVYZDdjakxoRkE&usp=sharing#gid=0