Re: [Cfrg] Comparing ECC curves

[Yoav Nir <[e-mail]>]

On Jul 24, 2014, at 1:23 PM, Phillip Hallam-Baker <[e-mail]> wrote:

> On Thu, Jul 24, 2014 at 12:53 PM, Mike Hamburg <[e-mail]> wrote:
>> On 7/24/2014 8:11 AM, Phillip Hallam-Baker wrote:
>> 
>> E-521 seems to have been chosen as the fastest prime giving a work
>> factor of at least 2^256. If someone finds a prime that gives a work
>> factor of 2^240 and is 30% faster, I would have to think about which I
>> preferred.
>> 
>> It may interest you to know that that the prime 2^480 - 2^240 - 1 is about
>> 40% faster than 2^512 - 569 on modern 64-bit Intel processors, meaning that
>> each field operation takes about 60% of the time.  For example, on Haswell a
>> field multiply mod 2^480 - 2^240 - 1 costs about 121 cycles, and addition
>> (with no reduce, because of reduced radix) takes fewer cycles than the
>> pipeline (it's just two AVX2 add instructions).
>> 
>> I believe it is also about that much faster on than 2^521 - 1 on Sandy
>> Bridge, but only by 20% or so on Haswell due to an implementation of
>> multiplication mod 2^521-1 using 3-way Karatsuba/Chung-Hasan with AVX2.  It
>> uses 9 limbs of 58 bits each organized as (Z[w]/(w^3-2))[t]/(t^3-w), and
>> needs AVX2 for all the adding.
> 
> Hmm, that is good for performance I guess. But doesn't help making a decision.
> 
> Talking to folk, I see the current concerns raised:
> 
> 1) Nothing up my sleeves.
> 2) Key size.
> 3) Ability to support encryption and signature with one set of code.
> 4) Performance.
> 5) Work factor

You missed:
   6) constant-time operation