### Impossibility on the Schnorr Signature from the One-more DL Assumption in the Non-programmable Random Oracle Model

Masayuki Fukumitsu and Shingo Hasegawa

##### Abstract

In the random oracle model (ROM), it is provable from the DL assumption, whereas there is negative circumstantial evidence in the standard model. Fleischhacker, Jager, and Schröder showed that the tight security of the Schnorr signature is unprovable from a strong cryptographic assumption, such as the One-More DL (OM-DL) assumption and the computational and decisional Diffie-Hellman assumption, in the ROM via a generic reduction as long as the underlying cryptographic assumption holds. However, it remains open whether or not the impossibility of the provable security of the Schnorr signature from a strong assumption via a non-tight and reasonable reduction. In this paper, we show that the security of the Schnorr signature is unprovable from the OM-DL assumption in the non-programmable ROM as long as the OM-DL assumption holds. Our impossibility result is proven via a non-tight Turing reduction.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.ProvSec2017
DOI
10.1007/978-3-319-68637-0_12
Keywords
digital signaturesdiscrete logarithm problem
Contact author(s)
fukumitsu @ do-johodai ac jp
shingo hasegawa b7 @ tohoku ac jp
History
2021-06-08: revised
See all versions
Short URL
https://ia.cr/2020/1234

CC BY

BibTeX

@misc{cryptoeprint:2020/1234,
author = {Masayuki Fukumitsu and Shingo Hasegawa},
title = {Impossibility on the Schnorr Signature from the One-more DL Assumption in the Non-programmable Random Oracle Model},
howpublished = {Cryptology ePrint Archive, Paper 2020/1234},
year = {2020},
doi = {10.1007/978-3-319-68637-0_12},
note = {\url{https://eprint.iacr.org/2020/1234}},
url = {https://eprint.iacr.org/2020/1234}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.