ROM ⇒ SNARK (Micali’s CS proofs)

Free reduction · random oracle model · Mic00, Val08 · security loss: a factor polynomial in the number of random-oracle queries

Statement

In the random-oracle model, every language in $\mathbf{NP}$ has a non-interactive argument, a computationally sound proof, whose proofs have length $\mathrm{poly}(\lambda ,\log T)$ and are verified in time $\mathrm{poly}(\lambda ,|x|,\log T)$, for statements $x$ whose $\mathbf{NP}$ verification takes time $T$ — Mic00. Instantiated with a PCP of knowledge, one from whose accepted proofs a witness can be extracted, the argument is an argument of knowledge, so it is a SNARK without a common reference string — Val08.

Sketch

The prover commits to a probabilistically checkable proof by the root of a Merkle tree built with one random oracle, derives the PCP verifier’s coins by applying a second, independent oracle to the statement and the root, $f_2(x\Vert \mathrm{root})$, and sends the root together with the queried positions and their authentication paths. The verifier recomputes the coins and checks the paths and the PCP verifier’s decision — Mic00.

Notes

• The statement must enter the challenge, since the prover chooses it. With coins $u:=f_2(\mathrm{root})$ alone, take $L:=\{(a,b):a\ne b\}$ for $\lambda$-bit $a,b$ and a PCP verifier that checks one dummy proof bit is $0$ and accepts iff $a\ne b$ or $u=a$; it has perfect completeness and soundness error $2^{-\lambda }$ on each fixed false statement, yet a prover that commits to the dummy proof, computes $u$ and then claims the false statement $(u,u)$ is always accepted — standard.
• The interactive precursor needs only collision-resistant hashing: CRHF ⇒ succinct arguments — Kil92.
• In the common reference string model, no reduction that uses the cheating prover only as an oracle proves adaptive soundness of a SNARG for an $\mathbf{NP}$ language with a sub-exponentially hard subset-membership problem from a falsifiable assumption, unless the assumption is false: No reduction from falsifiable assumptions to SNARKs — GW11.