KEM ⇒ KE

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

Statement

A KEM $(\mathsf{KeyGen},\mathsf{Encap},\mathsf{Decap})$ yields a two-message key exchange over an authenticated channel: the receiver samples $(\mathsf{pk},\mathsf{sk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$ and sends $\mathsf{pk}$; the sender runs $(c,k)\leftarrow \mathsf{Encap}(\mathsf{pk})$, sends $c$, and outputs $k$; the receiver outputs $\mathsf{Decap}(\mathsf{sk},c)$. If the KEM is IND-CPA-secure, the protocol is secure against eavesdroppers — folklore.

Sketch

The eavesdropper’s input, the transcript $(\mathsf{pk},c)$ with the real or a uniform key, is the IND-CPA KEM challenge $(\mathsf{pk},c^{\ast },k_b)$, so a key-exchange distinguisher is forwarded unchanged as a KEM distinguisher.

Notes

• A bare KEM gives unauthenticated key exchange, not AKE, which requires mutual authentication — folklore.