IEICE TRANSACTIONS on Fundamentals
Open Access
Impossibility on the Schnorr Signature from the One-More DL Assumption in the Non-Programmable Random Oracle Model
-
Full Text Views
64
- 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
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
