Chosen-ciphertext security is a central goal in designing a secure public-key encryption scheme, and it is also important that the chosen-ciphertext security is tightly reduced to some well-established hard problem. Moreover, it is more important to have a tight reduction in the multi-user multi-challenge setting, since a tight security reduction in the single-user single-challenge setting generally does not imply a tight reduction to the multi-user multi-challenge setting. We propose the first fully tightly secure and practical public-key encryption scheme which is chosen-ciphertext secure in the multi-user multi-challenge setting in the random oracle model. The scheme is proven secure under the decisional Diffie-Hellman assumption in a pairing-free group. The ciphertext overhead of our scheme is two group elements and two exponents.

This paper shows a simple methodology for shortening a ciphertext of reproducible key encapsulation mechanisms. Specifically, it transforms a key encapsulation mechanism having OW-CCCA security and reproducibility into that of IND-CCA secure in the random oracle model whose ciphertext is shorter. Various existing chosen-ciphertext secure key encapsulation mechanisms (in the standard model) are reproducible, and thus their ciphertext can be shortened by the proposed transformation. The transformed scheme requires only one additional hashing for encryption. This property enables us to implement both the original scheme and the transformed scheme into a single chip simultaneously with small gate-size overhead. Using this chip, a sender can flexibly switch schemes to encrypt a message in a message-by-message manner. Such a use of schemes is also analyzed.

In this paper, we propose two new chosen-ciphertext (CCA) secure schemes from the computational Diffie-Hellman (CDH) and bilinear computational Diffie-Hellman (BCDH) assumptions. Our first scheme from the CDH assumption is constructed by extending Cash-Kiltz-Shoup scheme. This scheme yields the same ciphertext as that of Hanaoka-Kurosawa scheme (and thus Cramer-Shoup scheme) with cheaper computational cost for encryption. However, key size is still the same as that of Hanaoka-Kurosawa scheme. Our second scheme from the BCDH assumption is constructed by extending Boyen-Mei-Waters scheme. Though this scheme requires a stronger underlying assumption than the CDH assumption, it yields significantly shorter key size for both public and secret keys. Furthermore, ciphertext length of our second scheme is the same as that of the original Boyen-Mei-Waters scheme.

In this paper, we introduce the intermediate hashed Diffie-Hellman (IHDH) assumption which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH assumption), and is stronger than the computational DH assumption. We then present two public key encryption schemes with short ciphertexts which are both chosen-ciphertext secure under this assumption. The short-message scheme has smaller size of ciphertexts than Kurosawa-Desmedt (KD) scheme, and the long-message scheme is a KD-size scheme (with arbitrary plaintext length) which is based on a weaker assumption than the HDH assumption.

Every public-key encryption scheme has to incorporate a certain amount of randomness into its ciphertexts to provide semantic security against chosen ciphertext attacks (IND-CCA). The difference between the length of a ciphertext and the embedded message is called the ciphertext overhead. While a generic brute-force adversary running in 2t steps gives a theoretical lower bound of t bits on the ciphertext overhead for IND-CPA security, the best known IND-CCA secure schemes demand roughly 2t bits even in the random oracle model. Is the t-bit gap essential for achieving IND-CCA security? We close the gap by proposing an IND-CCA secure scheme whose ciphertext overhead matches the generic lower bound up to a small constant. Our scheme uses a variation of a four-round Feistel network in the random oracle model and hence belongs to the family of OAEP-based schemes. Maybe of independent interest is a new efficient method to encrypt long messages exceeding the length of the permutation while retaining the minimal overhead.

We propose a new security class, called plaintext simulatability, defined over the public-key encryption schemes. The notion of plaintext simulatability (denoted PS) is similar to the notion of plaintext awareness (denoted PA) defined in [3], but it is "properly" a weaker security class for public-key encryption. It is known that PA implies the class of CCA2-secure encryption (denoted IND-CCA2) but not vice versa. In most cases, PA is "unnecessarily" strong--In such cases, PA is only used to study that the public-key encryption scheme involved meets IND-CCA2, because it looks much easier to treat the membership of PA than to do "directly" the membership of IND-CCA2. We show that PS also implies IND-CCA2, while preserving such a technical advantage as well as PA. We present two novel CCA2-secure public-key encryption schemes, which should have been provided with more complicated security analyses. One is a random-oracle version of Dolev-Dwork-Naor's encryption scheme [8],[9]. Unlike the original scheme, this construction is efficient. The other is a public-key encryption scheme based on a strong pseudo-random permutation family [16] which provides the optimal ciphertext lengths for verifying the validity of ciphertexts, i.e., (ciphertext size) = (message size) + (randomness size). According to [19], such a construction remains open. Both schemes meet PS but not PA.