TY - GEN
T1 - Impossibility of the provable security of the schnorr signature from the one-more DL assumption in the non-programmable random oracle model
AU - Fukumitsu, Masayuki
AU - Hasegawa, Shingo
N1 - Funding Information:
Acknowledgment. We would like to thank anonymous reviewers for their valuable comments and suggestions. A part of this work is supported by JSPS KAKENHI Grant Number 15K16001.
Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
N2 - The security of the Schnorr signature was widely discussed. In the random oracle model (ROM), it is provable from the DL assumption, whereas there is a 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 and non-restricted Turing reduction.
AB - The security of the Schnorr signature was widely discussed. In the random oracle model (ROM), it is provable from the DL assumption, whereas there is a 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 and non-restricted Turing reduction.
KW - Impossibility result
KW - Non-programmable random oracle model
KW - One-more DL assumption
KW - Schnorr signature
UR - http://www.scopus.com/inward/record.url?scp=85032665126&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032665126&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-68637-0_12
DO - 10.1007/978-3-319-68637-0_12
M3 - Conference contribution
AN - SCOPUS:85032665126
SN - 9783319686363
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 201
EP - 218
BT - Provable Security - 11th International Conference, ProvSec 2017, Proceedings
A2 - Okamoto, Tatsuaki
A2 - Yu, Yong
A2 - Au, Man Ho
A2 - Li, Yannan
PB - Springer Verlag
T2 - 11th International Conference on Provable Security, ProvSec 2017
Y2 - 23 October 2017 through 25 October 2017
ER -