The summer of OAEP

lcs Mixmaster Remailer mix at
Wed Jun 13 13:40:07 EDT 2001

These are some of the papers to be presented at Crypto 2001 in August[1]:

   A Chosen Ciphertext Attack On RSA Optimal Asymmetric Encryption
   Padding (OAEP) as Standardized In PKCS #1
   James Manger

   OAEP Reconsidered
   Victor Shoup
   RSA--OAEP is Secure Under the RSA Assumption
   Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval and Jacques
   Simplified OAEP for the RSA and Rabin Functions
   Dan Boneh

Shoup's abstract[2] reads:

   The OAEP encryption scheme was introduced by Bellare and Rogaway at
   Eurocrypt '94.  It converts any trapdoor permutation scheme into a
   public-key encryption scheme.  OAEP is widely believed to provide
   resistance against adaptive chosen ciphertext attack.  The main
   justification for this belief is a supposed proof of security in the
   random oracle model, assuming the underlying trapdoor permutation
   scheme is one way.

   This paper shows conclusively that this justification is invalid.
   First, it observes that there appears to be a non-trivial gap in
   the OAEP security proof.  Second, it proves that this gap cannot
   be filled, in the sense that there can be no standard "black box"
   security reduction for OAEP.  This is done by proving that there
   exists an oracle relative to which the general OAEP scheme is insecure.

   The paper also presents a new scheme OAEP+ along with a complete
   proof of security in the random oracle model.  OAEP+ is essentially
   just as efficient as OAEP, and even has a tighter security reduction.

   It should be stressed that these results do not imply that a particular
   instantiation of OAEP, such as RSA-OAEP, is insecure.  They simply
   undermine the original justification for its security.  In fact,
   it turns out - essentially by accident, rather than by design -
   that RSA-OAEP is secure in the random oracle model; however this
   fact relies on special algebraic properties of the RSA function,
   and not on the security of the general OAEP scheme.

The Fujisaki, et al abstract[3] reads:

   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.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list