Paper 2024/1081
Practical Non-interactive Multi-signatures, and a Multi-to-Aggregate Signatures Compiler
Abstract
In a fully non-interactive multi-signature, resp. aggregate-signature scheme (fNIM, resp. fNIA), signatures issued by many signers on the same message, resp. on different messages, can be succinctly ``combined'', resp. ``aggregated''.
fNIMs are used in the Ethereum consensus protocol, to produce the certificates of validity of blocks which are to be verified by billions of clients. fNIAs are used in some PBFT-like consensus protocols, such as the production version of Diem by Aptos, to replace the forwarding of many signatures by a new leader. In this work we address three complexity bottlenecks.
(i) fNIAs are costlier than fNIMs, e.g., we observe that verification time of a 3000-wise aggregate signature of BGLS (Eurocrypt'03), takes 300x longer verification time than verification of a 3000-wise pairing-based multisignature.
(ii) fNIMs impose that each verifier processes the setup published by the group of potential signers. This processing consists either in verifying proofs of possession (PoPs), such as in Pixel (Usenix'20) and in the IETF'22 draft inherited from Ristenpart-Yilek (Eurocrypt'07), which costs a product of pairings over all published keys. Or, it consists in re-randomizing the keys, such as in SMSKR (FC'24).
(iii) Existing proven security bounds on efficient fNIMs do not give any guarantee in practical curves with 256bits-large groups, such as BLS12-381 (used in Ethereum) or BLS12-377 (used in Zexe). Thus, computing in much larger curves is required to have provable guarantees.
Our first contribution is a new fNIM called
Note: See changelog (appendix E) for a list of what's changed. Expands and proves some results introduced in the 2023 version of 2020/1480.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- multi-signaturesaggregate signaturesproofs of possession
- Contact author(s)
-
matthieu rambaud @ telecom-paris fr
christophe levrat @ inria fr - History
- 2024-07-07: last of 5 revisions
- 2024-07-03: received
- See all versions
- Short URL
- https://ia.cr/2024/1081
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1081, author = {Matthieu Rambaud and Christophe Levrat}, title = {Practical Non-interactive Multi-signatures, and a Multi-to-Aggregate Signatures Compiler}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1081}, year = {2024}, url = {https://eprint.iacr.org/2024/1081} }