[curves] FourQ

[D. J. Bernstein]

Michael Hamburg writes:
> FourQ does have the advantage over Kummer that it can be used for
> signatures and other non-ECDH systems.

That's an obsolete view of Kummer. What "hyperand" showed is how to
build groups that can be viewed simultaneously as small-coefficient
Kummer surfaces, for fast ECDH, and as Edwards curves, for fast
signatures etc. For example, near the end of

   http://cr.yp.to/talks/2015.07.09/slides-djb-20150709-a4.pdf

you can find an elliptic curve over F_{p^2}, where of course p is
2^127-1, having

   * group order 32*prime (higher security than FourQ's 392*prime),
   * twist order 12*prime (much safer than FourQ), and
   * full support for the Kummer ladder with 5-digit coefficients.

Another example has group order 720*prime, twist order 260*prime, and
amazingly small coefficients---even better for computation than the
Gaudry--Schost surface.

I don't think FourQ is doing anything for signatures that won't work for
these curves---it's the same field, the same curve shape, etc. So the
only interesting question is DH, which is why I commented before on DH.

It's unfortunate that the FourQ paper doesn't acknowledge what the
previous literature says about this. The principle here can't be as
simple as "we don't care about speeds until implementations have been
published": the authors also fail to compare to, e.g., the speeds from
Andrew Moon and the more recent speeds from Tung Chou on most of the
platforms they've selected, even though all of that code was publicly
available before the first version of this paper appeared.

I suppose that seeing this sort of stunt provides extra incentive for
designers and implementors to submit to eBATS, and for me to hurry up
and get eBATS updates out the door faster. I've been working on a new
system that will get benchmarks done much more quickly (with the same
API for implementations), but I realize that this shouldn't take time
away from maintaining the existing system.

---Dan