# What is meant by the probability distribution of a verifier?

I'm having trouble understanding the role of probability distributions in the definitions of computational/statistical indistinguishability, especially in the definition of zero-knowledge.

An interactive proof is called perfect zero-knowledge if the probability distribution generated by any probabilistic polynomial-time verifier interacting with the prover on input a theorem $$\phi$$, can be generated by another probabilistic polynomial time machine which only gets $$\phi$$ as input (and interacts with nobody!).

This I would understand if "probability distribution" were replaced by "computable function", such that zero-knowledge means that we cannot compute anything beyond what we can compute anyway after the proof because we did not gain new knowledge besides the truth of the theorem. But why "probability distribution"? And what is the subject of distribution here, the random coin tosses of prover and verifier? Because that would not make sense to me.

Consider a pair x, y in QNR and say that A follows the protocol. Can B obtain any additional knowledge? For the moment, assume that B follows the protocol. B "sees" [$$\{b_i\}$$, $$\alpha$$, $$\{ w_i\}$$, $$\{c_i\}$$] distributed according to a particular distribution. Without any help from a prover, we can quickly generate a random string according to this distribution: just choose $$\{b_i\}$$ and $$\alpha$$ randomly, and then compute $$\{w_i\}$$ from them; then compute $$c_i = b_i$$ for each $$i$$.

Here we have a very concrete example of the "subject of distribution" I mentioned above, namely [$$\{b_i\}$$, $$\alpha$$, $$\{w_i\}$$, $$\{c_i\}$$]. However, I don't quite get the usefulness of that.

Is it just that the verifier, does not know anything for certain, so he looks sort of through a "probability-distribution lens" to make sense of the world?

Suppose that the unknown value $$x$$ is just a $$n$$-bit string, a verifier might start out with no information about $$x$$ and thinks all $$2^n$$ possible values are equally likely: a uniform probability distribution on $$2^n$$ values. After an interaction with the prover, the verifier might say "I now know that $$x$$ is not one of these $$k$$ values" and their knowledge could be summarised as a uniform distribution on $$2^n-k$$ values. Or they might say "I now know that $$x$$ has even Hamming weight", giving a uniform distribution on $$2^{n-1}$$. They might say that "I am now 90% sure that $$x$$ has even Hamming weight" and give a two-valued histogram distribution with probability $$1.8/2^{n}$$ on even Hamming weight values and $$0.2/2^n$$ on odd Hamming weight values. They might even say "I think that interpreted as an integer $$x$$ is (truncated) Poisson distributed with mean $$\mu$$". All of these are different types of knowledge that the verifier might infer about $$x$$ based on their interactions with the prover.
• @cadaniluk: 1. Classical statisticians might balk at the notion of a probability distribution on $x$ which they view as a fixed number albeit unknown to the verifier. Bayesian statisticians are more comfortable with the idea that a probability distribution can describe a subjective belief rather than an objective reality. It's a question of language. A friend once said: "Classical statisticians and Bayesians do the same sums; they just think different thoughts while doing them". Apr 16, 2021 at 6:10
• @cadaniluk 2. I think you might need to append "... (counting the computation expended in the proof as part of the overall computation of the function)". Otherwise people could use the prover to outsource pre-computation for certain algorithms. I'm also trying to decide if it is possible that there's knowledge $x$ that can't be effectively computationally exploited. Apr 16, 2021 at 6:17