4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks, that was enlightening. Regarding your reference to Bayesian statistics, could you elaborate on why exactly someone familiar with the field might understand it better? $\endgroup$
    – cadaniluk
    Apr 15 at 19:40
  • $\begingroup$ And perhaps another question: isn't this definition with probability distributions somehow equivalent to saying that nothing new can be computed, like, maybe, "there exists no computable function whose computation is rendered more efficient after the zero-knowledge proof is completed?" Because that I find way more intuitive. I find the idea with probability distributions interesting, it just does not appeal to my intuition very much. $\endgroup$
    – cadaniluk
    Apr 15 at 19:46
  • $\begingroup$ @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". $\endgroup$
    – Daniel S
    Apr 16 at 6:10
  • $\begingroup$ @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. $\endgroup$
    – Daniel S
    Apr 16 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.