Paper 2026/2957

Does Witness Indistinguishability Require Cryptography?

Gal Arnon, NTT Research
Noam Mazor, New York University
Rafael Pass, Technion – Israel Institute of Technology, Cornell Tech, Tel Aviv University
Jad Silbak, Massachusetts Institute of Technology
Abstract

An interactive proof is witness indistinguishable ($\mathsf{WI}$) if the verifier cannot tell which of several valid witnesses the prover used. $\mathsf{WI}$ is a fundamental privacy guarantee that is implied by a number of central primitives, including zero knowledge ($\mathsf{ZK}$), batch arguments, and succinct arguments. Ostrovsky and Wigderson [OW93] showed that, assuming the worst-case hardness of $\mathsf{NP}$, $\mathsf{ZK}$ proofs for $\mathsf{NP}$ imply auxiliary-input one-way functions. This was recently strengthened by Hirahara and Nanashima [HN24], who showed that, under the same assumption, $\mathsf{ZK}$ proofs for $\mathsf{NP}$ imply standard one-way functions. For $\mathsf{WI}$, no analogous result was known; in fact, we do not known if cryptography is necessary for $\mathsf{WI}$ at all. One source of difficulty in proving a cryptographic implication from $\mathsf{WI}$ is the possible unconditional existence of witness canonicalization. More formally, an $\varepsilon$-witness canonicalization ($\varepsilon$-$\mathsf{WC}$) is a deterministic polynomial-time map that sends any valid witness $w$ for $x$, together with public randomness $r$, to an efficiently verifiable string that depends only on $x$ and $r$ (and not on the specific witness $w$), except with probability $\varepsilon$. Completeness and soundness hold perfectly (only canonicalization is allowed to fail). Indeed, if a valid witnesses for an $\mathsf{NP}$ statement can be efficiently mapped to a single canonical representation, then $\mathsf{WI}$ is trivial and requires no cryptography: the prover sends the canonical witness, and so reveals nothing about its own. We prove the following: 1. Let $L$ be an $\mathsf{NP}$ language that admits no $\varepsilon$-$\mathsf{WC}$ for some inverse-polynomial $\varepsilon$. Then, under a derandomization assumption, every constant-round (honest-verifier) $\mathsf{WI}$ proof for $L$ implies infinitely-often auxiliary-input one-way functions. The derandomization assumption can be avoided if one settles for canonicalization with negligible completeness and soundness errors. 2. Combining (a variant of) the above with a theorem of Bitansky, Kamath, Paneth, Rothblum, and Vasudevan [BKPRV24] yields analogous consequences for sufficiently compressing batch arguments and succinct non-interactive arguments. Since it is unlikely that $\mathsf{SAT}$ has a $\varepsilon$-$\mathsf{WC}$, even for constant $\varepsilon$, the above results establish that cryptography is necessary for designing $\mathsf{WI}$ proofs (or sufficiently compressing BARG/SNARGs) for $\mathsf{SAT}$. As far as we are aware, these are the first results establishing the necessity of cryptographic hardness for witness indistinguishability, BARGs, and SNARGs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
witness indistinguishabilityone-way functions
Contact author(s)
galarnon42 @ gmail com
noammaz @ gmail com
rafael @ cs cornell edu
jadsilbak @ gmail com
History
2026-11-22: approved
2026-11-19: received
See all versions
Short URL
https://ia.cr/2026/2957
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2957,
      author = {Gal Arnon and Noam Mazor and Rafael Pass and Jad Silbak},
      title = {Does Witness Indistinguishability Require Cryptography?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2957},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2957}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.