Paper 2023/155
More Efficient Two-Round Multi-Signature Scheme with Provably Secure Parameters
Abstract
In this paper, we propose the first two-round multi-signature scheme that can guarantee 128-bit security under a standardized EC in concrete security without using the Algebraic Group Model (AGM). To construct our scheme, we introduce a new technique to tailor a certain special homomorphic commitment scheme for the use with the Katz-Wang DDH-based signature scheme. We prove that an EC with at least a 321-bit order is sufficient for our scheme to have the standard 128-bit security. This means that it is easy for our scheme to implement in practice because we can use the NIST-standardized EC P-384 for 128-bit security. The signature size of our proposed scheme under P-384 is 1152 bits, which is the smallest size among the existing schemes without using the AGM. Our experiment on an ordinary machine shows that for signing and verification, each can be completed in about 65 ms under 100 signers. This shows that our scheme has sufficiently reasonable running time in practice.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. IEICE Transactions
- Keywords
- Multi-signaturesConcrete securityTight security
- Contact author(s)
-
kaoru takemure @ gmail com
yusuke sakai @ aist go jp
santoso bagus @ uec ac jp
hanaoka-goichiro @ aist go jp
kazuo ohta @ uec ac jp - History
- 2024-05-08: revised
- 2023-02-09: received
- See all versions
- Short URL
- https://ia.cr/2023/155
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/155,
author = {Kaoru Takemure and Yusuke Sakai and Bagus Santoso and Goichiro Hanaoka and Kazuo Ohta},
title = {More Efficient Two-Round Multi-Signature Scheme with Provably Secure Parameters},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/155},
year = {2023},
url = {https://eprint.iacr.org/2023/155}
}
