OWF ⇒ Four-message ZK arguments for NP

Standard model · BJY97

Statement

If one-way functions exist, every language in $\mathbf{NP}$ has a four-message computational zero-knowledge argument with negligible soundness error — BJY97. Four-message zero-knowledge arguments for $\mathbf{NP}$ were known before only from stronger assumptions — FS89.

Notes

• Four rounds and one-way functions are each necessary for negligible-error zero-knowledge arguments for $\mathbf{NP}$ — BJY97; the round bound holds for black-box simulation, since three-message black-box zero knowledge exists only for languages in $\mathbf{BPP}$ (Three-message black-box ZK ⊆ BPP) — GK96a.
• The construction cannot be fully black-box in the one-way function unless $\mathbf{coNP}\subseteq \mathbf{MA}$ (No fully-black-box reduction from OWF to four-message ZK arguments) — HPV20.
• Fully black-box four-message arguments follow from injective one-way functions (Injective OWF ⇒ Four-message ZK arguments for NP (fully black-box)) — HV18, KOS18.