文档介绍：1
Chosen-Ciphertext Security
without Redundancy
Duong Hieu Phan and David Pointcheval
Ecole´ normale sup´erieure – D´ept d’informatique
45 rue d’Ulm, 75230 Paris Cedex 05, France
{,}***@
Abstract. We propose asymmetric encryption schemes for which all ci-
phertexts are valid (which means here “reachable”: the encryption func-
tion 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 A 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 work 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 A even without
the usual redundancy m
0k1 , 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.
1 Introduction
By now, the widely admitted appropriate security level for asymmetric encryp-
tion is the so-called chosen-ciphertext security (A): that is actually the
semantic security [16] against adaptive chosen-ciphertext attacks [21]. For achiev-
ing semantic security, even in the basic chosen-plaintext scenario, the encryption
algorithm must be probabilistic, which means that a given plaintext (with a fixed
public key) should be possibly encrypted in many different ways (at least 2k dif-
ferent ciphertexts if 2−k is the expected security level). This naturally implies an
expansion: the ciphertext is at least over k more bits than the plaint