Optimal asymmetric encryption -- How to encrypt with RSA

Authors: M. Bellare and P. Rogaway

Abstract: Given an arbitrary k-bit to k-bit trapdoor permutation f and a hash function, we exhibit an encryption scheme for which (i) any stringx of length slightly less than k bits can be encrypted as f(rx), where rx is a simple probabilistic encoding of x depending on the hash function; and (ii) the scheme can be proven semantically secure assuming the hash function is ``ideal.'' Moreover, a slightly enhanced scheme is shown to have the property that the adversary can create ciphertexts only of strings for which she ``knows'' the corresponding plaintexts---such a scheme is not only semantically secure but also non-malleable and secure against chosen-ciphertext attack.

Ref: Extended abstract in Advances in Cryptology - Eurocrypt 94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed, Springer-Verlag, 1995. Full paper of revised version available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


The definition of plaintext-awareness presented in this paper is too weak to imply security against chosen-ciphertext attack. An appropriate definition, together with a proof that plaintext awareness plus security against chosen plaintext attack implies security against chosen-cihpertext attack, appears in the work of Bellare, Desai, Pointcheval and Rogaway, 1998.

However, as pointed out by Victor Shoup in the paper OAEP Reconsidered, no proof that f-OAEP is plaintext aware under the new definition (or secure against chosen-ciphertext attack) has ever appeared, and, contrary to the claims of our paper, such a proof is unlikely to be possible assuming only that f is a trapdoor permutation. However, a proof has been provided, in the paper RSA-OAEP is Secure under the RSA Assumption by Fujisaki, Okamoto, Pointcheval and Stern, for the case where f is RSA, meaning that RSA-OAEP, the scheme currently adopted by various standards, is provably plaintext aware and secure against chosen-ciphertext attack in the random oracle model, assuming that the RSA function is one-way.

In a Crypto 2001 paper, James Manger points out that one must be careful in implementing OAEP, since poor implementations can give rise to attacks.

Related work and links