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

[Ilari Liusvaara <[e-mail]>]

On Fri, Feb 20, 2015 at 01:09:56AM -0500, Phillip Hallam-Baker wrote:
> On Wed, Feb 18, 2015 at 5:51 AM, Alexey Melnikov <[e-mail]>
> 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?
> >
> 
> No, and I rather object to the phrasing.
> 
> The issue has never been the bandwidth of 9 extra bits. Its that it is an
> odd size. Going down a bit from 256 to 255 is much easier than going up a
> step.

Well, cachelines are 512 bits on (semi-)modern Intel CPUs. Breaking that
means a couple more L1 promotions (the calculations itself should produce
very few Data-L1 misses).

However, 2^512-569 in practice _breaks_ 512 bits. The issue is that working
on full 64-bit (or whatever) units in software leads to excessive carry
propagation.

This carry propagation is an issue for threee reasons:
1) Pretty much nothing above assembly has good support for carry
   propagation (pick your favorite compiled language).
2) SIMD vector units often have no carry propagation support
   (smartphones).
3) Carry propagation interacts badly with tricks modern CPUs use for
   fast code execution (Intel CPUs).

Then there is the 569 constant, which due to its size tends to cause
lots of carrying without at least two extra words (M_521 needs none).

AFAIK, the largest prime that properly fits into 8 words of 64 bits
each (512 bits) when doing arithmetic is 480-bits in size
("Ridinghood"). For 16 of 32, it is 450 bits (the second largest is
448 ("Goldilocks")).


On dedicated hardware, one can make all sorts of odd sizes. And
there doesn't seem to be any significant scalability problems
(512x512 parallel multiplier is already too big to be practical).

Mike Hamburg posted a mail about this earlier.


> Speed isn't much of a concern as this is going to be used for the long term
> trust framework and as a backup algorithm.

That's not what I have heard. I have heard actual use being
planned (and that's a major reason I found 256-level curves so
distasteful).


-Ilari