Re: [Cfrg] revised requirements for new curves

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

Well one thing that leaps out is that I can get 512 bits of the NUMS
curves for the price of 256 bits of the NIST curves. And that is a BIG
difference as far as I am concerned.

The performance difference between the NUMS curves and the various
'cherry picked' primes is visible but much less significant.

On Sun, Sep 14, 2014 at 6:59 PM, Michael Hamburg <[e-mail]> wrote:
>
> 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/
>
> 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