Paper 2024/1528
Schnorr Signatures are Tightly Secure in the ROM under a Non-interactive Assumption
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, a new, non-interactive and falsifiable variant of the discrete-log (DL) problem we introduce, holds in the underlying group. Notably, our reduction is tight, meaning the constructed adversary against CDL has essentially the same running time and success probability as the assumed forger. This is crucial for justifying the size of the underlying group 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 et al., EUROCRYPT 2020). We justify CDL by showing it holds in two carefully-chosen idealized models that idealize different aspects of it. Namely, we show that CDL is as hard as DL in these models.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Schnorr signaturestight securityECDSA conversion function
- Contact author(s)
-
gkcho @ umass edu
georg fuchsbauer @ tuwien ac at
amoneill @ gmail com - History
- 2024-11-14: last of 2 revisions
- 2024-09-29: received
- See all versions
- Short URL
- https://ia.cr/2024/1528
- License
-
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}
}
