Two-Round Multi-Signatures from Okamoto Signatures

Kwangsu Lee; Hyoseung Kim

Paper 2022/1117

Two-Round Multi-Signatures from Okamoto Signatures

Kwangsu Lee

, Sejong University

Hyoseung Kim, Korea University

Abstract

Multi-signatures (MS) are a special type of public key signature (PKS) in which multiple signers participate cooperatively to generate a signature for a single message. Recently, applications that use an MS scheme to strengthen the security of blockchain wallets or to strengthen the security of blockchain consensus protocols are attracting a lot of attention. In this paper, we propose an efficient two-round MS scheme based on Okamoto signatures rather than Schnorr signatures. To this end, we first propose a new PKS scheme by modifying the Okamoto signature scheme, and prove the unforgeability of our PKS scheme under the discrete logarithm assumption in the algebraic group model (AGM) and the non-programmable random oracle model (ROM). Next, we propose a two-round MS scheme based on the new PKS scheme and prove the unforgeability of our MS scheme under the discrete logarithm assumption in the AGM and the non-programmable ROM. Our MS scheme is the first one to prove security among two-round MS based on Okamoto signature.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Mathematics
DOI: 10.3390/math11143223
Keywords: Public-key signature Multi-signature Okamoto signature Key aggregation Algebraic group model
Contact author(s): kwangsu @ sejong ac kr
History: 2023-07-22: last of 2 revisions; 2022-08-29: received; See all versions
Short URL: https://ia.cr/2022/1117
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1117,
      author = {Kwangsu Lee and Hyoseung Kim},
      title = {Two-Round Multi-Signatures from Okamoto Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1117},
      year = {2022},
      doi = {10.3390/math11143223},
      url = {https://eprint.iacr.org/2022/1117}
}