Zap + HSG ⇒ Non-interactive zaps (BOV)

Standard model · BOV03

Statement

Suppose every language in $\mathbf{NP}$ has a zap and there is a hitting-set generator against co-nondeterministic circuits. Then every language in $\mathbf{NP}$ has a non-interactive zap: a one-message witness-indistinguishable proof that needs no setup or shared random string — BOV03, who derandomize the zaps of DN00.

Sketch

For every seed $s$, the prover sends the zap prover’s answer to the first message $G(s)$, and the verifier accepts iff every answer verifies. Fix a false statement $x$: the first messages on which some answer is accepted form a set of density at most $1/2$, and a polynomial-size co-nondeterministic circuit decides its complement, so some $G(s)$ lies outside it. Witness indistinguishability of each answer holds for every first message, and a hybrid over the polynomially many seeds gives witness indistinguishability of the whole proof — BOV03.

Notes

• Composed with NIZK ⇒ Zaps (Dwork–Naor) and Doubly enhanced certified TDP ⇒ NIZK, this gives non-interactive zaps from doubly enhanced certified trapdoor permutations together with the generator; BOV03 state the result for any trapdoor permutation, and the enhancement is what the NIZK step needs — BOV03, GR13.
• The same generator derandomizes Naor’s commitment (PRG ⇒ COM) into a non-interactive commitment from any one-way function — BOV03.
• Non-interactive zaps without a derandomization assumption follow from the decisional linear assumption in bilinear groups (Bilinear pairing + DLIN ⇒ Zaps (non-interactive)) — GOS06b.