MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces

Jonas Nick; Tim Ruffing; Yannick Seurin; Pieter Wuille

Paper 2020/1057

MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces

Jonas Nick, Tim Ruffing, Yannick Seurin, and Pieter Wuille

Abstract

MuSig is a multi-signature scheme for Schnorr signatures, which supports key aggregation and is secure in the plain public key model. Standard derandomization techniques for discrete logarithm-based signatures such as RFC 6979, which make the signing procedure immune to catastrophic failures in the randomness generation, are not applicable to multi-signatures as an attacker could trick an honest user into producing two different partial signatures with the same randomness, which would reveal the user's secret key. In this paper, we propose a variant of MuSig in which signers generate their nonce deterministically as a pseudorandom function of the message and all signers' public keys and prove that they did so by providing a non-interactive zero-knowledge proof to their cosigners. The resulting scheme, which we call MuSig-DN, is the first Schnorr multi-signature scheme with deterministic signing. Therefore its signing protocol is robust against failures in the randomness generation as well as attacks trying to exploit the statefulness of the signing procedure, e.g., virtual machine rewinding attacks. As an additional benefit, a signing session in MuSig-DN requires only two rounds instead of three as required by all previous Schnorr multi-signatures including MuSig. To instantiate our construction, we identify a suitable algebraic pseudorandom function and provide an efficient implementation of this function as an arithmetic circuit. This makes it possible to realize MuSig-DN efficiently using zero-knowledge proof frameworks for arithmetic circuits which support inputs given in Pedersen commitments, e.g., Bulletproofs. We demonstrate the practicality of our technique by implementing it for the secp256k1 elliptic curve used in Bitcoin.

Note: Revision 15 Oct 2020: Minor fixes and improvements

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. MAJOR revision.2020 ACM Conference on Computer and Communications Security (CCS 2020)
DOI: 10.1145/3372297.3417236
Keywords: digital signatures multi-signatures Schnorr signatures MuSig non-interactive zero-knowledge proofs deterministic nonces
Contact author(s): jonas @ n-ck net
crypto @ timruffing de
yannick seurin @ m4x org
pieter @ wuille net
History: 2020-10-15: revised; 2020-09-01: received; See all versions
Short URL: https://ia.cr/2020/1057
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1057,
      author = {Jonas Nick and Tim Ruffing and Yannick Seurin and Pieter Wuille},
      title = {MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1057},
      year = {2020},
      doi = {10.1145/3372297.3417236},
      note = {\url{https://eprint.iacr.org/2020/1057}},
      url = {https://eprint.iacr.org/2020/1057}
}