Which Languages Have 4-Round Fully Black-Box Zero-Knowledge Arguments from One-Way Functions?

摘要

We prove that if a language £ has a 4-round fully black-box zero-knowledge argument with negligible soundness based on one-way functions, then £ ∈ MA. Since coNP ⊆ MA implies that the polynomial hierarchy collapses, our result implies that NP-complete languages are unlikely to have 4-round fully black-box zero-knowledge arguments based on one-way functions. In TCC 2018, Hazay and Venkitasubrama-niam, and Khurana, Ostrovsky, and Srinivasan demonstrated 4-round fully black-box zero-knowledge arguments for all languages in NP based on injective one-way functions. Their results also imply a 5-round protocol based on one-way functions. In essence, our result resolves the round complexity of fully black-box zero-knowledge arguments based on oneway functions.