Tony Arcieri

2017-06-01 03:27:55 UTC

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.

"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

Tony Arcieri