Paper 2020/1261

MuSig2: Simple Two-Round Schnorr Multi-Signatures

Jonas Nick, Blockstream
Tim Ruffing, Blockstream
Yannick Seurin, ANSSI
Abstract

Multi-signatures enable a group of signers to produce a joint signature on a joint message. Recently, Drijvers et al. (S&P'19) showed that all thus far proposed two-round multi-signature schemes in the pure DL setting (without pairings) are insecure under concurrent signing sessions. While Drijvers et al. proposed a secure two-round scheme, this efficiency in terms of rounds comes with the price of having signatures that 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 in 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 pure DL setting that supports preprocessing of all but one rounds, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2021
DOI
10.1007/978-3-030-84242-0_8
Keywords
multi-signaturesSchnorr signatureskey aggregationdiscrete logarithm problemforking lemmaBitcoin
Contact author(s)
jonas @ n-ck net
crypto @ timruffing de
yannick seurin @ m4x org
History
2023-10-20: last of 2 revisions
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1261
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1261,
      author = {Jonas Nick and Tim Ruffing and Yannick Seurin},
      title = {MuSig2: Simple Two-Round Schnorr Multi-Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1261},
      year = {2020},
      doi = {10.1007/978-3-030-84242-0_8},
      note = {\url{https://eprint.iacr.org/2020/1261}},
      url = {https://eprint.iacr.org/2020/1261}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.