Impossibility on the Provable Security of the Fiat-Shamir-Type Signatures in the Non-programmable Random Oracle Model
Impossibility on the Provable Security of the Fiat-Shamir-Type Signatures in the Non-programmable Random Oracle Model
复制标题
DOI：
10.1007/978-3-319-45871-7_23
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
Masayuki Fukumitsu;Shingo Hasegawa
中科院分区：
文献类型：
--
作者：
Masayuki Fukumitsu;Shingo Hasegawa
针对Fiat-Shamir（FS）型签名的安全性，在非可编程随机预言模型（NPROM）下给出了一些否定的间接证据。Fischlin和Fleischhacker首先通过单实例约简证明了特定FS类型签名的不可能性。在ISC 2015中，Joshumitsu和Hasegawa发现了另一个条件来证明这种不可能性，但是他们的结果需要一个强的约简条件，即密钥保持约简。本文主要研究了一种非密钥保持的约简，并从底层ID方案的安全性出发，证明了FS型签名在NPROM中不能通过序贯多实例约简被证明是安全的。我们的结果可以解释为上述两个不可能性结果的推广，应用我们的不可能性结果，通过一个顺序的多实例约简，可以证明DL假设与NPROM中Schnorr签名的安全性之间的安全不相容性.我们的不兼容性结果意味着Schnorr签名的安全性不太可能在NPROM中得到证明。
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 anon-key-preserving reduction, and then we show that an FS-type signature cannot be proven to be secure in the NPROM via asequentially multi-instance reductionfrom 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.