IND-CCA KEM + CCA-secure SKE ⇒ IND-CCA PKE

Fully-black-box reduction · standard model · CS03 · security loss: additive: twice the KEM CCA advantage plus twice the KEM bad-key-pair probability plus the DEM one-time CCA advantage

Statement

The KEM-DEM hybrid builds PKE from a KEM and a one-time-secure SKE (the DEM): $\mathsf{Enc}(\mathsf{pk},m)$ runs $(c_1,k)\leftarrow \mathsf{Encap}(\mathsf{pk})$ and $c_2\leftarrow \mathsf{SKE}.\mathsf{Enc}(k,m)$ and outputs $(c_1,c_2)$; $\mathsf{Dec}(\mathsf{sk},(c_1,c_2))$ outputs $\mathsf{SKE}.\mathsf{Dec}(\mathsf{Decap}(\mathsf{sk},c_1),c_2)$. If the KEM is IND-CCA secure and the DEM is one-time IND-CCA secure (e.g. encrypt-then-MAC), the hybrid is IND-CCA secure — CS03, Theorem 5. A CCA-secure SKE scheme becomes a one-time IND-CCA DEM by using the encapsulated key as the coins of $\mathsf{SKE}.\mathsf{KeyGen}$ — standard.

Sketch

First replace the encapsulated key $k^{\ast }$ by an independent uniform key, answering decryption queries $(c_1,c_2)$ with $c_1\ne c_1^{\ast }$ via $\mathsf{Decap}$ — indistinguishable by KEM IND-CCA security. Then the challenge and every query $(c_1^{\ast },c_2)$ with $c_2\ne c_2^{\ast }$ are handled under that uniform key, which is exactly a one-time IND-CCA attack on the DEM; this hop is where the DEM’s decryption oracle is needed.

Notes

• The IND-CPA analogue is IND-CPA KEM + SKE ⇒ IND-CPA PKE — folklore.
• A one-time IND-CPA DEM does not suffice for an IND-CCA hybrid, even with an IND-CCA KEM: the one-time pad is one-time IND-CPA secure but malleable — CS03, Remark 13; HHK10 study systematically which combinations of KEM and DEM security notions suffice.
• Efficiency: the public-key work is one encapsulation per message, whatever its length, and the rest is symmetric encryption — standard.