[curves] Prime order curves vs Decaf

[Joost Renes]

On 01/06/17 05:27, Tony Arcieri wrote:
> During the recent standardization effort for next-gen TLS curves (i.e.
> through the CFRG), there was a big push for Edwards curves. But around
> the same time there were several papers on complete formulas for
> Weierstrass curves:
> 
> https://eprint.iacr.org/2015/1060
> 
> My rough understanding is these formulas are still less efficient than
> the Edwards equivalents, and implementing them requires (non-constant
> time?) inversions which can be completely avoided on Edwards curves. And
> all that said, I believe libsecp256k1 uses a number of the techniques
> described in these papers and is roughly 2X faster than Ed25519 at
> signature verification.

Just to clarify: there is nothing "weird" about the complete formulas
for prime order curves. Implementing them requires as few inversions as
you would need for curves in (twisted) Edwards form, namely only for
normalization from projective to affine coordinates (so perhaps once at
the end of your scalar multiplication). All operations are
constant-time. These formulas are just as easy to implement as the
complete formulas for Edwards form, but simply require some more operations.

Note that in the special case of secp256k1 (where a=0) these formulas
allow for quite a few optimizations, and they end up being only barely
slower (if at all) than the incomplete Weierstrass formulas. We also
comment on this on page 4 of said paper.

Joost