[curves] Prime order curves vs Decaf

[Tony Arcieri]

Cofactors seem to complicate both the design and safe implementation of
"exotic" protocols on top of what are effectively signature mechanisms,
e.g. Schnorr/Ring signatures.

The Bitcoin ecosystem (by which I really mean Blockstream) made a Schnorr
signature algorithm on top of secp256k1 and have implemented many of the
sort of exotic constructions I have been referring to earlier.

Others (including my employer) have attempted to implement similarly exotic
constructions on top of Edwards curves, namely the cofactor 8
"edwards25519" curve. Sometimes this hasn't gone so well, see CryptoNote
and the recent "CryptoNote and equivalent points" thread.

It seems like Decaf provides a strategic mitigation for these sorts of
attacks, as opposed for the
always-multiply-by-the-cofactor-and-check-for-identity tactical response
suggested by Monero's developers:

https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html


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. I also believe I've heard Decaf decompression of Ed25519
points can actually be faster than the regular Edwards decompression.

Seems like a complicated topic. Curious about people's thoughts.

[Trevor Perrin]

Post by Tony Arcieri
It seems like Decaf provides a strategic mitigation for these sorts of
attacks, as opposed for the
always-multiply-by-the-cofactor-and-check-for-identity tactical response
https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html

A small point: that link doesn't suggest to
multiply-by-cofactor-and-check-for-identity.

It suggests to multiply by *SUBGROUP ORDER* and reject if *NOT*
identity, which is different.

(Multiplying the key image by cofactor might be a different fix).

Otherwise good questions, I'm curious about people's thoughts too.


Trevor

[Henry de Valence]

Post by Tony Arcieri
I also believe I've heard Decaf decompression of Ed25519
points can actually be faster than the regular Edwards decompression.

I think I might have said the thing you're referring to; what I said
was that, after changing our (mine and Isis') prototype of a Decaf
encoding for Curve25519 to use Mike Hamburg's trick for doing the
computation with only one inverse square root, I measured the cost of
Decaf decompression as slightly less than the cost of
Edwards-Y-plus-sign decompression plus multiplication by 8 to "clear"
the cofactor [1]. This wasn't a scientific benchmark or anything,
just a `cargo bench` run inside a VM to get a ballpark estimate.

[1]: "clear" seems like a bad word here, because (at least to me) it
sounds like the 8-torsion component of the input point is removed
while the l-torsion component is unaffected. Maybe "mangle" might be a
better word?

Post by Tony Arcieri
Seems like a complicated topic. Curious about people's thoughts.

Just my opinions:

Decaf for an existing cofactor-4 curve seems like a very elegant and
non-invasive solution.

Decaf for an existing cofactor-8 curve (in particular, Decaf for
Curve25519) seems like a somewhat messier solution that could be added
to existing Ed25519 implementations relatively easily.

I don't understand the benefit of specifying a new prime-order curve
versus specifying a cofactor-4 curve with Decaf.

Henry

[Joost Renes]

Post by Tony Arcieri
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
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