Paper 2024/1528

Schnorr Signatures are Tightly Secure in the ROM under a Non-interactive Assumption

Gavin Cho, University of Massachusetts Amherst
Georg Fuchsbauer, TU Wien
Adam O'Neill, University of Massachusetts Amherst
Marek Sefranek, TU Wien
Abstract

We show that the widely-used Schnorr signature scheme meets existential unforgeability under chosen-message attack (EUF-CMA) in the random oracle model (ROM) if the circular discrete-logarithm (CDL) assumption holds in the underlying group. CDL is a new, non-interactive and falsifiable variant of the discrete-logarithm (DL) assumption that we introduce. Our reduction is completely tight, meaning the constructed adversary against CDL has essentially the same running time and success probability as the assumed forger. This serves to justify the size of the underlying group for Schnorr signatures used in practice. To our knowledge, we are the first to exhibit such a reduction. Indeed, prior work required interactive and non-falsifiable assumptions (Bellare and Dai, INDOCRYPT 2020) or additional idealized models beyond the ROM like the algebraic group model (Fuchsbauer, Plouviez and Seurin, EUROCRYPT 2020). To further demonstrate the applicability of CDL, we show that Sparkle+ (Crites, Komlo and Maller, CRYPTO 2023), a threshold signing scheme for Schnorr, is tightly secure (under static corruptions) assuming CDL. Finally, we justify CDL by showing it holds in two carefully chosen idealized models that idealize different aspects of the assumption.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2025
Keywords
Schnorr signaturesthreshold signaturestight securityECDSA conversion function
Contact author(s)
gkcho @ umass edu
georg fuchsbauer @ tuwien ac at
amoneill @ gmail com
marek sefranek @ tuwien ac at
History
2025-06-13: last of 5 revisions
2024-09-29: received
See all versions
Short URL
https://ia.cr/2024/1528
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1528,
      author = {Gavin Cho and Georg Fuchsbauer and Adam O'Neill and Marek Sefranek},
      title = {Schnorr Signatures are Tightly Secure in the {ROM} under a Non-interactive Assumption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1528},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1528}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.