Prof. Sebastian Faust (TU Darmstadt)
Prof. Stefan Dziembowski (University of Warsaw)
Multi-signatures enable a group of signers to produce a single signature on a given message. Recently, Drijvers et al. (S&P’19) showed that all thus far proposed two-round multi-signature schemes in the DL setting (without pairings) are insecure under concurrent signing sessions. While Drijvers et al. propose a secure two-round scheme, this efficiency in terms of rounds comes with the price of having less compact signatures: the signatures are more than twice as large as Schnorr signatures, which are becoming popular in cryptographic systems due to their practicality (e.g., they will likely be adopted by Bitcoin). If one needs a multi-signature scheme that can be used as a drop-in replacement for Schnorr signatures, then one is forced to resort either to a three-round scheme or to sequential signing sessions, both of which are undesirable options in practice.
In this work, we propose MuSig2, a simple and highly practical two-round multi-signature scheme. This is the first scheme that simultaneously i) is secure under concurrent signing sessions, ii) supports key aggregation, iii) outputs ordinary Schnorr signatures, iv) needs only two communication rounds, and v) has similar signer complexity as ordinary Schnorr signatures. Furthermore, it is the first multi-signature scheme in the DL setting that supports preprocessing of all but one round, effectively enabling a non-interactive signing process without forgoing security under concurrent sessions. We prove the security of MuSig2 in the random oracle model, and the security of a more efficient variant in the combination of the random oracle and the algebraic group model. Both our proofs rely on a weaker variant of the OMDL assumption.