IND$-CPA Security ⇒ CPA Security

Fully-black-box reduction · standard model · folklore · security loss: factor 2

Statement

Every IND$-CPA-secure SKE scheme $\mathsf{SKE}$ is CPA-secure — folklore. For every CPA adversary $\mathcal{A}$ there are IND$-CPA adversaries ${\mathcal{B}}_0,{\mathcal{B}}_1$, each running $\mathcal{A}$ once, with

$${\mathbf{Adv}}_{\mathsf{SKE},\mathcal{A}}^{\mathrm{cpa}}(\lambda )\le {\mathbf{Adv}}_{\mathsf{SKE},{\mathcal{B}}_0}^{ind\$\text{-}\mathrm{cpa}}(\lambda )+{\mathbf{Adv}}_{\mathsf{SKE},{\mathcal{B}}_1}^{ind\$\text{-}\mathrm{cpa}}(\lambda ).$$

Sketch

${\mathcal{B}}_c$ answers each query $(m_0,m_1)$ of $\mathcal{A}$ with its own oracle on $m_c$ and outputs $\mathcal{A}$‘s guess: with the real oracle it simulates ${\mathcal{O}}_c$, with the uniform oracle an oracle independent of $b$. The triangle inequality over the hybrids ${\mathcal{O}}_0$, uniform, ${\mathcal{O}}_1$ gives the bound.

Notes

• The converse fails for the identity construction: appending a constant bit to every ciphertext preserves CPA security and breaks IND$-CPA security (CPA ⇏ IND$-CPA) — folklore.