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.