No fixed-construction reduction from CPA security to CCA1 security

Conditional · against fixed-construction reductions · assuming CPA Security · BDPR98

Statement

If an IND-CPA-secure PKE scheme exists, then there is a PKE scheme that is IND-CPA-secure but not IND-CCA1-secure, so the identity map is no reduction from CPA to CCA1 security — BDPR98.

Sketch

Given an IND-CPA-secure $\mathsf{PKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$, let ${\mathsf{Enc}}^{\prime }(\mathsf{pk},m)=0\Vert \mathsf{Enc}(\mathsf{pk},m)$ and ${\mathsf{Dec}}^{\prime }(\mathsf{sk},0\Vert c)=\mathsf{Dec}(\mathsf{sk},c)$, and let ${\mathsf{Dec}}^{\prime }$ return $\mathsf{sk}$ on the designated ciphertext $1$, which ${\mathsf{Enc}}^{\prime }$ never outputs. The CPA game never calls ${\mathsf{Dec}}^{\prime }$, so ${\mathsf{PKE}}^{\prime }$ is IND-CPA-secure; a CCA1 adversary queries $1$ in Phase 1, receives $\mathsf{sk}$, and decrypts $c^{\ast }$ — standard.

Notes

• The converse holds for every scheme: CCA1 security ⇒ CPA security — folklore.