TY - GEN

T1 - Instantiability of RSA-OAEP under chosen-plaintext attack

AU - Kiltz, Eike

AU - O'Neill, Adam

AU - Smith, Adam

N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - 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 the standard model based 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 sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satifies condition (1) if its hash function is t-wise independent for appopriate t and that RSA satisfies condition (2) under the Φ-Hiding Assumption of Cachin et al. (Eurocrypt 1999). This appears to be the first non-trivial positive result about the instantiability of RSA-OAEP. In particular, it increases our 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).

AB - 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 the standard model based 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 sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satifies condition (1) if its hash function is t-wise independent for appopriate t and that RSA satisfies condition (2) under the Φ-Hiding Assumption of Cachin et al. (Eurocrypt 1999). This appears to be the first non-trivial positive result about the instantiability of RSA-OAEP. In particular, it increases our 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).

UR - http://www.scopus.com/inward/record.url?scp=77957001343&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957001343&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14623-7_16

DO - 10.1007/978-3-642-14623-7_16

M3 - Conference contribution

AN - SCOPUS:77957001343

SN - 3642146228

SN - 9783642146220

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 295

EP - 313

BT - Advances in Cryptology - CRYPTO 2010 - 30th Annual Cryptology Conference, Proceedings

T2 - 30th Annual International Cryptology Conference, CRYPTO 2010

Y2 - 15 August 2010 through 19 August 2010

ER -