[curves] FourQ

[D. J. Bernstein]

Trevor Perrin writes:
>  - FourQ is a little faster (~10%) than 25519 without endomorphisms

Maybe, but for such small differences one has to look very carefully at
what exactly is being measured (e.g., is point validation included? what
exactly are the assumptions on the input and output?) and of course also
the quantitative security level (2^122.5 vs. 2^125.8---one expects this
to have a close-to-cubic effect).

What's clear from the literature is that about 10% of the time in a
typical conservative scalarmult is spent on inversion, and of course
this part becomes much faster for a quadratic extension field. On the
other hand, a prime field provides more flexibility in adapting to the
multipliers available on the platform. Surely Curve25519 should use 5
limbs with Intel's new 52-bit multiplication instructions, for example,
while GF((2^127-1)^2) will be stuck using 6 limbs.

>  - endomorphisms give close to 2x speedup

Yes, that's about right.

Watson Ladd writes:
> This is an issue for Kummer surfaces also, but there we do not know
> how to attack invalid points.

What "hyperand" recommends is to simply send compressed elliptic-curve
points, rather than sending Kummer points. Unlike FourQ, hyperand
provides twist-secure curves, so it's safe to skip point validation. The
receiver then switches over to the fast Kummer formulas to compute the
DH shared secret.

---Dan