Paper 2006/391
A Note on Bounded Chosen Ciphertext Security from Blackbox Semantical Security
Ronald Cramer, Dennis Hofheinz, and Eike Kiltz
Abstract
Designing public key encryption schemes withstanding chosen ciphertext attacks, which is the highest security level for such schemes, is generally perceived as a delicate and intricate task, and for good reason. In the standard model, there are essentially three wellknown but quite involved approaches. This state of affairs is to be contrasted with the situation for semantically secure encryption schemes, a much weaker security notion that only guarantees security in the absence of active attack but that appears to be much easier to fulfill, both conceptually and practically. Thus, the boundary between passive attack and active attack seems to make up the dividing line between which security levels are relatively easily achieved and which are not. Our contributions are twofold. First, we show a simple, efficient blackbox construction of a public key encryption scheme withstanding chosen ciphertext attack from any given semantically secure one. Our scheme is $q$bounded in the sense that security is only guaranteed if the adversary makes at most $q$ adaptive chosen ciphertext queries. Here, $q$ is an arbitrary polynomial that is fixed in advance in the keygeneration. Our work thus shows that whether or not the number of active, adversarial queries is known in advance is the dividing line, and not passive versus active attack. In recent work, Gertner, Malkin and Myers show that such blackbox reductions are impossible if instead $q$ is a polynomial that only depends on the adversary. Thus, in a sense, our result appears to be the best blackbox result one can hope for. Second, we give a nonblackbox reduction from bounded chosen ciphertext security to semantic security where the length of the public/secret keys and ciphertexts drops from quadratic to linear in $q$, compared to our blackbox construction. This latter scheme, however, is only of theoretical interest as it uses general NPreductions, and our blackbox construction is in fact much more practical.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Blackbox constructionchosenciphertext security
 Contact author(s)
 kiltz @ cwi nl
 History
 20061112: revised
 20061112: received
 See all versions
 Short URL
 https://ia.cr/2006/391
 License

CC BY
BibTeX
@misc{cryptoeprint:2006/391, author = {Ronald Cramer and Dennis Hofheinz and Eike Kiltz}, title = {A Note on Bounded Chosen Ciphertext Security from Blackbox Semantical Security}, howpublished = {Cryptology ePrint Archive, Paper 2006/391}, year = {2006}, note = {\url{https://eprint.iacr.org/2006/391}}, url = {https://eprint.iacr.org/2006/391} }