Paper 2021/1375

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

Elizabeth Crites and Chelsea Komlo and Mary Maller

Abstract

In this paper, we present new techniques for proving the security of multi- and threshold signature schemes under discrete logarithm assumptions in the random oracle model. The purpose is to provide a simple framework for analyzing the relatively complex interactions of these schemes in a concurrent model, thereby reducing the risk of attacks. We make use of proofs of possession and prove that a Schnorr signature suffices as a proof of possession in the algebraic group model without any tightness loss. We introduce and prove the security of a simple, three-round multisignature $\mathsf{SimpleMuSig}$. Using our new techniques, we prove the concurrent security of a variant of the $\mathsf{MuSig2}$ multisignature scheme that includes proofs of possession as well as the $\mathsf{FROST}$ threshold signature scheme. These are currently the most efficient schemes in the literature for generating Schnorr signatures in a multiparty setting. Our variant of $\mathsf{MuSig2}$, which we call $\mathsf{SpeedyMuSig}$, has faster key aggregation due to the proofs of possession.