[curves] FourQ
Trevor Perrin
trevp at trevp.net
Wed Sep 16 16:33:55 PDT 2015
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
More information about the Curves
mailing list