Claw-free permutations ⇒ Concurrent ZK proofs for NP in ω(log n) rounds

Standard model · PRS02

Statement

If claw-free permutation collections exist, then for every $k(n)=\omega (\log n)$, every language in $\mathbf{NP}$ has a $k(n)$-round concurrent zero-knowledge proof with a black-box simulator, sound against unbounded provers. Soundness is unconditional; the claw-free collection is used only for zero knowledge — PRS02.

Notes

• For black-box simulation the round count is optimal up to an $\omega (\log \log n)$ factor, since $o(\log n/\log \log n)$ rounds suffice only for languages in $\mathbf{BPP}$ (Few-round black-box concurrent ZK ⊆ BPP) — CKPR01.
• From one-way functions alone the same round count is achieved by concurrent zero-knowledge arguments (OWF ⇒ Concurrent ZK arguments for NP in ω(log n) rounds) — PRS02.