On the Complexity of Interactive Arguments

We study the minimal hardness assumptions required for constructing interactive arguments for NP, focusing on succinct arguments—where the prover’s total communication is smaller than the witness size—and on relaxed forms of zero knowledge, such as witness indistinguisha- bility. Known constructions of succinct arguments rely on various types of collision-resistant hash functions, indistinguishability obfuscation, hardness of discrete logarithm, and lattice-based assumptions, while known constructions of witness-indistinguishable arguments require one-way functions (OWFs). This suggests that succinct witness-indistinguishable interactive arguments require OWFs, or equivalently, that the existence of such arguments implies that of OWFs. Nevertheless, we prove that, at least as far as fully black-box reductions are concerned, interactive arguments do not imply OWFs. Specifically, we consider assumption-dependent fully black-box reductions from OWFs to succinct witness-indistinguishable interactive arguments and an additional hardness assumption G (e.g., NP̸ ⊆ P/poly). Such a reduction is a pair (f, R) of (oracle-aided) function f and algorithm R such that, for any succinct witness-indistinguishable interactive argument Π = (P, V) and any inverter Inv of f Π, the algorithm RΠ,Inv breaks either the soundness of Π or the assumption G. We prove that the existence of such a reduction implies a black-box reduction from OWFs to G alone. Namely, beyond what is implied by G, succinct witness-indistinguishable interactive arguments have no black-box implications for the existence of OWFs.