IEICE TRANSACTIONS on Fundamentals
Chosen Ciphertext Security with Optimal Ciphertext Overhead
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.1 pp.22-33
- Publication Date
- 2010/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E93.A.22
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
- Public Key Cryptography
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masayuki ABE, Eike KILTZ, Tatsuaki OKAMOTO, "Chosen Ciphertext Security with Optimal Ciphertext Overhead" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 1, pp. 22-33, January 2010, doi: 10.1587/transfun.E93.A.22.
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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.22/_p
Copy
@ARTICLE{e93-a_1_22,
author={Masayuki ABE, Eike KILTZ, Tatsuaki OKAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Chosen Ciphertext Security with Optimal Ciphertext Overhead},
year={2010},
volume={E93-A},
number={1},
pages={22-33},
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 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.},
keywords={},
doi={10.1587/transfun.E93.A.22},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Chosen Ciphertext Security with Optimal Ciphertext Overhead
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 22
EP - 33
AU - Masayuki ABE
AU - Eike KILTZ
AU - Tatsuaki OKAMOTO
PY - 2010
DO - 10.1587/transfun.E93.A.22
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2010
AB - 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.
ER -
English
