A new and improved paradigm for hybrid encryption secure against chosen-ciphertext attack

Yvo Desmedt, Rosario Gennaro, Kaoru Kurosawa, Victor Shoup

Research output: Contribution to journalArticlepeer-review


We present a new encryption scheme which is secure against adaptive chosen-ciphertext attack (or CCA2-secure) in the standard model (i.e., without the use of random oracle). Our scheme is a hybrid one: it first uses a public-key step (the Key Encapsulation Module or KEM) to encrypt a random key, which is then used to encrypt the actual message using a symmetric encryption algorithm (the Data Encapsulation Module or DEM). Our scheme is a modification of the hybrid scheme presented by Shoup in (Euro-Crypt'97, Springer LNCS, vol. 1233, pp. 256-266, 1997) (based on the Cramer-Shoup scheme in CRYPTO'98, Springer LNCS, vol. 1462, pp. 13-25, 1998). Its major practical advantage is that it saves the computation of one exponentiation and produces shorter ciphertexts. This efficiency improvement is the result of a surprising observation: previous hybrid schemes were proven secure by proving that both the KEM and the DEM were CCA2-secure. On the other hand, our KEM is not CCA2-secure, yet the whole scheme is, assuming the Decisional Diffie-Hellman (DDH) Assumption. Finally we generalize our new scheme in two ways: (i) we show that security holds also if we use projective hash families (as the original Cramer-Shoup), and (ii) we show that in the random oracle model we can prove security under the weaker Computational Diffie-Hellman (CDH) Assumption.

Original languageEnglish (US)
Pages (from-to)91-120
Number of pages30
JournalJournal of Cryptology
Issue number1
StatePublished - Jan 2010


  • Chosen ciphertext security
  • Projective hash proofs
  • Public key encryption

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'A new and improved paradigm for hybrid encryption secure against chosen-ciphertext attack'. Together they form a unique fingerprint.

Cite this