Paper 2023/1613
Toothpicks: More Efficient Fork-Free Two-Round Multi-Signatures
, University of Kassel, Norwegian University of Science and Technology, CISPA Helmholtz Center for Information Security, Saarland UniversityAbstract
Tightly secure cryptographic schemes can be implemented with standardized parameters, while still having a sufficiently high security level backed up by their analysis. In a recent work, Pan and Wagner (Eurocrypt 2023) presented the first tightly secure two-round multi-signature scheme without pairings, called Chopsticks. While this is an interesting first theoretical step, Chopsticks is much less efficient than its non-tight counterparts. In this work, we close this gap by proposing a new tightly secure two-round multi-signature scheme that is as efficient as non-tight schemes. Our scheme is based on the DDH assumption without pairings. Compared to Chopsticks, we reduce the signature size by more than a factor of 3 and the communication complexity by more than a factor of 2. Technically, we achieve this as follows: (1) We develop a new pseudorandom path technique, as opposed to the pseudorandom matching technique in Chopsticks. (2) We construct a more efficient commitment scheme with suitable properties, which is an important primitive in both our scheme and Chopsticks. Surprisingly, we observe that the commitment scheme does not have to be binding, enabling our efficient construction.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2024
- Keywords
- Multi-SignaturesTightnessCommitment SchemeLossy Identification
- Contact author(s)
-
jiaxin pan @ uni-kassel de
benedikt wagner @ cispa de - History
- 2024-02-26: revised
- 2023-10-18: received
- See all versions
- Short URL
- https://ia.cr/2023/1613
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1613,
author = {Jiaxin Pan and Benedikt Wagner},
title = {Toothpicks: More Efficient Fork-Free Two-Round Multi-Signatures},
howpublished = {Cryptology ePrint Archive, Paper 2023/1613},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1613}},
url = {https://eprint.iacr.org/2023/1613}
}
