CPA-secure PKE + NIZK ⇒ CCA1-secure PKE (Naor–Yung)

Free reduction · standard model · NY90 · security loss: additive: twice the CPA advantage plus the NIZK zero-knowledge and soundness advantages

Statement

A perfectly correct IND-CPA-secure PKE scheme and an adaptively sound NIZK proof system for $\mathbf{NP}$ yield an IND-CCA1-secure scheme — NY90. The public key is two independent public keys ${\mathsf{pk}}_0,{\mathsf{pk}}_1$ and a common random string $\sigma$; a ciphertext is $(c_0,c_1,\pi )$ with $c_b\leftarrow \mathsf{Enc}({\mathsf{pk}}_b,m)$ and $\pi$ a NIZK proof under $\sigma$ that $c_0$ and $c_1$ encrypt the same message; decryption verifies $\pi$ and decrypts $c_0$.

Sketch

The hybrids simulate the challenge proof, switch $c_1$ from $m_0$ to $m_1$ by a reduction to the CPA security of ${\mathsf{pk}}_1$ that knows ${\mathsf{sk}}_0$, and switch $c_0$ symmetrically with ${\mathsf{sk}}_1$. Decrypting with either key answers a query correctly unless its proof is accepted and its two ciphertexts encrypt different messages; this event is negligible under a real common string by soundness, and, being checkable with both keys, stays negligible under a simulated one by zero knowledge. Only the challenge proof is simulated, so single-theorem zero knowledge suffices, and every decryption query precedes it, so plain soundness suffices — NY90.

Notes

• After the challenge, an adversary could maul the simulated proof into an accepted proof of a false statement; ruling this out takes one-time simulation soundness and gives IND-CCA2 security — Sah99.
• Efficiency: the ciphertext carries a NIZK proof for an $\mathbf{NP}$ statement about the encryption circuit, so the construction is a feasibility result — standard.