[Cfrg] ed448goldilocks vs. numsp384t1 and numsp512t1

["D. J. Bernstein" <[e-mail]>]

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.

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.

Microsoft says that its goal is to justify "all choices" in NUMS with
"undisputable efficiency arguments"; but the actual measurements show
considerably better efficiency/security tradeoffs for other curves.
There's a lot more wiggle room for achieving not-quite-the-best speeds
than there is for achieving the best speeds.

---Dan