Paper 2026/682
Witness-Indistinguishable Arguments of Knowledge and One-Way Functions
, Bocconi University, Technion – Israel Institute of Technology, Cornell Tech, Tel Aviv University, Massachusetts Institute of TechnologyAbstract
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).
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- One-Way Functionsauxiliary-input one-way functionswitness indistinguishability
- Contact author(s)
-
galarnon42 @ gmail com
noammaz @ gmail com
rafael @ cs cornell edu
jadsilbak @ gmail com - History
- 2026-04-08: approved
- 2026-04-07: received
- See all versions
- Short URL
- https://ia.cr/2026/682
- License
-
CC BY
BibTeX
@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}
}
