CPA-secure PKE + NIZK ⇒ CCA2-secure PKE (DDN, Sahai)

Free reduction · standard model · DDN91, Sah99 · security loss: polynomial

Statement

A perfectly correct IND-CPA-secure PKE scheme and an adaptively sound NIZK proof system for $\mathbf{NP}$ yield an IND-CCA2-secure scheme. DDN91 construct a scheme that is non-malleable under adaptive chosen-ciphertext attack, a notion equivalent to IND-CCA2 — BDPR98. Sah99 builds one-time simulation-sound NIZK from any NIZK and one-way function, and shows that Naor–Yung double encryption with such a proof is IND-CCA2-secure.

Sketch

In Sah99’s proof, the single simulated proof in the challenge cannot be mauled: simulation soundness keeps every accepted decryption query, after the challenge as before, an encryption of one message under both keys, so the Naor–Yung hybrid goes through — Sah99.

Notes

• Both constructions use a one-way function for one-time signatures or simulation soundness; the CPA-secure scheme supplies one — IL89.
• A simpler construction uses ordinary NIZK and one-time signatures — Lin03.
• Suitably enhanced trapdoor permutations give both NIZK proofs for $\mathbf{NP}$ (Doubly enhanced certified TDP ⇒ NIZK) and PKE, hence IND-CCA2-secure PKE — FLS90, GR13.