Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / multisignatures, threshold signatures, Schnorr signatures

Date: received 11 Oct 2021, last revised 11 Oct 2021

Contact author: ecrites at ed ac uk

Available format(s): PDF | BibTeX Citation

Version: 20211012:062617 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]