Chosen Ciphertext Security with Optimal Ciphertext Overhead

Masayuki Abe; Eike Kiltz; Tatsuaki Okamoto

Paper 2008/374

Chosen Ciphertext Security with Optimal Ciphertext Overhead

Masayuki Abe, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. A short version will appear in the proceedings of Asiacrypt 2008.
Keywords: ciphertext overhead OAEP chosen ciphertext attacks
Contact author(s): abe masayuki @ lab ntt co jp
History: 2008-09-05: received
Short URL: https://ia.cr/2008/374
License: CC BY

BibTeX

@misc{cryptoeprint:2008/374,
      author = {Masayuki Abe and Eike Kiltz and Tatsuaki Okamoto},
      title = {Chosen Ciphertext Security with Optimal Ciphertext Overhead},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/374},
      year = {2008},
      url = {https://eprint.iacr.org/2008/374}
}