Welcome to the resource topic for 2023/498
Title:
Subset-optimized BLS Multi-signature with Key Aggregation
Authors: Foteini Baldimtsi, Konstantinos Kryptos Chalkias, Francois Garillot, Jonas Lindstrom, Ben Riva, Arnab Roy, Alberto Sonnino, Pun Waiwitlikhit, Joy Wang
Abstract:We propose a variant of the original Boneh, Drijvers, and Neven (Asiacrypt '18) BLS multi-signature aggregation scheme best suited to applications where the full set of potential signers is fixed and known and any subset I of this group can create a multi-signature over a message m. This setup is very common in proof-of-stake blockchains where a 2f+1 majority of 3f validators sign transactions and/or blocks and is secure against \textit{rogue-key} attacks without requiring a proof of key possession mechanism.
In our scheme, instead of randomizing the aggregated signatures, we have a one-time randomization phase of the public keys: each public key is replaced by a sticky randomized version (for which each participant can still compute the derived private key). The main benefit compared to the original Boneh at al. approach is that since our randomization process happens only once and not per signature we can have significant savings during aggregation and verification. Specifically, for a subset I of t signers, we save t exponentiations in \mathbb{G}_2 at aggregation and t exponentiations in \mathbb{G}_1 at verification or vice versa, depending on which BLS mode we prefer: \textit{minPK} (public keys in \mathbb{G}_1) or \textit{minSig} (signatures in \mathbb{G}_1).
Interestingly, our security proof requires a significant departure from the co-CDH based proof of Boneh at al. When n (size of the universal set of signers) is small, we prove our protocol secure in the Algebraic Group and Random Oracle models based on the Discrete Log problem. For larger n, our proof also requires the Random Modular Subset Sum (RMSS) problem.
ePrint: https://eprint.iacr.org/2023/498
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .