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 signaturesmulti-signaturesSchnorr signaturesMuSignon-interactive zero-knowledge proofsdeterministic 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.