Full Text Views
142
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.
Masayuki FUKUMITSU
Hokkaido Information University
Shingo HASEGAWA
Tohoku University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Masayuki FUKUMITSU, Shingo HASEGAWA, "Impossibility on the Schnorr Signature from the One-More DL Assumption in the Non-Programmable Random Oracle Model" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 9, pp. 1163-1174, September 2021, doi: 10.1587/transfun.2020DMP0008.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020DMP0008/_p
Copy
@ARTICLE{e104-a_9_1163,
author={Masayuki FUKUMITSU, Shingo HASEGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Impossibility on the Schnorr Signature from the One-More DL Assumption in the Non-Programmable Random Oracle Model},
year={2021},
volume={E104-A},
number={9},
pages={1163-1174},
abstract={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.},
keywords={},
doi={10.1587/transfun.2020DMP0008},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Impossibility on the Schnorr Signature from the One-More DL Assumption in the Non-Programmable Random Oracle Model
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1163
EP - 1174
AU - Masayuki FUKUMITSU
AU - Shingo HASEGAWA
PY - 2021
DO - 10.1587/transfun.2020DMP0008
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2021
AB - 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.
ER -