Chosen-Ciphertext Security without Redundancy.
Duong Hieu Phan and David Pointcheval.
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.