IND-CPA ⇔ Semantic security

Equivalence · fully-black-box reduction · standard model · GM84, MRS88

Statement

A PKE scheme is IND-CPA-secure if and only if it is semantically secure, using the key-dependent, efficiently samplable formulation in which the message sampler, target function, and auxiliary state are chosen after $\mathsf{pk}$ — standard. The equivalence between indistinguishability and semantic security originates in GM84 and MRS88.

Sketch

For IND-CPA $\Rightarrow$ semantic security, $\mathcal{S}(z)$ draws an independent $m^{\prime }\leftarrow M$ and runs ${\mathcal{A}}_2(z,\mathsf{Enc}(\mathsf{pk},m^{\prime }))$. A reduction samples $m,m^{\prime }\leftarrow M$, submits $(m,m^{\prime })$ as its challenge pair, and tests the adversary’s output against $f(m)$. Both messages are valid and have the same length; the reduction’s distinguishing gap equals the semantic-security gap. No designated dummy message need belong to $\mathcal{M}$.

Conversely, run an IND-CPA adversary’s first stage after receiving $\mathsf{pk}$, choose $M$ uniform on its pair $(m_0,m_1)$, and set $f(m):=[m=m_1]$. For distinct messages, $f(m)$ is a fresh unbiased bit even given $z$, so no simulator predicts it with probability above $1/2$, whereas the ciphertext adversary can use its IND-CPA guess. On branches where $m_0=m_1$, return $1$ directly; these branches contribute no IND-CPA distinguishing gap. Flipping the IND-CPA guess if necessary, a non-negligible IND-CPA advantage gives a non-negligible prediction advantage over every simulator — standard.