SNARK + OWF ⇒ NIZK argument

CRS model · KMY20

Statement

A SNARG for $\mathbf{NP}$ with proof size $\mathrm{poly}(\lambda )\cdot (|x|+|w|{)}^c$ for a constant $c<1/2$, together with a one-way function, yields a NIZK argument for $\mathbf{NP}$. The SNARG needs neither knowledge soundness nor efficient verification — KMY20.

Notes

• A SNARK need not be zero-knowledge, so it is not by itself a NIZK; a zk-SNARK is a NIZK argument by definition — standard.
• The 2022 revision of the paper (its Journal of Cryptology version) relaxes the succinctness requirement to proof size $\mathrm{poly}(\lambda )\cdot (|x|+|w|{)}^{\delta }$ for any constant $\delta <1$, still without requiring sublinear verification — KMY20.