Paper 2006/265

Some (in)sufficient conditions for secure hybrid encryption.

Javier Herranz, Dennis Hofheinz, and Eike Kiltz


The KEM/DEM hybrid encryption paradigm combines the efficiency and large message space of secret key encryption with the advantages of public key cryptography. Due to its simplicity and flexibility, the approach has ever since gained increased popularity and has been successfully adapted in encryption standards. In hybrid public key encryption (PKE), first a key encapsulation mechanism (KEM) is used to fix a random session key that is then fed into a highly efficient data encapsulation mechanism (DEM) to encrypt the actual message. A composition theorem states that if both the KEM and the DEM have the highest level of security (i.e. security against chosen-ciphertext attacks), then so does the hybrid PKE scheme. It is not known if these strong security requirements on the KEM and DEM are also neccessary, nor if such general composition theorems exist for weaker levels of security. In this work we study neccessary and sufficient conditions on the security of the KEM and the DEM in order to guarantee a hybrid PKE scheme with a certain given level of security. More precisely, using nine different security notions for KEMs, ten for DEMs, and six for PKE schemes we completely characterize which combinations lead to a secure hybrid PKE scheme (by proving a composition theorem) and which do not (by providing counterexamples). Furthermore, as an independent result, we revisit and extend prior work on the relation among security notions for KEMs and DEMs.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Information and Computation, Volume 208, Issue 11, pp. 1243-1257, 2010
key encapsulation mechanismdata encapsulation mechanismhybrid encryption
Contact author(s)
kiltz @ cwi nl
2010-11-24: revised
2006-08-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Javier Herranz and Dennis Hofheinz and Eike Kiltz},
      title = {Some (in)sufficient conditions for secure hybrid encryption.},
      howpublished = {Cryptology ePrint Archive, Paper 2006/265},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.