Paper 2026/682

Witness-Indistinguishable Arguments of Knowledge and One-Way Functions

Noam Mazor, New York University

Rafael Pass, Technion – Israel Institute of Technology, Cornell Tech, Tel Aviv University

Jad Silbak, Massachusetts Institute of Technology

Abstract

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\nsubseteq 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).

@misc{cryptoeprint:2026/682,
      author = {Gal Arnon and Noam Mazor and Rafael Pass and Jad Silbak},
      title = {Witness-Indistinguishable Arguments of Knowledge and One-Way Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/682},
      year = {2026},
      url = {https://eprint.iacr.org/2026/682}
}