w3f / schnorrkel

Schnorr VRFs and signatures on the Ristretto group
BSD 3-Clause "New" or "Revised" License
310 stars 93 forks source link

Signable vs Singers #5

Open burdges opened 5 years ago

burdges commented 5 years ago

There are some protocols that adapt the signing set, like multi-signatures, threshold signatures, and ring signatures, at least the first of which shall get implemented here. Afaik these produce extra protocol round trips in some DKG, except maybe not ring sigs.

There are also protocols that adapt the signature's function, like implicit certificates and DLEQ proofs for VRFs. Only some like implicit certificates produce extra protocol round trips, but not others like DLEQ proofs.

Is there a nice abstraction boundary between these two aspects of a generalized signature scheme?

For sure, there are combinations that make no sense, like a ring sig VRF gives the adversary choices, but a multi-sig VRF makes sense, and a threshold VRF makes sense in pairing land so maybe here too. An implicit certificate likely makes sense with ring, multi, threshold, blind, etc. signers too.

There are several notions that fall on both sides however:

Adaptor signatures sound like they fall outside this spectrum, in that any of the above could plausibly be made into adaptor constructions. I'm unsure if any non-anonymous payment channel constructions like adaptor signatures actually make sense or what their security proofs look like.

We're unsure if blind signatures can safely be implemented, due to Wagner's attack and the mitigations suck. We know blind threshold, ring, etc. scheme but blind implicit certificates should make sense too. And CloudFlare's PrivacyPass uses blind DLEQ proofs, so blind VRFs make sense and may even give the best route to blind signatures.

burdges commented 5 years ago

These are some natural targets for such a Signable abstraction:

Appendix A of the MuSig paper discusses Interactive Aggregate Signatures (IAS) in which cosigners' messages differ. Appendix A.3 gives a secure scheme that correctly binds signers to their messages. A priori, anything like this should wait on mBCJ #15 however.

A multi-signer VRF might be a natural application of such IAS scheme. Yet, one should normally have a commit and reveal phase for each individual signer's actual VRF output. A priori, all signers must know the message for signing, so this commit and reveal phase might happens concurrently with the R commit and reveal phase, except prevents using faster approaches like mBCJ. It's likely okay to hash only the commit so long as the actual signature fails if the commit is false, thereby making a two-round scheme like mBCJ viable, but this requires a security argument.

burdges commented 4 years ago

There is an easy fix to the Wagner attacks in https://eprint.iacr.org/2019/877.pdf so blind schnorr sounds doable now.

There is some document on applying adaptor and blind signatures at https://github.com/RubenSomsen/rubensomsen.github.io/blob/master/img/statechains.pdf

burdges commented 4 years ago

At first blush, the starsig musig code looks more elegant and better abstracted than my musig code. I do minimize the internal state better in places, which matters. I do think my separate add methods gives a nicer interface in some ways, but actually asking that developers build this themselves gives them more flexibility, especially given the session types restricting them so much. How much refactoring should be done here?

cc https://github.com/w3f/schnorrkel/issues/51

burdges commented 4 years ago

We're developing more of a sense of this. Adaptor implicit certificates https://github.com/w3f/schnorrkel/issues/4 but now future algorithms for blind signatures and threshold signatures should attempt alignment with https://bitcoinedge.org/transcript/telaviv2019/statechains