OAEP 3-Round: A Generic and Secure Asymmetric Encryption Padding.
Duong Hieu Phan and David Pointcheval.
Abstract:
The OAEP construction is already 10 years old and well-established in
many practical applications. But after some doubts about its actual security level, four
years ago, the first effcient and provably IND-CCA1 secure encryption padding was
formally and fully proven to achieve the expected IND-CCA2 security level, when used
with any trapdoor permutation. Even if it requires the partial-domain one-wayness
of the permutation, for the main application (with the RSA permutation family) this
intractability assumption is equivalent to the classical (full-domain) one-wayness, but
at the cost of an extra quadratic-time reduction. The security proof which was already
not very tight to the RSA problem is thus much worse.
However, the practical optimality of the OAEP construction is two-fold, hence its at-
tractivity: from the effciency point of view because of two extra hashings only, and from
the length point of view since the ciphertext has a minimal bit-length (the encoding of
an image by the permutation.) But the bandwidth (or the ratio ciphertext/plaintext) is
not optimal because of the randomness (required by the semantic security) and the re-
dundancy (required by the plaintext-awareness, the sole way known to provide effcient
CCA2 schemes.)
At last Asiacrypt '03, the latter intuition had been broken by exhibiting the first IND-
CCA2 secure encryption schemes without redundancy, and namely without achieving
plaintext-awareness, while in the random-oracle model: the OAEP 3-round construc-
tion. But this result achieved only similar practical properties as the original OAEP
construction: the security relies on the partial-domain one-wayness, and needs a trap-
door permutation, which limits the application to RSA, with still a quite bad reduction.
This paper improves this result: first we show the OAEP 3-round actually relies on the
(full-domain) one-wayness of the permutation (which improves the reduction), then we
extend the application to a larger class of encryption primitives (including ElGamal,
Paillier, etc.) The extended security result is still in the random-oracle model, and in
a relaxed CCA2 model (which lies between the original one and the replayable CCA
scenario.)
Ref: Advances in Cryptology-Proceeding of Asiacrypt '04, Lecture Notes in Computer Science Vol. 3329, pages 63-77, Springer-Verlag, 2004.
Available: pdf.