Re: [Cfrg] Comparing ECC curves

[Phillip Hallam-Baker <[e-mail]>]

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

My point here is meeting a work factor precisely is much less
important to me than performance.

But the other argument raised is that if you drop the requirement for
hitting the work factor exactly and allow a tradeoff between work
factor and performance this clouds the argument for 'nothing up my
sleeves'.

I think that is actually a good argument. If the requirement is for
256 and nothing less, that is completely defensible. Opening the door
to performance/work factor tradeoffs makes the decision subjective and
we get back to the problem of the proposers proving that there is
nothing up their sleeves.


The objective here is not to decide which algorithms are good, it is
deciding which to reject. I am arguing for each of those criteria as
criteria for reducing the search space.