IACR News item: 05 July 2024
Matthieu Rambaud, Christophe Levrat
ePrint Report
In a fully non-interactive multi- , 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 have larger cost than fNIMs, e.g., we observe that the fNIA of BGLS (Eurocrypt'03) over 3000 signatures, takes 100x longer verification time than a batch verification of 3000 Schnorr signatures.
(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 $\mathsf{dms}$, it addresses both (ii) and (iii). It is as simple as adding Schnorr PoPs to the schoolbook pairing-based fNIM of Boldyreva (PKC'03). (ii) For a group of 1000 signers, processing these PoPs is $5+$ times faster than for the previous pairing-based PoPs, and $3+$ times faster than the processing of SMSKR, which had furthermore to be done for every new group member. (iii) In the algebraic group model (AGM), and given the current estimation of roughly 128 bits of security for the discrete logarithm (DL) in both the curves BLS12-381 and BLS12-377, then we prove a probability of forgery of $\mathsf{dms}$ no higher than about $2^{-93}$ for a time $2^{80}$ adversary. This proof of security is our main technical contribution. The only related proof before was for an interactive Schnorr-based multi-signature scheme, using Schnorr PoPs. We observe a gap in its proof, which is that the adversary has not access to a signing oracle before publishing its PoPs, although it should have. On the one hand, the gap can easily be fixed in their context. But in our context of pairing-based multi-signatures, the signing oracle produces a correlated random string which significantly complicates our extraction of the keys of the adversary. 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 BLS-based fNIM.
Our second contribution addresses (i), it is a very simple compiler: $\mathcal{M}to\mathcal{A}$ (multi-to-aggregate). 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 obtained fNIA is post-quantum 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$ bits-long variable parts, than BGLS.
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 pairing-based fNIM of Boldyreva (PKC'03). (ii) For a group of 1000 signers, processing these PoPs is $5+$ times faster than for the previous pairing-based PoPs, and $3+$ times faster than the processing of SMSKR, which had furthermore to be done for every new group member. (iii) In the algebraic group model (AGM), and given the current estimation of roughly 128 bits of security for the discrete logarithm (DL) in both the curves BLS12-381 and BLS12-377, then we prove a probability of forgery of $\mathsf{dms}$ no higher than about $2^{-93}$ for a time $2^{80}$ adversary. This proof of security is our main technical contribution. The only related proof before was for an interactive Schnorr-based multi-signature scheme, using Schnorr PoPs. We observe a gap in its proof, which is that the adversary has not access to a signing oracle before publishing its PoPs, although it should have. On the one hand, the gap can easily be fixed in their context. But in our context of pairing-based multi-signatures, the signing oracle produces a correlated random string which significantly complicates our extraction of the keys of the adversary. 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 BLS-based fNIM.
Our second contribution addresses (i), it is a very simple compiler: $\mathcal{M}to\mathcal{A}$ (multi-to-aggregate). 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 obtained fNIA is post-quantum 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$ bits-long variable parts, than BGLS.
Additional news items may be found on the IACR news page.