Re: [Cfrg] revised requirements for new curves

[Michael Hamburg <[e-mail]>]

> On Sep 14, 2014, at 7:22 AM, Phillip Hallam-Baker <[e-mail]> wrote:
> 
> But if we plot the points on graphs of defender effort vs attacker
> work factor and look at the curves we can probably see quite easily
> what we are buying with the different approaches.


I hacked up some plots for ECDH (protected variable-base scalarmul) on Intel Sandy Bridge and Cortex A8, A9 platforms at

http://ed448goldilocks.sourceforge.net/comparison/ <http://ed448goldilocks.sourceforge.net/comparison/>

Lots of caveats follow!

It’s important to note that the curves aren’t all on equal footing here.  The measurements are from the NUMS paper, the Curve41417 paper, `openssl speed`, the Goldilocks bench utility (on SBR and Tegra 2); curve25519-donna (Curve25519 on Tegra2), SUPERCOP (Curve25519 on other platforms, Goldilocks on A8+NEON).  Of these, SUPERCOP and `openssl speed` almost certainly give less favorable numbers.

I haven’t fully implemented Ed480-Ridinghood.  The point in the graph is an estimate based on the field arithmetic being identical to Ed448-Goldilocks on 64-bit except for the shift amounts.  This is also why it doesn’t appear in the 32-bit numbers: it cannot use the same arithmetic on 32-bit platforms, but instead would take ~50% longer, which is why I didn’t propose it.

Curve25519, Curve41417, Goldilocks, and the MS “mont” curves are performing point (de)compression, but OpenSSL and the NUMS “ed” curves are not.  Point decompression would be about a 10% performance hit, but this hit may be mitigated (for stronger curves) or negated (for weaker ones) by the use of the Montgomery ladder.  Some of the software is also hashing the results and some are not.  (Goldilocks hashes; NUMS do not; I don’t know about the others.)  Goldilocks tests whether points are on the curve or twist while Curve25519 does not, but this test is cheap and adds little security.

The software benchmarked here has different amounts of optimization and is designed for different platforms.  Curve41417 has only been benchmarked on Cortex A8+NEON, and the NUMS curves have only been benchmarked on SBR.

The OpenSSL curves don’t include the latest optimizations, since they’re from 1.0.1 or 1.0.1f, compiled however the OS maintainers decided.

Curve25519-donna is not at all optimized for ARM, but I don’t have any other vectorless ARM numbers to go by, since I couldn’t get Curve25519 working in SUPERCOP on that platform.

I expect that the NUMS curves would perform passably well in scalar code on the Cortex-A9, because UMAAL can help with the carry handling.  But they would be at a disadvantage in NEON, where carry handling is much more expensive.  So I would expect the situation on Tegra 2 (with its fast scalar core but no NEON) to be comparable to that on Sandy Bridge, but on A8+NEON I would expect it to be considerably worse for the NUMS curves.

In the other direction, I expect that the numbers for Curve41417 would be similar on Sandy Bridge to how they are on NEON.  Field arithmetic is probably comparable to Ed448-Goldilocks, just as on NEON, so curve ops should be about 8% faster due to the 8% smaller curve.

I know that variable-base scalar multiplication is not the only benchmark which matters, but it’s consistently available across many curves.

I believe that all of the software contains comparable levels of side-channel protection.

Cheers,
— Mike