Statistically hiding COM ⇒ Statistical ZK arguments for NP

Fully-black-box reduction · standard model · BCC88 · security loss: polynomial: a prover breaking soundness yields a committer breaking binding

Statement

A commitment scheme statistically hiding against every receiver, including one that samples $\mathsf{pp}$ or deviates in the commit phase, and computationally binding, yields, for every language in $\mathbf{NP}$, an interactive argument that is statistically zero-knowledge and computationally sound — BCC88. With a perfectly hiding commitment the argument is perfect zero-knowledge.

Sketch

Run a zero-knowledge proof for an $\mathbf{NP}$-complete problem, such as GMW91’s protocol for graph 3-colourability, with the prover’s commitments made statistically hiding. The simulator’s guessing strategy then reproduces the verifier’s view up to statistical distance. On a graph with no 3-colouring, a prover that answers every edge challenge on the same commitments opens some vertex to two colours, so rewinding a prover that cheats with probability noticeably above $1-1/|E|$ per round breaks binding — standard.

Notes

• Statistically hiding commitments exist from one-way permutations — NOVY98 — and from one-way functions — HR07; statistical zero-knowledge arguments for $\mathbf{NP}$ from one-way functions came first, without such commitments (OWF ⇒ statistical ZK arguments) — NOV06.
• Statistical zero-knowledge proofs, as opposed to arguments, exist only for languages in $\mathbf{AM}\cap \mathbf{coAM}$ (SZK ⊆ AM, SZK ⊆ coAM), so they cannot cover $\mathbf{NP}$ unless the polynomial hierarchy collapses — BHZ87.