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

Authors: Elizabeth Crites, Chelsea Komlo, Mary Maller | Venue: preprint | Source

Abstract

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 that we call , and (3) the application of our framework to prove the security of 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 scheme with proofs of possession and a three-round multisignature . We introduce a novel three-round threshold signature and propose an optimization to the two-round threshold scheme that we call . 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 under the one-more discrete logarithm assumption and under the discrete logarithm assumption in the programmable random oracle model.

BibTeX

@Misc{EPRINT:CriKomMal21,
  author = {Elizabeth Crites and Chelsea Komlo and Mary Maller},
  title = {How to Prove {Schnorr} Assuming {Schnorr}: Security of Multi- and Threshold Signatures},
  year = {2021},
  url = {https://eprint.iacr.org/2021/1375},
  howpublished = {Cryptology ePrint Archive, Report 2021/1375},
}