Paper 2024/1081
Practical Noninteractive Multisignatures, and a MultitoAggregate Signatures Compiler
Abstract
In a fully noninteractive multisignature, resp. aggregatesignature 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 PBFTlike 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 3000wise aggregate signature of BGLS (Eurocrypt'03), takes 300x longer verification time than verification of a 3000wise pairingbased 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 RistenpartYilek (Eurocrypt'07), which costs a product of pairings over all published keys. Or, it consists in rerandomizing 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 256bitslarge groups, such as BLS12381 (used in Ethereum) or BLS12377 (used in Zexe). Thus, computing in much larger curves is required to have provable guarantees. Our first contribution is a new fNIM called $\mathsf{dms}$, it addresses both (ii) and (iii). It is as simple as adding Schnorr PoPs to the schoolbook pairingbased fNIM of Boldyreva (PKC'03). (ii) For a group of 1000 signers, verification of these PoPs is: $5+$ times faster than for the previous pairingbased PoPs; and $3+$ times faster than the Verifier's processing of the setup in SMSKR (and contrary to the latter, needs not be restarted when a new member joins the group). (iii) We prove a tight reduction to the discrete logarithm (DL), in the algebraic group model (AGM). Given the current estimation of roughly 128 bits of security for the DL in both the curves BLS12381 and BLS12377, we deduce a probability of forgery of $\mathsf{dms}$ no higher than about $2^{93}$ for a time $2^{80}$ adversary. This reduction is our main technical contribution. The only related proof before was for an interactive Schnorrbased multisignature scheme, using Schnorr PoPs. Our approach easily fills a gap in this proof, since we take into account that the adversary has access to a signing oracle even before publishing its PoPs. But in our context of pairingbased multisignatures, extraction of the keys of the adversary is significantly more complicated, since the signing oracle produces a correlated random string. We finally provide another application of $\mathsf{dms}$, which is that it can be plugged in recent threshold signatures without setup (presented by Das et al at CCS'23, and Garg et al at SP'24), since these schemes implicitly build on any arbitrary BLSbased fNIM. Our second contribution addresses (i), it is a very simple compiler: $\mathcal{M}to\mathcal{A}$ (multitoaggregate). It turns any fNIM into an fNIA, suitable for aggregation of signatures on messages with a prefix in common, with the restriction that a signer must not sign twice using the same prefix. The resulting fNIA is postquantum secure as soon as the fNIM is, such as Chipmunk (CCS'23). We demonstrate the relevance for Diem by applying $\mathcal{M}to\mathcal{A}$ to $\mathsf{dms}$: the resulting fNIA enables to verify 39x faster an aggregate of 129 signatures, over messages with $7$ bitslong variable parts, than BGLS.
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)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Keywords
 multisignaturesaggregate signaturesproofs of possession
 Contact author(s)

matthieu rambaud @ telecomparis fr
christophe levrat @ inria fr  History
 20240707: last of 5 revisions
 20240703: 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 Noninteractive Multisignatures, and a MultitoAggregate Signatures Compiler}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1081}, year = {2024}, url = {https://eprint.iacr.org/2024/1081} }