Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-333 | 19th November 2026 19:24

Does Witness Indistinguishability Require Cryptography?

RSS-Feed




TR26-333
Authors: Gal Arnon, Noam Mazor, Rafael Pass, Jad Silbak
Publication: 22nd November 2026 15:36
Downloads: 14
Keywords: 


Abstract:

An interactive proof is witness indistinguishable ($WI$) if the verifier cannot tell which of several valid witnesses the prover used. $WI$ is a fundamental privacy guarantee that is implied by a number of central primitives, including zero knowledge ($ZK$), batch arguments, and succinct arguments.

Ostrovsky and Wigderson [OW93] showed that, assuming the worst-case hardness of $NP$, $ZK$ proofs for $NP$ imply auxiliary-input one-way functions. This was recently strengthened by Hirahara and Nanashima [HN24], who showed that, under the same assumption, $ZK$ proofs for $NP$ imply standard one-way functions. For $WI$, no analogous result was known; in fact, we do not known if cryptography is necessary for $WI$ at all.

One source of difficulty in proving a cryptographic implication from $WI$ is the possible unconditional existence of witness canonicalization. More formally, an $\varepsilon$-witness canonicalization ($\varepsilon$-$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 $NP$ statement can be efficiently mapped to a single canonical representation, then $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 $NP$ language that admits no $\varepsilon$-$WC$ for some inverse-polynomial $\varepsilon$. Then, under a derandomization assumption, every constant-round (honest-verifier) $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 $SAT$ has a $\varepsilon$-$WC$, even for constant $\varepsilon$, the above results establish that cryptography is necessary for designing $WI$ proofs (or sufficiently compressing BARG/SNARGs) for $SAT$. As far as we are aware, these are the first results establishing the necessity of cryptographic hardness for witness indistinguishability, BARGs, and SNARGs.



ISSN 1433-8092 | Imprint