[curves] Threshold ECDSA / comparison to Schnorr

[Trevor Perrin]

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?


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?


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