What is the ideal multisignature scheme for Edwards Curves?

[Zaki Manian]

Here is a question I've been thinking about.

edDSA as developed by Dan Bernstein and Tanja Lange and standardized by the IETF uses a variant of Schnorr Signature Scheme that has increased hash collision resistance by hashing the private key into signature. Based on the discussion of the CFRG, it's widely accepted that this is a stronger scheme than a standard Schnorr signatures. One consequence of this is that normal Schnorr multisignature approach to combine signatures doesn't work with the standardized edDSA construction. 

I believe the approach Cothorities is taking is implementing a Sha256 ed25519 Schnorr signature scheme.  I think a goal for ed25519 multisignatures should be to reuse as much of widely deployed edDSA codebases as possible even if it isn't posisble to reuse sign and verify functions themselves. I'm curious what people think of that approach. At very least, I'd think it would be good to define a Sha512 ed25519 Schnorr signature to reuse Sha512 from edDSA.

Thoughts?

[Tony Arcieri]

It's also a question I've been thinking about. I would love to see some sort of standard here out of the CFRG.

[Bryan Ford]

Hi Zaki,

On Mar 8, 2016, at 7:14 PM, Zaki Manian <zma...@gmail.com> wrote:

Here is a question I've been thinking about.

edDSA as developed by Dan Bernstein and Tanja Lange and standardized by the IETF uses a variant of Schnorr Signature Scheme that has increased hash collision resistance by hashing the private key into signature. Based on the discussion of the CFRG, it's widely accepted that this is a stronger scheme than a standard Schnorr signatures. One consequence of this is that normal Schnorr multisignature approach to combine signatures doesn't work with the standardized edDSA construction. 

I assume you’re referring to the fact that Bernstein’s construction uses the (point,scalar) representation rather than the traditional (scalar,scalar) challenge-response representation?  I think I remember that choice being discussed extensively on the CFRG list - both representations have minor advantages and disadvantages.  

You’re right that CoSi currently uses the traditional (scalar,scalar) challenge-response format in the collective signatures it produces, but fortunately that’s completely trivial to change; nothing in the CoSi protocol depends on that choice in any fundamental way.  The protocol always computes all the values needed to produce both signature represents in any case; it’s just a matter of choosing whether to actually include the challenge itself or the scalar-multiplication of the challenge with the base point in the final multi signature.  In a multisignature standard based on EdDSA it would presumably make sense to align the representation as closely as possible with EdDSA.

I believe the approach Cothorities is taking is implementing a Sha256 ed25519 Schnorr signature scheme.  I think a goal for ed25519 multisignatures should be to reuse as much of widely deployed edDSA codebases as possible even if it isn't posisble to reuse sign and verify functions themselves. I'm curious what people think of that approach. At very least, I'd think it would be good to define a Sha512 ed25519 Schnorr signature to reuse Sha512 from edDSA.

Actually I think the current implementation is using SHA3 - but again I agree, for standardisation purposes it probably makes sense to align as closely as possible with the hashes chosen in the corresponding “base” signature schemes.  Which would mean SHA2-512 when using the Ed25519 curve, and SHAKE256 when using the Ed448 curve, as per the CFRG’s recent decision regarding the latter.

Cheers

Bryan

Thoughts?

--
You received this message because you are subscribed to the Google Groups "Cothority Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cothority+...@googlegroups.com.
To post to this group, send email to coth...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cothority/e4cb211b-db28-4981-b02a-cdb9b1b1eb79%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Bryan Ford]

By the way, it's great that you brought up these issues of alignment with the EdDSA standards. 

Another one that occurs to me is the question of how the commits are chosen. In EdDSA the signer chooses its commit deterministically using a hash based on the secret key and the message. For individual signatures this has a big upside (robustness against broken RNGs) and basically no downside I know of.  

In CoSi, signers could use this approach too to generate their individual commits, but they currently do not. And in the case of CoSi the tradeoffs are less clear: the upside of EdDSA's deterministic approach is "attenuated", but there's more of a real downside. By "attenuated" I simply mean the resulting collective signatures remain secure unless *all* of the signers have compromised keys or bad RNGs. 

The downside of the EdDSA approach in the CoSi context is that the message to be signed must be made available in the Announcement phase, since all the deterministically-generated Schnorr commits must depend on that message. This means it takes a full two round trips through the tree to produce a collective signature. With randomly-generated commits, in contrast, the Announce and Commit phases can be kept independent of the message to be signed, and hence can be performed ahead of time as a preprocessing step, or pipelined as ByzCoin does, so that from "message available" to "collective signature produced" there's only one full round-trip through the collective signing tree. 

The CoSi protocol is already designed to support and permit both of these modes of operation (either include or don't include the message in the round announcement) - but the choice represents an interesting question and set of tradeoffs to consider. 

Again thanks for bringing up these issues. 

Cheers

Bryan

[Zaki Manian]

Hi Bryan, thank you for your detailed comments. Congrats on the positive press for Cothorities this week. 

I think we have a vague outline of a spec for a multisignature standard. 

- (Scalar, Point) Signature format 
- Sha512 and SHAKE for hashing
- A stateful signers( random commitments) and stateless signers(deterministic commitments)  I think both is the right answer. The amortization possibilities of random commitments are too compelling for situations where lots of signatures among the same parties are needed. It removes the trade off of an additional round trip vs larger signatures in consensus protocols.

Do you have any thoughts on work plan towards a prototype? I've wanted to figure out how to construct the (Scalar,Point) multisignature format and your comments definitely point past where I got stuck. But I doubt I have time to work on ECC math in the immediate future.

[Philipp Jovanovic]

Hi Zaki,

let me pitch in. In case you want to hack a bit on the code yourself, here are the relevant parts which produce the collective signature (including the tests):

https://github.com/dedis/cothority/blob/master/lib/cosi/cosi.go#L54-L61

https://github.com/dedis/cothority/blob/master/lib/cosi/cosi_test.go

If you want to run a test execute:

```

cd lib/cosi

go test -run TestCosiChallenge

```

or

```

cd lib/cosi

go test -run TestCosiResponse

```

Currently we do not have a suite with SHA512 but it should be just a matter of creating a new variant of:

https://github.com/dedis/crypto/blob/master/edwards/ed25519/suite.go

The implementation of the SHAKE hash function is here:

https://github.com/dedis/crypto/blob/master/cipher/sha3/shake.go

In case you have more questions feel free to ask any time. :)

All the best,

Philipp

--
You received this message because you are subscribed to the Google Groups "Cothority Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cothority+...@googlegroups.com.
To post to this group, send email to coth...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/cothority/66eeb550-7044-4cc6-92b5-ae3e86a917d0%40googlegroups.com.