Today we define the notion of computational zero knowledge and show that the simulator we described in the last lecture establishes the computational zero knowledge property of the 3-coloring protocol.
1. The Protocol and the Simulator
Recall that we use a commitment scheme for messages in , and that the common input to the prover and the verifier is a graph , where . The prover, in addition, is given a valid 3-coloring of .
The protocol is defined as follows:
- The prover picks a random permutation of the set of colors, and defines the 3-coloring . The prover picks keys for , constructs the commitments and sends to the verifier;
- The verifier picks an edge uniformly at random, and sends to the prover;
- The prover sends back the keys ;
- If and are the same color, or if at least one of them is equal to , then the verifier rejects, otherwise it accepts
For every verifier algorithm , we defined a simulator algorithm which repeats the following procedure until the output is different from :
- Input: graph
- Pick random coloring .
- Pick random keys
- Define the commitments
- Let be the 2nd-round output of given as input and as first-round message
- If , then output FAIL
- Else output
We want to show that this simulator construction establishes the computational zero knowledge property of the protocol, assuming that is secure. We give the definition of computational zero knowledge below.
Definition 1 (Computational Zero Knowledge) We say that a protocol for 3-coloring is computational zero knowledge with simulator overhead if for every verifier algorithm of complexity there is a simulator of complexity on average such that for every algorithm of complexity , every graph and every valid 3-coloring we have
Theorem 2 Suppose that is -secure and that is computable in time .
Then the protocol defined above is computational zero knowledge with simulator overhead at most .
2. Proving that the Simulation is Indistinguishable
In this section we prove Theorem 2.
Suppose that the Theorem is false. Then there is a graph , a 3-coloring , a verifier algorithm of complexity , and a distinguishing algorithm also of complexity such that
Let be the event that the edge is selected in the second round; then
So there must exist an edge such that
(We have omitted references to , which are fixed for the rest of this section.)
Now we show that there is an algorithm of complexity that is able to distinguish between the following two distributions over commitments to colors:
- Distribution (1) commitments to the colors ;
- Distribution (2) commitments to random colors
- Input: 3n commitments where and ;
- Pick a random permutation
- Pick random keys ,
- Construct the sequence of commitments by setting:
- for every ,
- If the 2nd round output of given and is different from output 0
- Else output
First, we claim that
This follows by observing that on input Distribution (1) behaves exactly like the prover given the coloring , and that accepts if and only if the event happens and accepts the resulting transcript.
Next, we claim that
To prove this second claim, we introduce, for a coloring , the quantity , defined as the probability that the following probabilistic process outputs 1:
- Pick random keys
- Define commitments
- Let be the 2nd round output of given the input graph and first round message
- Output 1 iff , , and
Then we have
Because , on input Distribution 2, first prepares commitments to a coloring chosen uniformly at random among all colorings such that and then outputs 1 if and only if, given such commitments as first message, replies with and the resulting transcript is accepted by .
We also have
To see why Equation (5) is true, consider that the probability that outputs a particular transcript is exactly times the probability that outputs that transcript. Also, the probability that outputs a transcript which involves at the second round and which is accepted by conditioned on being the coloring selected at the beginning is if is a coloring such that , and it is zero otherwise. Finally, selects the initial coloring uniformly at random among all possible coloring.
From our security assumption on and from Lemma 6 in Lecture 27 we have
and so the claim we made in Equation (3) follows from Equation (4), Equation (5), Equation (6) and the fact that if are quantities such that , , and (so that ), then
(We use the above inequality with , , and .)
Having proved that Equation (3) holds, we get
where is an algorithm of complexity at most . Now by a proof similar to that of Theorem 3 in Lecture 27, we have that is not secure.