No fully-black-box reduction from OWF to four-message ZK arguments

Unconditional · against fully-black-box reductions · HPV20

Statement

If a language $L$ has a four-message zero-knowledge argument with negligible soundness error that is fully black-box from one-way functions, then the complement of $L$ is in $\mathbf{MA}$ — HPV20. So a fully black-box construction of four-message zero-knowledge arguments for $\mathbf{NP}$ from every one-way function would give $\mathbf{coNP}\subseteq \mathbf{MA}\subseteq \mathbf{AM}$ (BM88) and collapse the polynomial hierarchy to its second level — BHZ87.

Notes

• Four-message zero-knowledge arguments for $\mathbf{NP}$ do follow from any one-way function (OWF ⇒ Four-message ZK arguments for NP) — BJY97; by HPV20’s theorem that construction is not fully black-box unless $\mathbf{coNP}\subseteq \mathbf{MA}$.
• Fully black-box four-message arguments exist from injective one-way functions (Injective OWF ⇒ Four-message ZK arguments for NP (fully black-box)) — HV18, KOS18 — and, as HPV20 note, the same works give fully black-box five-message ones from any one-way function — HPV20.
• For proofs sound against unbounded provers, four messages with a black-box simulator put $L$ in coMA under no assumption at all (Four-message black-box ZK proofs ⊆ coMA) — Kat08.