Claw-free permutations ⇒ Constant-round ZK proofs for NP (Goldreich–Kahan)

Standard model · GK96b · security loss: polynomial

Statement

If claw-free permutation collections exist, every language in $\mathbf{NP}$ has a constant-round zero-knowledge proof with negligible soundness error, sound against unbounded provers — GK96b.

Sketch

The prover sends a claw-free pair, under which the verifier commits to all its challenges with a statistically hiding commitment; the prover sends the first messages of many parallel copies of a three-message zero-knowledge proof, committing with statistically binding commitments; the verifier opens its challenges and the prover answers. Statistical hiding keeps the challenges independent of the prover’s first messages, so soundness holds against unbounded provers, and the commitment to the challenges lets the simulator rewind the verifier to learn them before answering — GK96b.

Notes

• For languages outside $\mathbf{BPP}$, no zero-knowledge proof with negligible soundness error and a black-box simulator has three messages, or is constant-round and public-coin: No constant-round public-coin black-box ZK — GK96a. The GK96b protocol has five messages and is private-coin, since the verifier commits to its challenges — GK96b.
• Claw-free permutations follow from factoring: Factoring ⇒ claw-free permutations — GMR88.