Re: [Cfrg] ed448goldilocks vs. numsp384t1 and numsp512t1

[Michael Hamburg <[e-mail]>]

> On Oct 20, 2014, at 2:24 PM, Ilari Liusvaara <[e-mail]> wrote:
> 
> On Sat, Oct 18, 2014 at 08:30:17PM -0000, D. J. Bernstein wrote:
>> Michael Hamburg writes:
>>> I didn’t do this last time, which is (part of?) why the numbers from
>>> my own benchmarks do not match DJB’s numbers; see below.
>> 
>> Numbers are now coming into eBATS (see http://bench.cr.yp.to) for Mike's
>> fixed ed448goldilocks software, and confirm what Mike said about speed
>> compared to Microsoft's claimed speed. Here's the updated comparison
>> chart on Sandy Bridge, the microarchitecture selected by Microsoft for
>> benchmarks in http://eprint.iacr.org/2014/130.pdf:
>> 
>>    617000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
>>    666544 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
>>   1293000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.
> 
> IIRC, Mike has said that Ed448 software is not quite optimized as far
> as it would go.

Maybe not "as far as it would go”, but those numbers are for recent, optimized code, and fixes to the bug which was holding it back in previous SUPERCOP benchmarks.

> Also, these all are apples-to-apples comparisions (either all uncompressed
> or all compressed), right?

No, Goldilocks is compressed and NUMS is uncompressed.

I’ll see if I can get (possibly untwisted) NUMS curves working in the Goldilocks source tree, which would make a slightly more apples-to-apples comparison.

>> These DH ratios don't _perfectly_ predict ratios for other operations---
>> the instruction mix changes, and speeds of other operations depend on
>> choices of precomputed table size---but at this point it's unsurprising
>> to see ed448goldilocks close to numsp384t1 for signature generation:
>> 
>>    231000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
>>    234844 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
>>    446000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.
>> 
>> Also signature verification:
>> 
>>    624000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
>>    729152 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
>>   1320000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.
> 
> Here Ed448 seems to be slightly slow for some reason.
> 
> I would have estimated (on very dubious grounds) ~680k.
> 
> -Ilari

It’s due in large part to point decompression.  Point compression costs about the same as affine serialization.

For signing, Goldilocks needs to compress points but not decompress them, so it doesn’t take a speed penalty.  Also, its precomputed tables are slightly bigger than the ECCLib tables.  On the other hand, the signature is a bit slower than I’d have guessed; it might just be that the constant-time selection is vectorized, and SBR doesn’t have AVX2 and so uses SSE2 instead.

For ECDH, Goldilocks uses the Montgomery ladder, which avoids decompression at the cost of a slightly slower scalarmul.  So it has a small disadvantage vs ECCLib.

For verification, Goldilocks has to decompress and ECCLib doesn’t, which costs almost 10%.

Cheers,
— Mike