OWF ⇒ ZKP (MPC in the head)

Fully-black-box reduction · standard model · IKOS07

Statement

Suppose one-way functions exist, and let $R(x,w)$ be an $\mathbf{NP}$ relation checked by a circuit of size $s$ on witnesses of length $m$. Then $R$ has a computational zero-knowledge proof that uses a statistically binding commitment, and a multi-party protocol computing $R(x,w_1\oplus \cdots \oplus w_n)$ from additive shares of $w$, only as black boxes; the multi-party protocol need only be secure against a small number of semi-honest parties — IKOS07. Such protocols exist unconditionally with an honest majority — BGW88. For security parameter $k$, the communication is $O(s)+\mathrm{poly}(k)$ for a circuit with bounded fan-in, and $m\cdot \mathrm{poly}(k)\cdot \mathrm{polylog}(s)$ for a constant-depth circuit with unbounded fan-in — IKOS07.

Sketch

The prover splits $w$ into shares $w_1\oplus \cdots \oplus w_n$, runs in its head a protocol private against any two parties, and commits to every party’s view. The verifier opens two random views and accepts iff they are consistent and output 1. For a false statement, perfect correctness and statistical binding force some inconsistent pair, which is caught with probability at least $1/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ per repetition, and privacy against two parties together with hiding give the simulator — IKOS07.

Notes

• The previous best communication for such proofs was $O(ks)$ — IKOS07.
• The commitment is Naor’s, on a pseudorandom generator from the one-way function (PRG ⇒ COM, OWF ⇒ PRG) — Naor91, HILL99. The same hypothesis gives zero-knowledge proofs for $\mathbf{NP}$ through graph 3-colorability (OWF ⇒ ZKP) — GMW91.