[curves] Choosing an extra-strength curve

[Trevor Perrin]

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.

 * An argument could be made that choosing curves at arbitrary 384 or
512 bit levels is more "rigid" [2], with less room for the curve
creator to search for curves satisfying some
(unknown-to-the-rest-of-the-world) weakness condition.  But I don't
buy that - I'd argue that choosing the most efficient curve we know of
is also a rigid choice, and one based on a desirable criterion rather
than an arbitrary one.

 * As Mike points out, AES-192 is mostly unused.  People choose
"regular" AES-128 or "extra-strength" AES-256.  Similarly, we don't
need two extra-strength curves.  More curves means more time spent
arguing which to use, and implementing them; more compatibility
problems; and more area and memory wasted on logic and lookup tables.

So for an extra-strength curve, shouldn't we just try to find the most
efficient curve in the 384-512ish range that meets the "safe" criteria
[3], and maximizes an efficiency criterion like [4]?

Are things more complicated than that?

Trevor

[1] https://www.imperialviolet.org/2010/12/04/ecc.html
[2] http://patricklonga.webs.com/Presentation_CFRG_Selecting_Elliptic_Curves_for_Cryptography.pdf
[3] http://safecurves.cr.yp.to/
[4] https://docs.google.com/a/trevp.net/spreadsheet/ccc?key=0Aiexaz_YjIpddFJuWlNZaDBvVTRFSjVYZDdjakxoRkE&usp=sharing#gid=0