Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin

[JackH]

This new paper here: https://eprint.iacr.org/2016/013.pdf states that it helps with the security of wallets. From my understanding it relies on n >= t+1 servers, where t is the compromised servers.

What I am not sure of I understand correctly is how it secures the malicious part is not capable of obtaining all the keys if all servers are breached? Hope someone can elaborate on this topic a bit better.

[jl777]

This new paper here: https://eprint.iacr.org/2016/013.pdf states that it helps with the security of wallets. From my understanding it relies on n >= t+1 servers, where t is the compromised servers.

What I am not sure of I understand correctly is how it secures the malicious part is not capable of obtaining all the keys if all servers are breached? Hope someone can elaborate on this topic a bit better.

My understanding is that it is like shamir's shared secret for getting MofN

Without M valid sets of data, it is garbage with M to N valid data, you can recreate the original.

Taking this concept further, add some crypto magic and we get:

 secp256k1_schnorr_partial_sign() from the zkp lib:
* The intended procedure for creating a multiparty signature is:
 * - Each signer S with private key x and public key Q runs
 *   secp256k1_schnorr_generate_nonce_pair to produce a pair (k,R) of
 *   private/public nonces.
 * - All signers communicate their public nonces to each other (revealing your
 *   private nonce can lead to discovery of your private key, so it should be
 *   considered secret).
 * - All signers combine all the public nonces they received (excluding their
 *   own) using secp256k1_ec_pubkey_combine to obtain an
 *   Rall = sum(R[0..i-1,i+1..n]).
 * - All signers produce a partial signature using
 *   secp256k1_schnorr_partial_sign, passing in their own private key x,
 *   their own private nonce k, and the sum of the others' public nonces
 *   Rall.
 * - All signers communicate their partial signatures to each other.
 * - Someone combines all partial signatures using
 *   secp256k1_schnorr_partial_combine, to obtain a full signature.
 * - The resulting signature is validatable using secp256k1_schnorr_verify, with
 *   public key equal to the result of secp256k1_ec_pubkey_combine of the
 *   signers' public keys (sum(Q[0..n])).
 *
 *  Note that secp256k1_schnorr_partial_combine and secp256k1_ec_pubkey_combine
 *  function take their arguments in any order, and it is possible to
 *  pre-combine several inputs already with one call, and add more inputs later
 *  by calling the function again (they are commutative and associative).


Not sure if false data will prevent reconstruction, if so, then M choose n (where n is the total received and it must be between M and n) possibilities would need to be reconstructed to get a valid result. So depending on the attacker ratio, processing power available, practical limits of the M and N values that can be used will be limited

James

[JackH]

If all we are dealing with is M of N shared secret keys here, how come this is more secure than multisig? They seem to argue that deploying DSA to wallets will make them more secure. What am I missing?

[jl777]

If all we are dealing with is M of N shared secret keys here, how come this is more secure than multisig? They seem to argue that deploying DSA to wallets will make them more secure. What am I missing?

Not limited to N of 16.

a lot shamir's secret implementations can handle M of 256 as it uses a 2^8 field

but the shnorr's can handle arbitrary number of M of N. Not sure if it is practical but you could setup a M = 500,001 of N =1,000,000 to get a majority of 1 million accounts.

I wouldnt recommend it as it will probably blow up somewhere, but the current multisig implementation is not using fancy crypto, just a brute force list of pubkeys, so all the N pubkeys need to go in the blockchain. Current limit is 15 or 16 using compressed pubkeys. For older altcoins N = 3 is the most due to strict limits on script sizes

James

P.S. Another reason for more security is that by disclosing the pubkey msig addresses are not cold as the pubkey is known. However, short of using bad RNG, I wouldnt worry too much about revealing pubkeys until QC's become more widespread