[curves] Threshold ECDSA for Bitcoin

[Michael Hamburg]

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.

“Proof" of security: each party is performing the Schnorr ID protocol, which is zero-knowledge.  Any n-1 malicious parties can forge as many transcripts of this protocol as they want with any subset of the honest parties.  In the concurrent version, they are performing concurrent Schnorr ID, which is even better.

Maybe it's hard to turn that “proof” into a rigorous proof of security for a signature scheme?

— Mike


On Mar 28, 2014, at 3:36 PM, Watson Ladd <watsonbladd at gmail.com> wrote:

> On Fri, Mar 28, 2014 at 6:14 PM, Trevor Perrin <trevp at trevp.net> wrote:
>> https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/
>> http://www.cs.princeton.edu/~stevenag/bitcoin_threshold_signatures.pdf
>> 
>> Apparently based on this:
>> 
>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.9913
>> 
>> I'd be interested to hear how the state-of-the-art in threshold-ECDSA
>> compares to threshold-Schnorr, if anyone knows.
> 
> Threshold Schnorr requires computing only a multiplication and an
> addition. As a result you don't need special tricks: if you have k
> people out of n who can get the key, 2k-1 can compute the shares of
> the signature value and reconstruct in the usual manner. This way
> avoids the inversion and degree reduction protocols entirely.
> 
> Sincerely,
> Watson Ladd
>> 
>> 
>> Trevor
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/curves
> 
> 
> 
> -- 
> "Those who would give up Essential Liberty to purchase a little
> Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves