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