Duong Hieu Phan

Chosen-Ciphertext Security without Redundancy.

Abstract: We propose asymmetric encryption schemes for which all ciphertexts are valid (which means here ``reachable'': the encryption function is not only a probabilistic injection, but also a surjection). We thus introduce the Full-Domain Permutation encryption scheme which uses a random permutation. This is the first IND-CCA cryptosystem based on any trapdoor one-way permutation without redundancy, and more interestingly, the bandwidth is optimal: the ciphertext is over k more bits only than the plaintext, where 2^{-k} is the expected security level. Thereafter, we apply it into the random oracle model by instantiating the random permutation with a Feistel network construction, and thus using OAEP. Unfortunately, the usual 2-round OAEP does not seem to be provably secure, but a 3-round can be proved IND-CCA even without the usual redundancy m||0^{k_1} , under the partial-domain one-wayness of any trapdoor permutation. Although the bandwidth is not as good as in the random permutation model, absence of redundancy is quite new and interesting: many implementation risks are ruled out.

Ref: Advances in Cryptology-Proceeding of Asiacrypt '03, Lecture Notes in Computer Science Vol. 2894, pages 1-18, Springer-Verlag, 2003.

Available: pdf.