Instantiability of RSA-OAEP Under Chosen-Plaintext Attack
Instantiability of RSA-OAEP Under Chosen-Plaintext Attack
复制标题
DOI：
10.1007/s00145-016-9238-4
复制
发表时间：
2010-08
影响因子：
3
通讯作者：
Eike Kiltz;Adam O'Neill;Adam D. Smith
中科院分区：
文献类型：
--
作者：
Eike Kiltz;Adam O'Neill;Adam D. Smith
我们证明了Bellare和Rogaway（Eurocrypt 1994）的广泛部署的RSA-OAEP加密方案，该方案将RSA与两轮底层Feistel网络相结合，该网络的散列（即，Round）函数被建模为随机预言机，满足标准模型中基于RSA和Hash函数简单、非交互、非依赖假设的选择明文攻击（IND-CPA）下的不可破译性。为了证明这一点，我们首先给出了一个更一般的概念，称为“基于填充”的加密，说这样的方案是IND-CPA，如果（1）它的底层填充变换满足一个“愚弄”条件，对小范围的加密器在一类高熵输入分布，和（2）它的陷门置换是由Peikert和沃茨定义的（STOC 2008）。然后证明了如果第一轮OAEP的散列函数与允许的消息长度成正比，则第一轮OAEP满足条件（1）。我们澄清，这个结果需要哈希函数被加密，并且其密钥被包含在RSA-OAEP的公钥中。在Cachin等人（Eurocrypt 1999）的隐藏假设下，我们还证明了RSA满足条件（2）。这是RSA-OAEP实例化的第一个积极结果。特别是，它增加了选择明文攻击不太可能被发现对该计划的信心。相比之下，科龙等人（Eurocrypt 2000年）证明，PKCS #1 v1.5中的RSA-OAEP前身易受此类攻击。
We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash ( i.e., round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in thestandard modelbased on simple, non-interactive, and non-interdependent assumptions on RSA and the hash functions. To prove this, we first give a result on a more general notion called “padding-based” encryption, saying that such a scheme is IND-CPA if (1) its underlying padding transform satisfies a “fooling" condition against small-range distinguishers on a class of high-entropy input distributions, and (2) its trapdoor permutation is sufficientlylossyas defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satisfies condition (1) if its hash function ist-wise independent fortroughly proportional to the allowed message length. We clarify that this result requires the hash function to be keyed, and for its key to be included in the public key of RSA-OAEP. We also show that RSA satisfies condition (2) under the-Hiding Assumption of Cachin et al. (Eurocrypt 1999). This is the firstpositiveresult about the instantiability of RSA-OAEP. In particular, it increases confidence that chosen-plaintext attacks are unlikely to be found against the scheme. In contrast, RSA-OAEP’s predecessor in PKCS #1 v1.5 was shown to be vulnerable to such attacks by Coron et al. (Eurocrypt 2000).