[FOPS01] RSA-OAEP Is Secure under the RSA Assumption

Authors: Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, Jacques Stern | Venue: CRYPTO 2001 | Source

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 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 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.

BibTeX

Copy

@Inproceedings{C:FOPS01,
  author = {Eiichiro Fujisaki and Tatsuaki Okamoto and David Pointcheval and Jacques Stern},
  title = {{RSA-OAEP} Is Secure under the {RSA} Assumption},
  pages = {260--274},
  editor = {Joe Kilian},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2001},
  volume = {2139},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~19--23},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2001},
  doi = {10.1007/3-540-44647-8_16},
}