Four-message black-box ZK proofs ⊆ coMA

Inclusion · Kat08

Statement

Suppose a language $L$ has a four-message interactive proof, sound against unbounded provers, with negligible soundness error that is computational zero-knowledge with a black-box simulator. Then the complement of $L$ is in $\mathbf{MA}$, so $L$ is in coMA — Kat08. The theorem is unconditional and allows imperfect completeness — Kat08. An $\mathbf{NP}$-complete language with such a proof would give $\mathbf{coNP}\subseteq \mathbf{MA}\subseteq \mathbf{AM}$ (BM88), which collapses the polynomial hierarchy to its second level — BHZ87.

Notes

• Five-message private-coin black-box zero-knowledge proofs for $\mathbf{NP}$ exist from claw-free permutations (Claw-free permutations ⇒ Constant-round ZK proofs for NP (Goldreich–Kahan)) — GK96b — and are therefore round-optimal for black-box simulation unless the polynomial hierarchy collapses — Kat08.
• The bound does not extend to arguments: four-message zero-knowledge arguments for $\mathbf{NP}$ exist from any one-way function (OWF ⇒ Four-message ZK arguments for NP) — BJY97.
• Four-message arguments built fully black-box from one-way functions also put the complement of $L$ in $\mathbf{MA}$ (No fully-black-box reduction from OWF to four-message ZK arguments) — HPV20.
• Three-message black-box zero knowledge, for proofs and arguments alike, exists only for languages in $\mathbf{BPP}$ (Three-message black-box ZK ⊆ BPP) — GK96a.