Paper 2000/061

RSA-OAEP is Secure under the RSA Assumption

Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern

Abstract

Recently Victor Shoup noted that there is a gap in the widely-believed security result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed that, presumably, OAEP cannot be proven secure from the {\it one-wayness} of the underlying trapdoor permutation. This paper establishes another result on the security of OAEP. It proves that OAEP offers semantic security against adaptive chosen-ciphertext attacks, in the random oracle model, under the {\it partial-domain} one-wayness of the underlying permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since partial-domain one-wayness of the RSA function is equivalent to its (full-domain) one-wayness, it follows that the security of RSA--OAEP can actually be proven under the sole RSA assumption, although the reduction is not tight.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
David Pointcheval @ ens fr
History
2001-05-29: last of 3 revisions
2000-11-27: received
See all versions
Short URL
https://ia.cr/2000/061
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/061,
      author = {Eiichiro Fujisaki and Tatsuaki Okamoto and David Pointcheval and Jacques Stern},
      title = {RSA-OAEP is Secure under the RSA Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2000/061},
      year = {2000},
      note = {\url{https://eprint.iacr.org/2000/061}},
      url = {https://eprint.iacr.org/2000/061}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.