IND-CPA KEM + SKE ⇒ IND-CPA PKE

Fully-black-box reduction · standard model · folklore · security loss: additive: twice the KEM CPA advantage plus the DEM one-time advantage

Statement

The KEM-DEM hybrid of an IND-CPA KEM and a one-time IND-CPA SKE scheme, $\mathsf{Enc}(\mathsf{pk},m):=(c_1,\mathsf{SKE}.\mathsf{Enc}(k,m))$ for $(c_1,k)\leftarrow \mathsf{Encap}(\mathsf{pk})$, is IND-CPA secure — folklore.

Sketch

Replace the encapsulated key by an independent uniform key, indistinguishable by KEM IND-CPA security; the challenge is then a one-time encryption under a uniform key.

Notes

• With the one-time pad as DEM, which needs no assumption, an IND-CPA KEM alone gives IND-CPA PKE for messages of the key’s length — folklore.