Black-Box Separations on Fiat-Shamir-Type Signatures in the Non-Programmable Random Oracle Model
Summary :
In recent years, Fischlin and Fleischhacker showed the impossibility of proving the security of specific types of FS-type signatures, the signatures constructed by the Fiat-Shamir transformation, via a single-instance reduction in the non-programmable random oracle model (NPROM, for short). In this paper, we pose a question whether or not the impossibility of proving the security of any FS-type signature can be shown in the NPROM. For this question, we show that each FS-type signature cannot be proven to be secure via a key-preserving reduction in the NPROM from the security against the impersonation of the underlying identification scheme under the passive attack, as long as the identification scheme is secure against the impersonation under the active attack. We also show the security incompatibility between the security of some FS-type signatures in the NPROM via a single-instance key-preserving reduction and the underlying cryptographic assumptions. By applying this result to the Schnorr signature, one can prove the incompatibility between the security of the Schnorr signature in this situation and the discrete logarithm assumption, whereas Fischlin and Fleischhacker showed that such an incompatibility cannot be proven via a non-key-preserving reduction.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.1 pp.77-87
- Publication Date
- 2018/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E101.A.77
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
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, "Black-Box Separations on Fiat-Shamir-Type Signatures in the Non-Programmable Random Oracle Model" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 1, pp. 77-87, January 2018, doi: 10.1587/transfun.E101.A.77.
Abstract: In recent years, Fischlin and Fleischhacker showed the impossibility of proving the security of specific types of FS-type signatures, the signatures constructed by the Fiat-Shamir transformation, via a single-instance reduction in the non-programmable random oracle model (NPROM, for short). In this paper, we pose a question whether or not the impossibility of proving the security of any FS-type signature can be shown in the NPROM. For this question, we show that each FS-type signature cannot be proven to be secure via a key-preserving reduction in the NPROM from the security against the impersonation of the underlying identification scheme under the passive attack, as long as the identification scheme is secure against the impersonation under the active attack. We also show the security incompatibility between the security of some FS-type signatures in the NPROM via a single-instance key-preserving reduction and the underlying cryptographic assumptions. By applying this result to the Schnorr signature, one can prove the incompatibility between the security of the Schnorr signature in this situation and the discrete logarithm assumption, whereas Fischlin and Fleischhacker showed that such an incompatibility cannot be proven via a non-key-preserving reduction.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.77/_p
Copy
@ARTICLE{e101-a_1_77,
author={Masayuki FUKUMITSU, Shingo HASEGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Black-Box Separations on Fiat-Shamir-Type Signatures in the Non-Programmable Random Oracle Model},
year={2018},
volume={E101-A},
number={1},
pages={77-87},
abstract={In recent years, Fischlin and Fleischhacker showed the impossibility of proving the security of specific types of FS-type signatures, the signatures constructed by the Fiat-Shamir transformation, via a single-instance reduction in the non-programmable random oracle model (NPROM, for short). In this paper, we pose a question whether or not the impossibility of proving the security of any FS-type signature can be shown in the NPROM. For this question, we show that each FS-type signature cannot be proven to be secure via a key-preserving reduction in the NPROM from the security against the impersonation of the underlying identification scheme under the passive attack, as long as the identification scheme is secure against the impersonation under the active attack. We also show the security incompatibility between the security of some FS-type signatures in the NPROM via a single-instance key-preserving reduction and the underlying cryptographic assumptions. By applying this result to the Schnorr signature, one can prove the incompatibility between the security of the Schnorr signature in this situation and the discrete logarithm assumption, whereas Fischlin and Fleischhacker showed that such an incompatibility cannot be proven via a non-key-preserving reduction.},
keywords={},
doi={10.1587/transfun.E101.A.77},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Black-Box Separations on Fiat-Shamir-Type Signatures in the Non-Programmable Random Oracle Model
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 77
EP - 87
AU - Masayuki FUKUMITSU
AU - Shingo HASEGAWA
PY - 2018
DO - 10.1587/transfun.E101.A.77
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2018
AB - In recent years, Fischlin and Fleischhacker showed the impossibility of proving the security of specific types of FS-type signatures, the signatures constructed by the Fiat-Shamir transformation, via a single-instance reduction in the non-programmable random oracle model (NPROM, for short). In this paper, we pose a question whether or not the impossibility of proving the security of any FS-type signature can be shown in the NPROM. For this question, we show that each FS-type signature cannot be proven to be secure via a key-preserving reduction in the NPROM from the security against the impersonation of the underlying identification scheme under the passive attack, as long as the identification scheme is secure against the impersonation under the active attack. We also show the security incompatibility between the security of some FS-type signatures in the NPROM via a single-instance key-preserving reduction and the underlying cryptographic assumptions. By applying this result to the Schnorr signature, one can prove the incompatibility between the security of the Schnorr signature in this situation and the discrete logarithm assumption, whereas Fischlin and Fleischhacker showed that such an incompatibility cannot be proven via a non-key-preserving reduction.
ER -
English
