Paper 2026/2957
Does Witness Indistinguishability Require Cryptography?
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
-
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}
}