Re: [Cfrg] Elliptic Curves - poll on specific curve around 256bit work factor (ends on February 23rd)

[Ilari Liusvaara <[e-mail]>]

On Wed, Feb 18, 2015 at 10:51:16AM +0000, Alexey Melnikov wrote:
> CFRG chairs are starting another poll:
> 
> Q3: (For people who want CFRG to recommend a curve at 256bit level) Is
> bandwidth cost of going to p521 worth the speed win over primes closer to
> 512 bits?

Yes, it is a win.

- The cost is ~3% (~1.5% for some cases). Any application where that
  is a concern sure will not be using 256-level curves. Probably not
  even 128-level curves.
- The small speed penalty for "breaking a stride" is more than
  compensated by the faster arithmetic due to smaller constant.
- 2^512-569 looks quite nasty to implement (large constant causing
  overflows more easily, irregular structure)
- Both primes cause issues with signatures as required hash output
  length exceeds what is commonly available (the ECC signature
  schemes blow up with even the smallest nonuniformity, so you need
  the extra bits).
- 2^521-1 is already very slow (~5-6x slower than 128-level curves,
  which was one of the main reasons I think that 256-level is too
  high), 2^512-569 is even worse.

BTW: In NIST P-x curves, the 256-bit one is the only one that isn't
some nasty-looking trinomial or pentanomial. ECC people really
beeline for nearby Mersennes.


-Ilari