Paper 2021/1375

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

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 $\mathsf{FROST}$ that we call $\mathsf{FROST}\mathsf{2}$, 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.

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 $$ and includes the proof of security for $$ together with distributed key generation.