Black-Box Separations on Fiat-Shamir-Type Signatures in the Non-Programmable Random Oracle Model

Masayuki FUKUMITSU; Shingo HASEGAWA

doi:10.1587/transfun.E101.A.77

Black-Box Separations on Fiat-Shamir-Type Signatures in the Non-Programmable Random Oracle Model

Masayuki FUKUMITSU, Shingo HASEGAWA

Full Text Views

0

Share
Cite this

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

Fiat-Shamir transformation, non-programmable random oracle model, meta-reduction

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://globals.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 -