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

[Michael Hamburg <[e-mail]>]

Hi Phillip.

> On Feb 23, 2015, at 11:33 AM, Phillip Hallam-Baker <[e-mail]> wrote:
> 
> Yes, I know there will be error bars on the numbers because the code will run at different speeds on different platforms. But lets face it, modern platforms don't actually vary a whole lot.

This assertion may be true for Sandy Bridge vs Haswell, or even for other 64-bit platforms like Bulldozer, MIPS64, AArch64 etc.  I believe it’s worth noting that there is a large difference between 64-bit, 32-bit with no bignum acceleration, 32-bit with UMAAL but no vector unit, 32-bit with a NEON vector unit, etc.

For this difference, we mostly have conjecture.  As far as I’m aware, Ed448-Goldilocks is the only one of the proposed stronger curves which has been implemented and benchmarked on both ARM32 and AMD64, so we can’t measure how much the architecture influences rankings of curve speed.  This curve was also designed explicitly with 32-bit performance in mind, and it performs very well on NEON.

> A 10% difference in speed might be enough to make an objective choice between Edwards and Montgomery but only experts know the difference between those.
> 
> 
> In short, I want to see the end of this particuar thread:
> 
> http://www.ietf.org/mail-archive/web/cfrg/current/msg05349.html <http://www.ietf.org/mail-archive/web/cfrg/current/msg05349.html>
> 
> At the time the code for E512-569 was actually 15% faster than for E521-1


I believe that the most recent discussion of the performance of strong curves is in this thread:

https://www.ietf.org/mail-archive/web/cfrg/current/msg05733.html <https://www.ietf.org/mail-archive/web/cfrg/current/msg05733.html>

This is for field arithmetic on Haswell, and there are several caveats mentioned in that thread.  Some approximation of relative performance of the whole curve (across implementation tradeoffs, Montgomery vs Edwards, comb size etc) can be obtained by multiplying the M and S times by the number of bits in the field.  See

http://www.ietf.org/mail-archive/web/cfrg/current/msg06084.html <http://www.ietf.org/mail-archive/web/cfrg/current/msg06084.html>

So for EG a 60:40 M:S ratio, normalized to MS NUMS P384, the rough curve timing ratios would be:

384: 1.00
389: 0.93
448: 1.17
480: 1.25
512: 2.21
521: 1.68

Note that the inflection point in performance is likely to occur lower on 32-bit.  In particular, I expect that the 480:448 cycle cost ratio is likely to be in the neighborhood of 1.5:1 on ARM32+NEON instead of 1.07:1.

> If Microsoft care enough about this that they are willing to put in more cycles optimizing open source code for their favored outcome than supporters of E521-1, then I say let them have it.

I don’t think that effort should be the main factor in standards.  But if you think so, would you also support the converse?

Cheers,
— Mike