No fully-black-box reduction from Falsifiable assumption to SNARK

Conditional · against fully-black-box reductions · assuming the language has a sub-exponentially hard subset-membership problem · GW11

Statement

Let $L$ be an NP language with a sub-exponentially hard subset-membership problem. If a reduction that uses the cheating prover only as an oracle proves the adaptive soundness of a SNARG for $L$ in the CRS model from a falsifiable assumption, then the assumption is false; the separation covers designated-verifier SNARGs and slightly succinct ones, whose proofs need only be sublinear in the statement and witness length — GW11.

Sketch

Succinctness and the hardness of $L$ give an inefficient cheating prover $P^{\ast }$ that outputs false statements with accepting proofs, whose statement–proof pairs are indistinguishable from those of an efficient prover $P$ that samples true statements with witnesses and proves them honestly (the short proof is simulated as leakage on the witness). Since $P^{\ast }$ breaks adaptive soundness, the reduction $R^{P^{\ast }}$ breaks the assumption; the assumption’s challenger is efficient, so $R^P$ wins its game with probability negligibly close to that of $R^{P^{\ast }}$, and $R^P$ is efficient, so the assumption is false.

Notes

• Adaptively sound SNARGs for NP nonetheless exist in the plain model, from sub-exponentially hard indistinguishability obfuscation and one-way functions together with the polynomial hardness of discrete log or factoring — WW24.