Optimal Security Proofs for Full Domain Hash, Revisited
Optimal Security Proofs for Full Domain Hash, Revisited
复制标题
DOI：
10.1007/s00145-017-9257-9
复制
发表时间：
2012-04
影响因子：
3
通讯作者：
Saqib A. Kakvi;Eike Kiltz
中科院分区：
文献类型：
--
作者：
Saqib A. Kakvi;Eike Kiltz
RSA Full Domain Hash（RSA-FDH）是一种在随机预言模型下能抵抗选择消息攻击的数字签名方案。从RSA假设中最著名的安全性降低是非紧的，即，它失去了一个因子，其中是对手进行的签名查询的数量。它还被科龙证明（Advances in cryptology-EUROPHOTOPT 2002，Lecture notes in computer science，vol 2332. Springer，柏林，第272-287页，2002年），安全损失是最佳的，不可能得到改善。在这项工作中，我们发现了科龙的不可能性结果中的一个微妙的缺陷。具体地说，我们表明，它只持有，如果底层的陷门置换被证明。由于众所周知RSA陷门置换（对于所有实际参数）未被证明，这使得科龙的不可能性结果对于RSA-FDH没有实际意义。受此启发，我们重新审视了RSA-FDH是否存在严格的安全性证明的问题。具体地说，我们从一个更强的假设，即Cachin等人提出的Phi-Hiding假设给出了一个新的严格的安全性约简。计算机科学讲义，第1592卷。Springer，柏林，第402-414页，1999）。这证明在RSA-FDH中选择较小的参数是合理的，因为它在实践中通常使用。我们所有的结果（正面和负面）扩展到概率签名方案PSS（消息恢复）。
RSA Full Domain Hash (RSA-FDH) is a digital signature scheme, secure against chosen message attacks in the random oracle model. The best known security reduction from the RSA assumption is non-tight, i.e., it loses a factor of, whereis the number of signature queries made by the adversary. It was furthermore proven by Coron (Advances in cryptology—EUROCRYPT 2002, Lecture notes in computer science, vol 2332. Springer, Berlin, pp 272–287, 2002) that a security loss ofis optimal and cannot possibly be improved. In this work, we uncover a subtle flaw in Coron’s impossibility result. Concretely, we show that it only holds if the underlying trapdoor permutation iscertified. Since it is well known that the RSA trapdoor permutation is (for all practical parameters) not certified, this renders Coron’s impossibility result moot for RSA-FDH. Motivated by this, we revisit the question whether there is a tight security proof for RSA-FDH. Concretely, we give a new tight security reduction from a stronger assumption, the Phi-Hiding assumption introduced by Cachin et al. (Advances in Cryptology—EUROCRYPT’99. Lecture notes in computer science, vol 1592. Springer, Berlin, pp 402–414, 1999). This justifies the choice of smaller parameters in RSA-FDH, as it is commonly used in practice. All of our results (positive and negative) extend to the probabilistic signature scheme PSS (with message recovery).