Cryptology ePrint Archive: Report 2008/375
A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks
Jan Camenisch and Nishanth Chandran and Victor Shoup
Abstract: Recently, at Crypto 2008, Boneh, Halevi, Hamburg, and Ostrovsky (BHHO)
solved the long-standing open problem of ``circular encryption,''
by
presenting a public key encryption scheme
and proving that it
is semantically secure against key dependent chosen plaintext attack (KDM-CPA security)
under standard assumptions (and without resorting to random oracles).
However, they left as an open problem that of designing
an encryption scheme that \emph{simultaneously} provides security
against both key dependent chosen plaintext \emph{and} adaptive chosen ciphertext
attack (KDM-CCA2 security).
In this paper, we solve this problem.
First, we show that by applying the Naor-Yung ``double encryption''
paradigm, one can combine
any KDM-CPA secure scheme with any (ordinary) CCA2 secure scheme,
along with an appropriate non-interactive zero-knowledge proof,
to obtain a KDM-CCA2 secure scheme.
Second, we give a concrete instantiation that makes use
the above KDM-CPA secure scheme of BHHO,
along with a generalization of the Cramer-Shoup CCA2 secure
encryption scheme,
and recently developed
pairing-based NIZK proof systems.
This instantiation increases the complexity of the BHHO
scheme by just a small constant factor.
Category / Keywords: public key encryption, key dependent messages, circular encryption, chosen ciphertext attack
Publication Info: To appear, Eurocrypt 2009
Date: received 3 Sep 2008, last revised 16 Jan 2009
Contact author: shoup at cs nyu edu
Available format(s): PDF | BibTeX Citation
Version: 20090116:120956 (All versions of this report)
Short URL: ia.cr/2008/375
[ Cryptology ePrint archive ]