OWF ⇒ Constant-round WI proofs for NP (Feige–Shamir)

Fully-black-box reduction · standard model · FS90 · security loss: polynomial: the hybrid over the parallel repetitions loses a factor of their number, on top of the commitment’s loss

Statement

Every zero-knowledge proof is witness indistinguishable, and witness indistinguishability is preserved under parallel composition — FS90. Hence, if one-way functions exist, the parallel repetition of the GMW91 proof for an $\mathbf{NP}$-complete language is a constant-round witness-indistinguishable proof for $\mathbf{NP}$ with negligible soundness error — FS90.

Sketch

Witness indistinguishability compares the verifier’s views under two witnesses, and a hybrid argument switches the witness in one parallel copy at a time; the reduction plays the honest prover in every other copy, with the witness the hybrid prescribes, since it knows both. Zero knowledge does not survive this, since the simulator must handle all copies at once — FS90.

Notes

• Feige and Shamir also define witness-hiding protocols and show that witness indistinguishability with two independent witnesses gives witness hiding — FS90.
• Two messages suffice given NIZK proofs: NIZK ⇒ zaps — DN00.