Paper 2011/559

Instantiability of RSA-OAEP under Chosen-Plaintext Attack

Eike Kiltz, Adam O'Neill, and Adam Smith


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 ({\em i.e.}, round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in the {\em 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 {\em lossy} as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satisfies condition (1) if its hash function is $t$-wise independent for $t$ roughly 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 $\Phi$-Hiding Assumption of Cachin \emph{et al.}~(Eurocrypt 1999). This is the first {\em positive} result 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 {\em et al}.~(Eurocrypt 2000).

Note: This is the full version.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. To appear in Journal of Cryptology
RSAOAEPpadding-based encryptionlossy trapdoor functionsleftover hash lemmastandard model
Contact author(s)
amoneill @ gmail com
2016-07-04: last of 2 revisions
2011-10-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Eike Kiltz and Adam O'Neill and Adam Smith},
      title = {Instantiability of RSA-OAEP under Chosen-Plaintext Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2011/559},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.