TY - JOUR
T1 - Black-box separations on fiat-shamir-type signatures in the non-programmable random oracle model
AU - Fukumitsu, Masayuki
AU - Hasegawa, Shingo
N1 - Funding Information:
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:
© 2018 The Institute of Electronics, Information and Communication Engineers.
PY - 2018/1
Y1 - 2018/1
N2 - 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.
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.
KW - Fiat-Shamir transformation
KW - Meta-reduction
KW - Non-programmable random oracle model
UR - http://www.scopus.com/inward/record.url?scp=85040169658&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040169658&partnerID=8YFLogxK
U2 - 10.1587/transfun.E101.A.77
DO - 10.1587/transfun.E101.A.77
M3 - Article
AN - SCOPUS:85040169658
SN - 0916-8508
VL - E101A
SP - 77
EP - 87
JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
IS - 1
ER -