NIZK ⇒ Zaps (Dwork–Naor)

Fully-black-box reduction · standard model · DN00 · security loss: polynomial

Statement

If adaptively sound NIZK proofs in the common random string model exist for $\mathbf{NP}$, then every language in $\mathbf{NP}$ has a zap: a two-message public-coin witness-indistinguishable proof whose first message can be fixed and reused — DN00.

Sketch

The verifier sends many random strings ${\rho }_1,\dots ,{\rho }_{\ell }$. The prover picks a random string $r$ and sends $r$ with NIZK proofs of the statement relative to each reference string ${\rho }_i\oplus r$; the verifier accepts iff all of them verify. Soundness: for a false statement, a union bound over the prover’s choices of $r$ shows that some ${\rho }_i\oplus r$ is a string on which no accepting proof exists, except with negligible probability over the ${\rho }_i$. Witness indistinguishability follows from the zero knowledge of each proof — DN00.

Notes

• Non-interactive zaps, with no verifier message at all, exist under pairing-based assumptions — GOS06.
• Through Doubly enhanced certified TDP ⇒ NIZK, suitably enhanced trapdoor permutations give zaps — FLS90, DN00.