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.