[Resource Topic] 2000/060: OAEP Reconsidered

Welcome to the resource topic for 2000/060

OAEP Reconsidered

Authors: Victor Shoup


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

ePrint: https://eprint.iacr.org/2000/060

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .