[curves] Comparing high-speed / high-security curve implementations

[D. J. Bernstein]

Trevor Perrin writes:
> But maybe things are more interesting at 128-bits than I thought?

>From an academic perspective, things are definitely interesting. It's
not as if anyone has a serious attack strategy on CM, or subfields, or
genus 2. Those structures seem to allow considerably higher security
levels for the same performance budget. (If the user can afford high
security without these structures, great, but otherwise it's easy to
argue that having structures that _might_ allow attacks is better than
_definitely_ reducing the security level.)

Unfortunately, from a real-world perspective, my impression is that
patents 7110538 and 7995752 make it practically impossible to deploy any
GLV/GLS software, including

   * the Longa--Sica software (Asiacrypt 2012);
   * the newer Bos--Costello--Hisil--Lauter software (CHES 2013);
   * the Oliveira--López--Aranha--Rodríguez-Henríquez software (CHES 2013);
   * the Costello--Hisil--Smith software (Eurocrypt 2014); and
   * the Faz-Hernández--Longa--Sánchez software.

These patents have priority dates of 24 December 1998, which might sound
like expiration on 24 December 2018, but they also have patent-term
adjustments of 277 days and 267 days respectively, so they'll actually
expire late in 2019.

What's left is pure Kummer software, specifically

   * Bos--Costello--Hisil--Lauter (Eurocrypt 2013) and
   * Bernstein--Chuengsatiansup--Lange--Schwabe,

and of course conservative ECC options such as Curve25519.

---Dan