0

This paper (Crites, Komlo, Maller) on the security of Schnorr multisig and threshold signature schemes introduces a new variant of MuSig2 called SpeedyMuSig that includes proofs of possession and faster key aggregation.

As the paper states:

This is because proofs of possession allow the aggregate public key under which the multisignature is formed to be simply the product of the signers’ individual public keys. It involves group multiplications instead of costly group exponentiations and remains secure against rogue-key attacks.

What are the downsides or costs of SpeedyMuSig in comparison to MuSig2?

2 Answers 2

2

SpeedyMusig requires each signer to collect all n nonce pairs (Ri,Si) as input to the hash which determines how they are combined for the final nonce. Musig2 allows a single untrusted aggregator to collect the (Ri,Si) for all n signers and send only the aggregate (R,S) to each signer. So, SpeedyMusig requires O(n^2) communication, whereas Musig2 can be done in O(n) with a dedicated aggregator.

However, I am not sure the security is the same. SpeedyMusig says the signer much check the list (Ri,Si) to insure that no pair occurs more than once, in order for their security proof to be valid. If this check is also needed for Musig2, then the O(n) communication pattern would depend on the supposedly untrusted aggregator to do this correctly.

Musig2 uses more complicated public key aggregation, requiring n exponentiations, to solve the rogue key problem, whereas SpeedyMusig has simple key aggregation under Verified Key model. I am not sure if this interacts with the above issue somehow, or whether there is alternative security proof or some other aspect of operation that doesn't need the "no duplicates" assumption.

For myself, I would really like to combine these 2 approaches, using the O(n) nonce aggregation pattern of Musig2 but with the simple public key aggregation of SpeedyMusig.

2
  • 1
    (Disclosure: I'm one of the authors of the MuSig2 paper.) I'm pretty sure that the two mentioned drawbacks in SpeedyMuSig (less flexible nonce aggregation and rejecting duplicate nonces) are artifacts of the proof technique used by CKM, and the scheme would be secure with O(n) nonce aggregation and without the check for duplicate keys. Disclaimer: As long as we don't have a proper proof that establishes the security of the modified, "I'm pretty sure" is not a formal proof and there can be dragons. Don't implement a scheme because someone said in comment on StackExchange that it's secure. Aug 5, 2022 at 14:56
  • Thanks @real-or-random, would you have any thoughts on musig2 + BIP-32 style nonces? bitcoin.stackexchange.com/questions/115036/… Aug 25, 2022 at 23:36
0

There is a comparison table included in the Crites, Komlo, Maller paper.

speedymusig

The only downsides (included in the table and the paper) of SpeedyMuSig are the additional group exponentiations in the KeyGen phase and KeyVerify phases.

The MuSig2 paper (Nick, Ruffing, Seurin) does address the proof of possession approach:

One way to generically prevent rogue-key attacks is to require that users prove possession of the secret key, e.g., by attaching a zero-knowledge proof of knowledge to their public keys [RY07; BDN18]. However, this makes key management cumbersome, complicates implementations, and is not compatible with existing and widely used key serialization formats.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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