The search functionality is under construction.
The search functionality is under construction.

Open Access
Impossibility on the Schnorr Signature from the One-More DL Assumption in the Non-Programmable Random Oracle Model

Masayuki FUKUMITSU, Shingo HASEGAWA

  • Full Text Views

    142

  • Cite this
  • Free PDF (766.1KB)

Summary :

The Schnorr signature is one of the representative signature schemes and its security was widely discussed. 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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1163-1174
Publication Date
2021/09/01
Publicized
2021/03/08
Online ISSN
1745-1337
DOI
10.1587/transfun.2020DMP0008
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category
Cryptography and Information Security

Authors

Masayuki FUKUMITSU
  Hokkaido Information University
Shingo HASEGAWA
  Tohoku University

Keyword