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