[curves] Fwd: Threshold ECDSA / comparison to Schnorr

[Trevor Perrin]

Forwarding an email from Steven that was intended for this list but
didn't make it.

---------- Forwarded message ----------
From: Steven Goldfeder [...]


On Mon, Mar 16, 2015 at 4:25 PM, Trevor Perrin <trevp at trevp.net> wrote:
>
> Hi Steven,
>
> Thanks for your work, and for joining this discussion!  Couple questions:
>
>
> 1) I'm curious how this bears on the choice of EC-Schnorr vs ECDSA for
> new systems.  For Bitcoin you have to work with what exists.  But for
> a new, Bitcoin-like system, is the choice of ECDSA just as a good as
> Schnorr now - at least wrt threshold signing?
>
> I think the answer is no.  The Stinson protocol for threshold Schnorr
> seems to have several advantages for a k-of-n scheme:
>  (a) Storage doesn't increase linearly with C(n, k)
>  (b) Computation doesn't increase linearly with k
>  (c) Robust (bad participants detected)
>  (d) Doesn't need the Paillier cryptosystem / homomorphic encryption
>
> But I'm not sure how important these factors are - perhaps k is
> typically small, and (a)-(c) don't matter much?
>
>
As we show in our paper, for most practical applications these things
don't really matter as k would -- and should -- be small, but I would
agree with you that if you're building a system from scratch you might
as well use Schnorr.

>
> 2) There's increasing interesting in deterministic discrete-log
> signatures, to eliminate risk of bad RNGs.  See Ed25519 or RFC 6979.
> Can this be adapted to threshold signing?

I'd have to analyze this further, but I don't see why not. In RFC
6979, k is chosen deterministically using the private key and the
message. The threshold analog of this is for each participant to
generate their share of k deterministically using their share of the
private key and the message. Again, I have to think about this more,
but I think it could work.

Notice though that even with the deterministic scheme, k would be
deterministically chosen given a sharing of the key, not the key
itself. So different shares of the same key would result in a
different signature.

>
> Trevor
>
>
> On Sun, Mar 15, 2015 at 9:22 PM, Steven Goldfeder <sgoldfed at gmail.com> wrote:
> >> I have one question about these sorts of schemes...
> >>
> >> There's a naive approach where you don't attempt to model multisignature
> >> trust in terms of a single signature, but rather have a whitelisted set of
> >> keys, and have k / n potential signers produce an individual signature.
> >
> > Indeed, Bitcoin's built in mutlsig feature takes exactly this approach and
> > allows for addresses that have multiple associated keys. However, these
> > addresses are distinguishable from single-key addresses, and also the
> > information about the access structure being used is published on the block
> > chain. This has negative implications for privacy and anonymity. See section
> > 4.3.2 of our paper for a full discussion on this point:
> > http://www.cs.princeton.edu/~stevenag/threshold_sigs.pdf.
> >
> > On Sun, Mar 15, 2015 at 11:29 PM, Tom Ritter <tom at ritter.vg> wrote:
> >>
> >> On the topic of threshold ECC, I'll point to an implementation I ran
> >> across recently:
> >>
> >> https://github.com/cwgit/ximix/tree/master/common/src/main/java/org/cryptoworkshop/ximix/common/crypto/threshold
> >>
> >> The entire repo seems particularly interesting, but I haven't had time
> >> to dig into it closely.  RPC-based mixnet?
> >>
> >> -tom
> >> _______________________________________________
> >> Curves mailing list
> >> Curves at moderncrypto.org
> >> https://moderncrypto.org/mailman/listinfo/curves
> >
> >