##
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(r_{x}), where
r_{x} 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).

## Updates

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.