On the Impossibility of SNARGs with Short CRS : (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting)

We study the inherent barriers to constructing non-adaptively sound succinct non-interactive arguments (SNARGs) for NP with a CRS whose length is sublinear in the witness length. Our results cover both the standard SNARGs and SNARGs with an additional updatable feature (i.e. incrementally verifiable computation for NP).•For updatable SNARGs, we show a black-box separation from falsifiable assumptions for uniform polynomial-time reductions, assuming sub-exponential hardness of learning with error.•For general SNARGs, we show a black-box separation from falsifiable assumptions for non-uniform polynomial-time reductions that only make one query to the adversary, assuming the existence of sub-exponentially secure super-bit generators. We observe that all known SNARG constructions from polynomial hardness of standard assumptions have 1-query soundness reductions. Thus, our result complements existing constructions.Previously, the seminal work [Gentry-Wichs, STOC’11] showed a black-box separation of SNARGs from falsifiable assumptions in the adaptive soundness setting. We explore whether any barriers exist in the non-adaptive setting. To obtain our result, we derive a simulation lemma for unbounded polynomial-length auxiliary inputs assuming super-bit generators.