Two-round trip Schnorr multi-signatures via delinearized witnesses

Handan Kilinc Alper; Jeffrey Burdges

Paper 2020/1245

Two-round trip Schnorr multi-signatures via delinearized witnesses

Handan Kilinc Alper and Jeffrey Burdges

Abstract

We construct a two-round Schnorr-based signature scheme (DWMS) by delinearizing two pre-commitments supplied by each signer. DWMS is a secure signature scheme in the algebraic group model (AGM) and the random oracle model (ROM) under the assumption of the hardness of the one-more discrete logarithm problem and the 2-entwined sum problem that we introduce in this paper. Our new m-entwined sum} problem tweaks the k-sum problem in a scalar field using the associated group. We prove the hardness of our new problem in the AGM assuming the hardness of the discrete logarithm problem in the associated group. We believe that our new problem simplifies the security proofs of multi-signature schemes that use the delinearization of commitments.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in CRYPTO 2021
Keywords: digital signatures multi-signatures Schnorr signatures
Contact author(s): burdges @ gnunet org
handankilinc1 @ gmail com
History: 2021-07-15: revised; 2020-10-09: received; See all versions
Short URL: https://ia.cr/2020/1245
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1245,
      author = {Handan Kilinc Alper and Jeffrey Burdges},
      title = {Two-round trip Schnorr multi-signatures via delinearized witnesses},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1245},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1245}},
      url = {https://eprint.iacr.org/2020/1245}
}