How does SpeedyMuSig compare to MuSig2?

Question

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?

Answer 1

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.

Answer 2

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

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.