OWF ⇒ Concurrent ZK arguments for NP in ω(log n) rounds

Standard model · PRS02

Statement

If one-way functions exist, then for every $k(n)=\omega (\log n)$, every language in $\mathbf{NP}$ has a $k(n)$-round concurrent zero-knowledge argument — PRS02. The round count is within an $\omega (\log \log n)$ factor of the lower bound for black-box simulation (Few-round black-box concurrent ZK ⊆ BPP) — CKPR01.

Notes

• The first concurrent zero-knowledge protocol for $\mathbf{NP}$ without timing assumptions used $O(n^{\epsilon })$ rounds — RK99 — and the round count was then brought down to $\omega ({\log }^{2}n)$ — KP01.
• Assuming claw-free permutation collections, the same round count is achieved by concurrent zero-knowledge proofs, sound against unbounded provers (Claw-free permutations ⇒ Concurrent ZK proofs for NP in ω(log n) rounds) — PRS02.