**Chosen Ciphertext Security with Optimal Ciphertext Overhead**

*Masayuki Abe and Eike Kiltz and Tatsuaki Okamoto*

**Abstract: **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 $2^t$ 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 $2 t$ 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.

**Category / Keywords: **public-key cryptography / ciphertext overhead, OAEP, chosen ciphertext attacks

**Publication Info: **A short version will appear in the proceedings of Asiacrypt 2008.

**Date: **received 2 Sep 2008, last revised 2 Sep 2008

**Contact author: **abe masayuki at lab ntt co jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20080905:092026 (All versions of this report)

**Short URL: **ia.cr/2008/374

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]