PKE ⇒ KE

Fully-black-box reduction · standard model · folklore · security loss: tight: the eavesdropper’s advantage equals the CPA advantage

Statement

Let $\mathsf{PKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a CPA-secure PKE scheme with message space $\mathcal{M}$, and $\mathcal{K}\subseteq \mathcal{M}$ a key space. The two-message protocol in which $B$ sends $\mathsf{pk}$ for $(\mathsf{sk},\mathsf{pk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$, $A$ replies with $c\leftarrow \mathsf{Enc}(\mathsf{pk},k)$ for $k\stackrel{\$}{\leftarrow }\mathcal{K}$ and outputs $k$, and $B$ outputs $\mathsf{Dec}(\mathsf{sk},c)$, is a key exchange secure against eavesdroppers — folklore.

Sketch

The reduction submits independent uniform $k_0,k_1\stackrel{\$}{\leftarrow }\mathcal{K}$ as its CPA challenge pair, presents $(\mathsf{pk},c^{\ast })$ as the transcript with $k_0$ as the candidate key, and outputs $0$ iff the eavesdropper declares $k_0$ real: when $c^{\ast }$ encrypts $k_1$, $k_0$ is independent of the transcript.