What is meant by the probability distribution of a verifier?

Question

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

From A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm:

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.

From The Knowledge Complexity of Interactive Proof Systems:

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?

Answer 1

A probability distribution is how the verifier's knowledge of the unknown value is summarised. This idea is usually easier to grasp for Bayesian statisticians than classical ones.

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.

The important thing about a zero-knowledge proof is that whatever the verifier infers from their interactions with the prover, they could generate the same information and inferences on their own.