I'm trying to find a way to amortize the interactive session setup in the MuSig signature aggregation scheme. My motivation is to use signature aggregation between devices communicating using low bandwidth (radio) channels without having to do the session setup multiple times. Ideally pre-shared public nonces could be reused for different signer sets, public keys and messages.

I've summarized below how I understand it works now, mostly from looking at the code example here:

  • each peer creates a per session secret key from the hash of the set of signers public keys and the secret key for the peer's public key (independent of the nonce)

  • each peer creates a secret nonce from the signers public keys and other hashed information, including a random number

  • each peer creates a public nonce, generated like a public key from the secret nonce.

  • all peers send to all other peers a 32-byte nonce commitment

  • all peers send to all other peers their 32-byte public nonce and verify the others against their previously shared nonce commitments

the key point seems to be that the public nonce should NOT be freely chosen by anyone after learning the public nonces of the other signers

  • each peer can now sign using their session secret key and secret nonce

  • other peers can verify the final (or partial) multi-signature using the other signers chosen public keys and their corresponding public nonces.

  • What I wonder is if the public nonce can be committed to once in advance by all peers, and then reused for different combinations of (public key, other peers public keys, messages).

It seems like peers could cache each others public nonces and reuse them for different signing sessions with different public keys and other signers as long as all signers were compelled to use the same public nonce every time they signed.

Any pointers on the restrictions for reusing these MuSig public nonces would be appreciated.

  • 2
    If you ever reuse the same public nonce, the other participants learn you private key. You can preshare lists of public nonce commitments to avoid some steps, but all participants must go through the list in lockstep. If someone is ever confused about the position in the list, they likely leak their private key. May 8 '19 at 21:31

Nonces must not be reused! In particular, in MuSig, nonces can not be reused for other combinations of public keys or messages (also if everyone uses the same public nonces all the time). This would leak private keys.

You pre-share fresh nonces by running multiple signing rounds in parallel. With the library you link to (secp256k1-zkp) this is secure as you long as you keep the session states in memory and don't copy it. Serializing the state and storing it on a persistent medium is not supported by secp256k1-zkp and difficult to get right because if you accidentally use the wrong nonce, you leak the private key.

A straightforward way to eliminate the overhead of the first two interaction rounds is by attaching the nonce commitment and nonce to already existing messages in your protocol. That way you would only have two parallel signing sessions.

There is research being done on deterministic nonces for MuSig which have zero-knowledge proofs that the nonce is derived correctly. With such proofs nonces can be derived on demand from the signer set, your private key and the message and there is no state to keep track of.

  • Also no way to use something like a BIP-32 hierarchical deterministic key generation to get public nonces from a pre-shared root and agreed derivation path? May 8 '19 at 21:48
  • 2
    No, creativity will only make things harder to analyze, but won't help you bypass fundamental problems. MuSig has three interaction rounds for a reason; if there was a known way to avoid that, we wouldn't have written a paper that uses three rounds. May 8 '19 at 21:52
  • Thanks for the answers - hopefully you won't have to answer this line of dumb questions on SO again for awhile. :-) May 8 '19 at 22:04
  • 1
    We should start a betting pool for the date of the first reported funds loss due to an insecure threshold signature implementation.
    – G. Maxwell
    May 10 '19 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.