Re: [Cfrg] Comparing ECC curves

[Michael Hamburg <[e-mail]>]

On Jul 24, 2014, at 10:52 AM, Yoav Nir <[e-mail]> wrote:

> 
> 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


I’d like to add:
  7) difficulty of implementation.

I think that 2), 3) and 6) are close to even across every option.

2) Every curve can use point compression once the patent expires, even if they don’t use the Montgomery ladder.  So the key size is the same as the field size, +- a few bits.

3) Weierstrass has this by default.  The other options proposed are all twisted or untwisted Edwards, or Montgomery.  These three forms are all isomorphic or isogenous to each other depending on the field, so you can pick your representation.  The isomorphisms and isogenies tend to be cheap and simple enough not to matter very much.

For a stronger curve (384-bit field and above), Bos-Costello-Longa-Naehrig and I did work which suggests that the Montgomery ladder is only 5% faster than twisted Edwards, and only if you’re compressing points.  So implementations can use twisted Edwards for everything if they want simplicity.  Montgomery-compatible point formats might still be desirable, but they aren’t that important.

6) To my knowledge, all the options we’ve discussed support constant-time operation.  The Weierstrass options are complex but doable.  The full-size packed options (field size 256, 384, 512) are slightly tricky but not that bad.


So that leaves:

1) NUMS.  I think we can all agree that this favors the BCLN curves and Curve25519.

4) Performance.  This trades off with work factor, but overall I think it favors non-BCLN curves (Curve25519, Ed448-Goldilocks, a 480-bit cousin of Goldilocks, possibly E-521) and within the BCLN curves it favors the twisted Edwards ones.

5) Work factor.  It’s clear what this is for every curve, but it isn’t clear what the ideal set of options is.

7) Difficulty of implementation.  This favors cofactor-4 curves, because constant-time Weierstrass is tricky (but doable and not horribly slow; see BCLN).

Cheers,
— Mike