TY - GEN
T1 - One-more assumptions do not help fiat-shamir-type signature schemes in NPROM
AU - Fukumitsu, Masayuki
AU - Hasegawa, Shingo
N1 - Funding Information:
Acknowledgements. We would like to thank anonymous reviewers for their valuable comments and suggestions. A part of this work is supported by JSPS KAKENHI Grant Numbers 18K11288 and 19K20272.
Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - On the Fiat-Shamir-type signature schemes, there are several impossibility results concerning their provable security. Most of these impossibility results employ the non-programmable random oracle model (NPROM), and to the best of our knowledge, all impossibilities deal with the security reductions from the non-interactive cryptographic assumptions except for the result on the security of Schnorr signature scheme from the One-More DL (OM-DL) assumption in ProvSec2017. In this paper, we extend the impossibility result above concerning Schnorr signature scheme and the OM-DL assumption to a wider class of the Fiat-Shamir-type signature schemes, and aim to find out the conditions so that such impossibility results hold. We show that a specific class of the Fiat-Shamir-type signature schemes, including Schnorr signature scheme, cannot be proven to be euf-cma secure in NPROM from the generalized One-More cryptographic assumptions. This is just a generalization of the impossibility concerning Schnorr signature scheme and the OM-DL assumption. Our result also suggests that for some Fiat-Shamir-type signature schemes, which is not covered by our impossibility (e.g. the RSA-based schemes), there may exist a successful security proof in NPROM from the interactive cryptographic assumption.
AB - On the Fiat-Shamir-type signature schemes, there are several impossibility results concerning their provable security. Most of these impossibility results employ the non-programmable random oracle model (NPROM), and to the best of our knowledge, all impossibilities deal with the security reductions from the non-interactive cryptographic assumptions except for the result on the security of Schnorr signature scheme from the One-More DL (OM-DL) assumption in ProvSec2017. In this paper, we extend the impossibility result above concerning Schnorr signature scheme and the OM-DL assumption to a wider class of the Fiat-Shamir-type signature schemes, and aim to find out the conditions so that such impossibility results hold. We show that a specific class of the Fiat-Shamir-type signature schemes, including Schnorr signature scheme, cannot be proven to be euf-cma secure in NPROM from the generalized One-More cryptographic assumptions. This is just a generalization of the impossibility concerning Schnorr signature scheme and the OM-DL assumption. Our result also suggests that for some Fiat-Shamir-type signature schemes, which is not covered by our impossibility (e.g. the RSA-based schemes), there may exist a successful security proof in NPROM from the interactive cryptographic assumption.
KW - Fiat-Shamir-type signature schemes
KW - Impossibility result
KW - Non-programmable random oracle model
KW - One-more cryptographic assumptions
KW - Provable security
UR - http://www.scopus.com/inward/record.url?scp=85081180516&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85081180516&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-40186-3_25
DO - 10.1007/978-3-030-40186-3_25
M3 - Conference contribution
AN - SCOPUS:85081180516
SN - 9783030401856
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 586
EP - 609
BT - Topics in Cryptology – CT-RSA 2020 - The Cryptographers Track at the RSA Conference 2020, Proceedings
A2 - Jarecki, Stanislaw
PB - Springer
T2 - Cryptographers Track at the RSA Conference, CT-RSA 2020
Y2 - 24 February 2020 through 28 February 2020
ER -