Zero knowledge

The idea of zero knowledge is that in the interaction of two Turing machines it is possible to create a protocol that simulates a trust by one machine in the other without having to assume trust-worthiness of either machine.

The two machines are called the prover and the verifier. Both are probabilistic machines. This game cannot be played without randomness. In the context of cryptography this provides no real restriction since the entire aim is probabilistic. An encryption of any sort depends on a secret, and this secret can be guessed, however unlikely that guess might be. Any mathematical proof, therefore, cannot say: this is impossible; it aims to say: this is unlikely, and to quantify the likelihood.

The outlook to take on probabilistic Turing machines is that it is the embodiment of a random variable. For each input x, the machine gives a result depending on another input r. The input r is considered as a point in a probablity space, say Omega. In our discrete setting, Omega might be the set of length n strings of zero's and one's, Omega = { 0, 1 }n. Generally it is assumed that Omega is given the structure of n independent Bernoulli trials, that is, each zero or one is chosen independently with probability 50-50, so that each string is equally likely, and so forth.

In this way, the machine M, which is really a function on two variables M(x,r), is, for each x, a random variable M(x) from Omega to the machine's output. The function is measurable, the probability that M(x)=z, for some z in the output, is the measure of the set of r such that M(x,r)=z. In the usual interpretation of Omega, it would then be the number of r for which M(x,r)=z divided by the total number of elements in Omega, which is 2n.

The prover and verifier are distinguished by their computational power. The verifier is polynomial time, however the prover can have unbounded computational power, bound only by the raw computability constraint as understood in the theory of Turing machines. That is, the prover can compute any computable function. It also is probabilistic, and this is an important component of this game.

The two machines communicate and in this way the verifier is aided in its computations by the prover. The interaction is called an Interactive Proof (IP), and those things that the verifier can accept given any IP protocol is called a language in IP. Note that the verifier must be correctly convinced of the prover's proof. Zero-knowledge is an additional step beyond this.

Both the prover and verifier are probabilistic Turing machines, each with private random strings as input, each with the common input x as input, and with special tapes the permit communication between the two machines. The discipline of the communication is strict. The machines alternate in computation, which ends in the placing of a message on a common communication tape for the other party to read. A deux ex machina tells the machines to start, pause, and continue. The number of messages is called the round complexity of the protocol. We look at three round protocols with the first move from prover to verifier.

  1. Round 1: Given input x, Prover computes using randomness from its input rP. It writes message m1 on the communication tape and pauses.
  2. Round 2: Verifier begins when Prover pasuses. It reads input x and the message m1, and uses its own random bits rV. Verifier writes mesasge m2 on the communication tape and pauses. It
  3. Round 3: Prover continues its computation when the verifier pauses. It reads message m2 from the communication tape, and continues to read random bits from rP as needed. It writes message m3 on the communcation and halts.
  4. Final: Verifier continues, reading m3 from the communication, continuing its calculation. It accepts or rejects and halts. The protocol is complete.

An example from number theory. (From the original paper on Zero-knowledge)