More Efficient Two-Round Multi-Signature Scheme with Provably Secure Parameters

Kaoru Takemure; Yusuke Sakai; Bagus Santoso; Goichiro Hanaoka; Kazuo Ohta

Paper 2023/155

More Efficient Two-Round Multi-Signature Scheme with Provably Secure Parameters

Kaoru Takemure, The University of Electro-Communications, National Institute of Advanced Industrial Science

Yusuke Sakai, National Institute of Advanced Industrial Science and Technology

Bagus Santoso, The University of Electro-Communications

Goichiro Hanaoka, National Institute of Advanced Industrial Science

Kazuo Ohta, The University of Electro-Communications, National Institute of Advanced Industrial Science

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: Preprint.
Keywords: Multi-signatures Concrete security Tight security
Contact author(s): takemure @ uec ac jp
yusuke sakai @ aist go jp
santoso bagus @ uec ac jp
hanaoka-goichiro @ aist go jp
kazuo ohta @ uec ac jp
History: 2023-02-15: approved; 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},
      note = {\url{https://eprint.iacr.org/2023/155}},
      url = {https://eprint.iacr.org/2023/155}
}