[curves] Choosing an extra-strength curve
Trevor Perrin
trevp at trevp.net
Mon May 5 16:42:19 PDT 2014
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
More information about the Curves
mailing list