Paper 2021/1375

How to Prove Schnorr Assuming Schnorr: Security of Multi- and Threshold Signatures

Elizabeth Crites, University of Edinburgh
Chelsea Komlo, University of Waterloo, Zcash Foundation
Mary Maller, Ethereum Foundation

This work investigates efficient multi-party signature schemes in the discrete logarithm setting. We focus on a concurrent model, in which an arbitrary number of signing sessions may occur in parallel. Our primary contributions are: (1) a modular framework for proving the security of Schnorr multisignature and threshold signature schemes, (2) an optimization of the two-round threshold signature scheme $\mathsf{FROST}$ that we call $\mathsf{FROST2}$, and (3) the application of our framework to prove the security of $\mathsf{FROST2}$ as well as a range of other multi-party schemes. We begin by demonstrating that our framework is applicable to multisignatures. We prove the security of a variant of the two-round $\mathsf{MuSig2}$ scheme with proofs of possession and a three-round multisignature $\mathsf{SimpleMuSig}$. We introduce a novel three-round threshold signature $\mathsf{SimpleTSig}$ and propose an optimization to the two-round $\mathsf{FROST}$ threshold scheme that we call $\mathsf{FROST2}$. $\mathsf{FROST2}$ reduces the number of scalar multiplications required during signing from linear in the number of signers to constant. We apply our framework to prove the security of $\mathsf{FROST2}$ under the one-more discrete logarithm assumption and $\mathsf{SimpleTSig}$ under the discrete logarithm assumption in the programmable random oracle model.

Note: Parts of this work appear in the CRYPTO 2022 paper "Better than Advertised Security for Non-Interactive Threshold Signatures" by Bellare, Crites, Komlo, Maller, Tessaro and Zhu. It introduces the optimization $\mathsf{FROST2}$ and includes the proof of security for $\mathsf{FROST2}$ together with distributed key generation.

Available format(s)
Public-key cryptography
Publication info
multisignatures threshold signatures Schnorr signatures
Contact author(s)
ecrites @ ed ac uk
ckomlo @ uwaterloo ca
mary maller @ ethereum org
2022-08-03: revised
2021-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elizabeth Crites and Chelsea Komlo and Mary Maller},
      title = {How to Prove Schnorr Assuming Schnorr: Security of Multi- and Threshold Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1375},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.