[curves] Threshold ECDSA for Bitcoin

[Mike Hamburg]

On Mar 30, 2014, at 11:19 PM, Trevor Perrin <trevp at trevp.net> wrote:

> On Fri, Mar 28, 2014 at 3:59 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>> Out of curiosity, what's wrong with the following "obvious" protocol for threshold Schnorr?
>> 
>> The signers have a polynomial share x_i of x.  All the signers in the signing group know who is signing right now, and they know that x = sum a_i x_i, and they know the a_i.  If weeding out bad participants is desired, then each signer's share [x_i]G of the public key is known to the other group members.
>> 
>> Each signer computes R_i = [k_i]G for a random nonce k_i.  They broadcast commitments to these choices, then broadcast revelations.
>> 
>> Each signer computes R = sum [a_i] R_i, so that effectively r = sum a_i k_i; and c = Hash(R,m).
>> 
>> Each signer creates and broadcasts a mini-sig s_i = c x_i + k_i.  The signature is (R, s = sum a_i s_i).  Since k = sum a_i k_i and x = sum a_i x_i, we have s = cx + k as desired.
> 
> 
> Are you describing this, or something close to it?
> 
> http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps
> 
> 
> Comparing against the threshold ECDSA of:
> 
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.9913
> http://www.cs.princeton.edu/~stevenag/bitcoin_threshold_signatures.pdf
> 
> The ECDSA protocol seems similar, except with extra steps to deal with
> the inversion.
> 
> So is it accurate to say that both threshold ECDSA and threshold
> Schnorr can be done "well" (efficiently, robustly, good security
> proofs), but the Schnorr version is simpler / less communication?
> 
> Trevor

I think the dealing phase of what I'm describing is simpler, because I always assume that exactly [threshold] many participants are trying to sign and not more.  Also my design doesn't have that full proof, and there might be a hangup somewhere in trying to produce one.

And yeah, I think it's accurate to say that both can be thresholded, but Schnorr is simpler.

-- Mike