Paper 2024/1704
From One-Time to Two-Round Reusable Multi-Signatures without Nested Forking
Abstract
Multi-signature schemes are gaining significant interest due to their blockchain applications. Of particular interest are two-round schemes in the plain public-key model that offer key aggregation, and whose security is based on the hardness of the DLOG problem. Unfortunately, despite substantial recent progress, the security proofs of the proposed schemes provide rather insufficient concrete guarantees (especially for 256-bit groups). This frustrating situation has so far been approached either by relying on the security of seemingly stronger assumptions or by considering restricted classes of attackers (e.g., algebraic attackers, which are assumed to provide an algebraic justification of each group element that they produce).
We present a complementing approach by constructing multi-signature schemes that satisfy two relaxed notions of security, whose applicability nevertheless ranges from serving as drop-in replacements to enabling expressive smart contract validation procedures. Our first notion, one-time unforgeability, extends the analogous single-signer notion by considering attackers that obtain a single signature for some message and set of signers of their choice. We construct a non-interactive one-time scheme based on any ring-homomorphic one-way function, admitting efficient instantiations based on the DLOG and RSA assumptions. Aggregated verification keys and signatures consist of two group elements and a single group element, respectively, and our security proof consists of a single application of the forking lemma (thus avoiding the substantial security loss exhibited by the proposed two-round schemes). Additionally, we demonstrate that our scheme naturally extends to a
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2024
- Contact author(s)
-
lrotem @ cs stanford edu
segev @ cs huji ac il
eylon yogev @ biu ac il - History
- 2024-10-21: approved
- 2024-10-18: received
- See all versions
- Short URL
- https://ia.cr/2024/1704
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1704, author = {Lior Rotem and Gil Segev and Eylon Yogev}, title = {From One-Time to Two-Round Reusable Multi-Signatures without Nested Forking}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1704}, year = {2024}, url = {https://eprint.iacr.org/2024/1704} }