One-More Assumptions Do Not Help Fiat-Shamir-type Signature Schemes in NPROM
One-More Assumptions Do Not Help Fiat-Shamir-type Signature Schemes in NPROM
复制标题
DOI：
10.1007/978-3-030-40186-3_25
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Masayuki Fukumitsu;Shingo Hasegawa
中科院分区：
文献类型：
--
作者：
Masayuki Fukumitsu;Shingo Hasegawa
关于Fiat-Shamir-型签名方案，关于它们的可证安全性，有几个不可能的结果。这些不可能的结果大多使用不可编程的随机预言模型(NPROM)，据我们所知，除了ProvSec2017中关于Schnorr签名方案安全性的一个-多个DL(OM-DL)假设的结果外，所有的不可能都涉及非交互密码假设的安全性降低。本文将上面关于Schnorr签名方案和OM-DL假设的不可能结果推广到更广泛的一类Fiat-Shamir类型签名方案，目的是找出使这种不可能结果成立的条件。我们证明了一类特殊的Fiat-Shamir类签名方案，包括Schnorr签名方案，在广义的一个或多个密码学假设下，不能在NPROM中证明是uf-CMA安全的。这只是Schnorr签名方案的不可能性和OM-DL假设的推广。我们的结果还表明，对于一些我们不可能覆盖的Fiat-Shamir签名方案(例如基于RSA的签名方案)，在交互密码假设下，NPROM中可能存在一个成功的安全证明。
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 thegeneralizedOne-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.