If Enc is a PKE(Public Key Encryption) with key generation algorithm KG and message space $M = \{0, 1\}^n$, and SE is a Symmetric Key Encryption(SKE) with key space $\{0, 1\}^n$ and message space $M' = \{0, 1\}^*$ then the hybrid encryption uses the same key generation KG, but its message space is $M' = \{0, 1\}^*$ and its encryption procedure $Enc'(p_k, m)$ picks a random symmetric key $k \gets \{0, 1\}^n$ and outputs ciphertext $(c, c')$ where $c = Enc(p_k, k)$ and $c' = SE(k, m)$. The decryption given $(c, c')$ decrypts $k$ from $c$ using the private key corresponding to pk and then decrypts $m$ from $c'$ using $k$.

If Enc is a CPA secure PKE on $M = \{0, 1\}^n$ and SE is IND secure SKE on$ M' = \{0, 1\}^*$, is Enc' CPA secure PKE on $M'$?

If Enc is CPA secure PKE and SE is CCA secure SKE, is Enc' CCA secure?

  • $\begingroup$ Not quite sure, but intuition tells me that Enc should be CCA secure (at least when considering active adversaries). $\endgroup$ Jun 2, 2019 at 12:49
  • $\begingroup$ So "Introduction to Modern Cryptography" talks a bit about hybrid encryption and KEMs. It would appear that plain CPA-secure encryption doesn't yield a CCA-secure KEM (because eg ElGamal is CPA secure but you can win the KEM-CCA game using the homomorphism) and the book requires a CCA secure KEM for CCA secure hybrid encryption. $\endgroup$
    – SEJPM
    Jun 4, 2019 at 9:32

1 Answer 1


If the KEM is only CPA-secure, then the resulting scheme might not be CCA-secure. For example, consider a CPA-secure KEM that ignores the last bit of its ciphertext. Then it is possible to modify a KEM ciphertext in a way that doesn't affect its payload, which is enough to break CCA security of the hybrid scheme.

If the KEM and DEM are both CCA-secure, then the overall hybrid scheme is also CCA-secure. This is proved formally in Section 7 of:

Cramer, Shoup: Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack

However, it is possible to have a CCA-secure hybrid encryption scheme where the KEM is (slightly) weaker than CCA secure. This was first demonstrated in:

Kurosawa, Desmedt: A New Paradigm of Hybrid Encryption Scheme

The weakened KEM security definition and composition theorem for hybrid encryption were formalized/generalized in:

Hofheinz, Kiltz: Secure Hybrid Encryption from Weakened Key Encapsulation


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.