OWF + iO ⇒ Non-adaptively sound NIZK argument

Free reduction · CRS model · SW14 · security loss: additive: zero knowledge is perfect, and the soundness error is at most the iO advantages for the two obfuscated programs plus the punctured-PRF advantage plus the probability of inverting the one-way function, with the punctured PRF built from the one-way function at a polynomial loss

Statement

iO for all polynomial-size circuits together with a one-way function implies non-adaptively sound NIZK arguments for $\mathbf{NP}$ in the common reference string model, the CRS consisting of obfuscated programs — SW14.

Sketch

The reference string holds an obfuscation of a program that, on a statement $x$ and a valid witness, outputs $F(K,x)$ for a puncturable PRF key $K$, and an obfuscation of a program that accepts $(x,\pi )$ iff $f(\pi )=f(F(K,x))$ for a one-way function $f$. The proof is $\pi :=F(K,x)$. For zero knowledge, the simulator computes $F(K,x)$ directly. Soundness is computational and non-adaptive: for a false statement $x$ fixed before the reference string, the obfuscated programs can use $K$ punctured at $x$ with $f(F(K,x))$ hard-wired, then a uniform value in place of $F(K,x)$, after which an accepted proof for $x$ inverts $f$ — SW14.

Notes

• The system is an argument: for every false statement $x$ some $\pi$, namely $F(K,x)$, is accepted, so an unbounded prover finds one. Its soundness proof punctures $K$ at the false statement, which must be fixed before the reference string is sampled, so soundness is non-adaptive; the gap to adaptive soundness is discussed in WW24.
• Without setup, non-interactive zero knowledge exists only for languages in $\mathbf{BPP}$ — GO94.