PKE ⇒ KEM

Fully-black-box reduction · standard model · folklore · security loss: tight: advantage and decryption-query count are preserved

Statement

Let $\mathsf{PKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a PKE scheme whose message space contains the key space $\mathcal{K}$, and define a KEM by letting $\mathsf{Encap}(\mathsf{pk})$ sample $k\stackrel{\$}{\leftarrow }\mathcal{K}$ and output $(\mathsf{Enc}(\mathsf{pk},k),k)$, and $\mathsf{Decap}(\mathsf{sk},c):=\mathsf{Dec}(\mathsf{sk},c)$. If $\mathsf{PKE}$ is IND-CCA-secure, the KEM is IND-CCA-secure; if $\mathsf{PKE}$ is IND-CPA-secure, the KEM is IND-CPA-secure. In both cases every KEM adversary yields a PKE adversary with the same advantage and the same number of decryption queries — folklore.

Sketch

The reduction picks independent $k_0,k_1\stackrel{\$}{\leftarrow }\mathcal{K}$, submits them as its PKE challenge pair, hands the KEM adversary $(\mathsf{pk},c^{\ast },k_0)$, and answers decapsulation queries with its decryption oracle; when $c^{\ast }$ encrypts $k_1$, the shown key $k_0$ is independent of $c^{\ast }$, which is the KEM’s random-key world. The IND-CPA case is the same reduction with no decryption oracle.

Notes

• KEMs and the KEM/DEM hybrid framework are formalized in CS03.