Paper 2021/404
Chain Reductions for Multi-Signatures and the HBMS Scheme
Mihir Bellare and Wei Dai
Abstract
Existing proofs for Discrete Log (DL) based multi-signature schemes give essentially no guarantee if the schemes are implemented, as they are in practice, in 256-bit groups. This is because the current reductions, which are in the standard model and from DL, are loose. We show that relaxing either the model or the assumption suffices to obtain tight reductions. Namely we give (1) tight proofs from DL in the Algebraic Group Model, and (2) tight, standard-model proofs from well-founded assumptions other than DL. We first do this for the classical 3-round schemes, namely BN and MuSig. Then we give a new 2-round multi-signature scheme, HBMS, as efficient as prior ones, for which we do the same. These multiple paths to security for a single scheme are made possible by a framework of chain reductions, in which a reduction is broken into a chain of sub-reductions involving intermediate problems. Overall our results improve the security guarantees for DL-based multi-signature schemes in the groups in which they are implemented in practice.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2021
- Keywords
- Signaturesreduction tightnessAlgebraic Group Model
- Contact author(s)
-
mihir @ eng ucsd edu
weidai @ eng ucsd edu - History
- 2021-09-16: last of 7 revisions
- 2021-03-27: received
- See all versions
- Short URL
- https://ia.cr/2021/404
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/404,
author = {Mihir Bellare and Wei Dai},
title = {Chain Reductions for Multi-Signatures and the HBMS Scheme},
howpublished = {Cryptology ePrint Archive, Paper 2021/404},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/404}},
url = {https://eprint.iacr.org/2021/404}
}
