Cryptology ePrint Archive: Report 2020/1234

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\"{o}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.

Category / Keywords: public-key cryptography / digital signatures, discrete logarithm problem

Original Publication (with major differences): ProvSec2017

Date: received 6 Oct 2020, last revised 7 Oct 2020

Contact author: fukumitsu at do-johodai ac jp,shingo hasegawa b7@tohoku ac jp

Available format(s): PDF | BibTeX Citation

Version: 20201009:113114 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]