Paper 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.