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
Abstract

We show that the 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, a new, non-interactive variant of DL we introduce, holds in the underlying group. Our reduction is completely tight, meaning the constructed adversary against CDL has both essentially the same running time and success probability as the assumed forger. To our knowledge, we are the first to exhibit such a reduction. Previously, Bellare and Dai (INDOCRYPT 2020) showed the scheme is EUF-CMA the ROM if their multi-base DL assumption holds in the underlying group. However, multi-base DL is interactive; moreover, their reduction, while tighter than the initial result of Pointcheval and Stern (EUROCRYPT 1996), still incurs a security loss that is linear in the number of the adversary’s RO queries. We justify CDL by showing it holds in two carefully chosen idealized models, which idealize different aspects of our assumption. Our quantitative bounds in these models are essentially the same as for DL, giving strong evidence that CDL is as hard DL in appropriate elliptic-curve groups groups.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Schnorr signaturestight securityECDSA function
Contact author(s)
gkcho @ umass edu
georg fuchsbauer @ tuwien ac at
amoneill @ gmail com
History
2024-09-30: approved
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},
      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.