TR26-050 | Witness-Indistinguishable Arguments of Knowledge and One-Way Functions | Gal Arnon, Noam Mazor, Rafael Pass, Jad Silbak

In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable ($WI$) arguments of knowledge. We establish that: - Assuming that $NP\not\subseteq P/poly,$ the existence of a constant-round computational $WI$ argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist. - Assuming that $NP\not\subseteq P^{Sam}/poly,$ there is no black-box construction of a constant-round (unbounded-verifier) statistical $WI$ argument of knowledge from one-way permutations. Here, $Sam$ is the collision finder oracle of Haitner, Hoch, Reingold, and Segev [FOCS '07]. Moreover, we identify a natural class of knowledge extractors for which stronger versions of the above implications hold (e.g., even if the protocols have many rounds).