CRHF ⇒ Succinct arguments for NP (Kilian)

Standard model · Kil92 · security loss: polynomial

Statement

If collision-resistant hash functions exist, every language in $\mathbf{NP}$ has a four-message public-coin interactive argument whose communication is polylogarithmic in the size of the $\mathbf{NP}$ verification, times a polynomial in $\lambda$ — Kil92. The argument can be made zero-knowledge — Kil92.

Sketch

The verifier sends a hash key; the prover commits to a probabilistically checkable proof of the statement by the root of a Merkle tree; the verifier sends the PCP verifier’s random queries; the prover opens the queried positions with authentication paths. A prover that answers inconsistently on rewinding yields a collision, so its answers are those of a fixed proof string, which PCP soundness rejects — Kil92.

Notes

• In the random-oracle model, applying the Fiat–Shamir transform to this protocol gives non-interactive succinct arguments: ROM ⇒ SNARK (CS proofs) — Mic00.
• Efficiency: the prover’s work is dominated by computing the PCP and the Merkle tree, and the verifier’s work beyond reading the statement is polylogarithmic in the PCP length — standard.