TY - GEN
T1 - Impossibility on the provable security of the Fiat-Shamir-type signatures in the non-programmable random oracle model
AU - Fukumitsu, Masayuki
AU - Hasegawa, Shingo
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2016.
PY - 2016
Y1 - 2016
N2 - On the security of Fiat-Shamir (FS) type signatures, some negative circumstantial evidences were given in the non-programmable random oracle model (NPROM). Fischlin and Fleischhacker first showed an impossibility for specific FS-type signatures via a single-instance reduction. In ISC 2015, Fukumitsu and Hasegawa found another conditions to prove such an impossibility, however their result requires a strong condition on a reduction, i.e. a key-preserving reduction. In this paper, we focus on a non-key-preserving reduction, and then we show that an FS-type signature cannot be proven to be secure in the NPROM via a sequentially multi-instance reduction from the security of the underlying ID scheme. Our result can be interpreted as a generalization of the two impossibility results introduced above. By applying our impossibility result, the security incompatibility between the DL assumption and the security of the Schnorr signature in the NPROM via a sequentially multi-instance reduction can be shown. Our incompatibility result means that the security of the Schnorr signature is not likely to be proven in the NPROM.
AB - On the security of Fiat-Shamir (FS) type signatures, some negative circumstantial evidences were given in the non-programmable random oracle model (NPROM). Fischlin and Fleischhacker first showed an impossibility for specific FS-type signatures via a single-instance reduction. In ISC 2015, Fukumitsu and Hasegawa found another conditions to prove such an impossibility, however their result requires a strong condition on a reduction, i.e. a key-preserving reduction. In this paper, we focus on a non-key-preserving reduction, and then we show that an FS-type signature cannot be proven to be secure in the NPROM via a sequentially multi-instance reduction from the security of the underlying ID scheme. Our result can be interpreted as a generalization of the two impossibility results introduced above. By applying our impossibility result, the security incompatibility between the DL assumption and the security of the Schnorr signature in the NPROM via a sequentially multi-instance reduction can be shown. Our incompatibility result means that the security of the Schnorr signature is not likely to be proven in the NPROM.
KW - Fiat-Shamir transformation
KW - Meta-reduction
KW - Nonprogrammable random oracle model
KW - Schnorr signature
KW - Static message attack
UR - http://www.scopus.com/inward/record.url?scp=84988377972&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84988377972&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-45871-7_23
DO - 10.1007/978-3-319-45871-7_23
M3 - Conference contribution
AN - SCOPUS:84988377972
SN - 9783319458700
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 389
EP - 407
BT - Information Security - 19th International Conference, ISC 2016, Proceedings
A2 - Bishop, Matt
A2 - Nascimento, Anderson C.A.
PB - Springer Verlag
T2 - 19th Annual International Conference on Information Security, ISC 2016
Y2 - 3 September 2016 through 6 September 2016
ER -