**A Note on Bounded Chosen Ciphertext Security from Black-box Semantical Security**

*Ronald Cramer and 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 well-known 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 two-fold.

First, we show a simple, efficient black-box 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 key-generation. 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 black-box 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 black-box result one can hope for. Second, we give a non-blackbox 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 black-box construction. This latter scheme, however, is only of theoretical interest as it uses general NP-reductions, and our blackbox construction is in fact much more practical.

**Category / Keywords: **foundations / Black-box construction, chosen-ciphertext security

**Date: **received 6 Nov 2006, last revised 12 Nov 2006

**Contact author: **kiltz at cwi nl

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

**Version: **20061112:194937 (All versions of this report)

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

[ Cryptology ePrint archive ]