[curves] FourQ

[Trevor Perrin]

On Tue, Sep 15, 2015 at 3:01 PM, D. J. Bernstein <djb at cr.yp.to> wrote:
>
> 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 don't understand your criticism:

They cite Tung Chou's (not-yet-conference-published!) "sandy2x" work
for Sandy Bridge and Ivy Bridge, which according to [1] are the
platforms it was "tailored for".  Those are also the platforms Tung
Chou presented numbers for in [2].

Tung Chou's 25519 code brings performance closer to FourQ (without
endomorphisms) on those platforms, but 25519 is still slower, and much
slower with endomorphisms.  Maybe having numbers for Haswell etc would
flesh out the picture, but I wouldn't expect it to change the overall
conclusion that FourQ is faster.

So it seems like they did a good job comparing with recent state of the art.

My only quibble with the FourQ performance analysis is that adding the
var-base and fixed-base numbers into an "ephem DH" and claiming this
represents the "context of a real-world protocol" isn't that helpful.

Different protocols will have different ratios of variable-base to
fixed-base (keygen) operations.  MSR likes to argue against the
Montgomery ladder, since it doesn't lend itself to fixed-base
optimization, but I think that's a separate debate that doesn't add
much here.

Trevor

[1] https://sites.google.com/a/crypto.tw/blueprint/
[2] http://csrc.nist.gov/groups/ST/ecc-workshop-2015/presentations/session6-chou-tung.pdf