Let (P, V) be any ZK protocol, then the protocol is WI. --> help with proof In the amazing paper &quot;Witness Indistinguishable and Witness Hiding Protocols
&quot; by Shamir and Feige.

Theorem 3.3: Let (P, V) be any ZK protocol, then the protocol is WI.

The sketch of the proof involves a distinguisher $D$, which I never saw used in the context of ZK, and I don't know it's definition.
Can you define $D$ ?
Can you point me to the proof of this theorem or just walk me through it loosely?
TL,DR: there's already a quite nice proof sketch in the original paper by Feige and Shamir. Check it out here! If you want to see an intuitive explanation then keep reading!
What does witness indistinguishability mean, intuitively?
Witness indistinguishability (WI): The proof system $(P,V)$ is WI over a relation $R$, if for any instance $x$ the verifier with auxiliary information $y$ cannot distinguish which witness was used in a proof $x\in R$.

Can you define ?

$D$ is a distinguisher that tries to guess which witness was used to generate the proof. Note, that the distinguisher has only access to the proof's transcript and auxiliary information $y$.
What does zero knowledge mean, intuitively?
Zero knowledge (ZK): The proof's transcript $V_{P(w,x)}(x,y)$ and the simulated view $M(x,y;V)$ are indistinguishable.
Theorem (Feige and Shamir): If a proof system $(P,V)$ is zero-knowledge (ZK) then it is also witness indistinguishable (WI).
Proof sketch
If the success probability of distinguisher $D$ is $p$ when witness $w_1$ was used, then by the zero-knowledge property of $(P,V)$ the distinguisher's success probability remains the same, even if it runs on a simulated transcript outputted by $M$, i.e. $M(x,y;V)$, because by the zero-knowledge property we have that the simulator's view $M(x,y;V)$ and the verifier's view $V_{P(x,w_1)}(x,y)$ are indistinguishable. Since the simulator's view is independent from the used witness, therefore we also have that the ensembles $M(x,y;V)$ and $V_{P(x,w_2)}(x,y)$ are indistinguishable. By the transitivity of indistinguishability we have that the ensembles $V_{P(x,w_1)}(x,y)$ and $V_{P(x,w_2)}(x,y)$ are indistinguishable, i.e., the protocol $(P,V)$ is WI.
Note, however, that the opposite is not true. There are WI protocols, that are not ZK. An example is taken from here: Assume the existence of a length-preserving one-way permutation $f$ and define the language
$L_0:= \{y |\text{the first bit of } f^{−1}(y)\text{ is } 0 \}$. (Note that every $y\in L_0$ has the unique witness $x = f^{−1}(y)$.) An interactive proof in which the prover sends $f^{−1}(y)$ on common input $y$ is witness indistinguishable (trivially) but not zero knowledge (assuming $f$ is indeed one-way).