Injective OWF ⇒ Four-message ZK arguments for NP (fully black-box)

Fully-black-box reduction · standard model · HV18, KOS18

Statement

If injective one-way functions exist, every language in $\mathbf{NP}$ has a four-message zero-knowledge argument with negligible soundness error that uses the function only as a black box — HV18, KOS18, independently.

Notes

• For an arbitrary one-way function, a fully black-box four-message construction would give $\mathbf{coNP}\subseteq \mathbf{MA}$ (No fully-black-box reduction from OWF to four-message ZK arguments) — HPV20; four messages from any one-way function are reached by a construction that is not fully black-box (OWF ⇒ Four-message ZK arguments for NP) — BJY97.
• The same works give fully black-box five-message zero-knowledge arguments for $\mathbf{NP}$ from any one-way function — HPV20.
• HV18 also give a four-message perfect zero-knowledge argument for $\mathbf{NP}$ from claw-free permutations by a black-box construction — HV18. KOS18’s commit-and-prove protocols from injective one-way functions are zero-knowledge in four rounds and witness-indistinguishable in three — KOS18.