[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.

-- 
Tony Arcieri
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170531/5f020f7d/attachment.html>