[curves] FourQ

[Trevor Perrin]

On Wed, Sep 16, 2015 at 3:21 AM, D. J. Bernstein <djb at cr.yp.to> wrote:
>
> Certainly there _is_ a speedup. This isn't news; see, e.g., the Kummer
> paper and the literature cited there. The problem is that the FourQ
> paper quantitatively _exaggerates_ the FourQ speedup. Consider, for
> example, the following statement from the paper:
>
>    When considering the results for the DH key exchange, FourQ performs
>    1.8--3.5 times faster than Curve25519.
>
> The ratios here come from Table 5, dividing the "ephem. DH" numbers
> (what they mean is one-time DH: fixed-base time + variable-base time)
> between

Agreed 3.5x is a little unfair, as they assume 1:1
fixed-base:variable-base operations is the typical ratio, but then
compare a 25519 implementation that doesn't have a fixed-base
optimization against a FourQ implementation that does.

Their broader claim is:

"it is [...] between two and three times faster than Curve25519."
http://research.microsoft.com/en-us/projects/fourqlib/

"it is between two and three times faster than curves that are
currently under consideration as NIST alternatives, such as
Curve25519."
http://eprint.iacr.org/2015/565.pdf

Comparing variable-base, and FourQ with endomorphisms, their numbers
are 2.5-2.75 faster than the CHES2011 implementation, and 2.1-2.2x
faster than Tung Chou's on Sandy Bridge and Ivy Bridge.

Considering all this, it looks roughly like:
 - FourQ is a little faster (~10%) than 25519 without endomorphisms
 - endomorphisms give close to 2x speedup
 - so overall a little over 2x for variable-base (but only a little
faster for fixed-base)?

Seem about right?


Trevor