[curves] Choosing an extra-strength curve

[Johannes Merkle]

Trevor Perrin wrote on 06.05.2014 01:42:
> Pains me to link there, but Mike wrote a great mail to CFRG:
> 
> http://www.ietf.org/mail-archive/web/cfrg/current/msg04495.html
> 
> The gist is that trying to closely match AES's 192 or 256-bit security
> levels for extra-strength curves isn't important.  With an
> extra-strength curve we're trying to buy extra security margin against
> cryptanalytic breakthroughs, and the breakthroughs that might affect
> AES and elliptic curves - and the costs of security margin - are very
> different.
> 
> I'd add a few arguments:
> 
>  * The curve size determines the availability of primes for efficient
> reduction, and the options for representing field elements efficiently
> as "limbs" [1].  So it makes sense to choose curve sizes based on
> efficiency instead of arbitrary criteria.
> 

If our concern is potential cryptanalytic breakthroughs, shouldn't we widen our focus from key lengths (which might not
make much difference anyway in case of a serious improvement) to design/selection criteria? So instead of choosing
curves with some extra bits as security margin, we could consider more conservative selection criteria.

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

I know that this has a downside on performance but we are talking about a backup.

-- 
Johannes