Cryptology ePrint Archive: Report 2021/404

Chain Reductions for Multi-Signatures

Mihir Bellare and Wei Dai

Abstract: Current proofs of current multi-signature schemes yield bounds on adversary advantage that are loose, failing to match the indications of cryptanalysis, and failing to justify security of implementations of the schemes in the 256-bit groups that are the choice of practioners. We bridge this gap via proofs in the Algebraic Group Model (AGM). For classical 3-round schemes we give AGM proofs with tight bounds. We then give a new 2-round multi-signature scheme, as efficient as prior ones, for which we prove a tight AGM bound. These results are obtained via a framework in which a reduction is broken into a chain of sub-reductions involving intermediate problems. By giving as many as possible of the sub-reductions tightly in the standard model, we minimize use of the AGM, and also hedge the AGM proofs with standard-model ones from different starting points.

Category / Keywords: public-key cryptography / Signatures, reduction tightness, Algebraic Group Model

Date: received 25 Mar 2021, last revised 25 Mar 2021

Contact author: mihir at eng ucsd edu,weidai@eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20210327:071819 (All versions of this report)

Short URL: ia.cr/2021/404


[ Cryptology ePrint archive ]