13.4 Computational Zero-knowledge Proofs

In this section, we give a zero-knowledge proof system for the NP-complete decision problem Graph 3-Colorability, which is defined in Figure 13.11. The proof system uses a bit commitment scheme; to be specific, we will employ the bit commitment scheme presented in Section 13.3 that is based on probabilistic encryption. We assume that Peggy knows a 3-coloring φ of a graph G, and she wants to convince Vic that G is 3-colorable in a zero-knowledge fashion. Without loss of generality, we assume that G has vertex set V = {1, …, n}. Denote m = |E|. The proof system will be described in terms of a commitment scheme f : {0, 1} x X → Y which is made public. Since we want to encrypt a color rather than a bit, we will replace the color 1 by the two bits 01, the color 2 by 10 and the color 3 by 11. Then we encrypt each of the two bits representing the color by using f.

Figure 13.11  Graph 3-Colorability

The interactive proof system is presented in Figure 13.12. Informally, what happens is the following. In each round, Peggy commits a coloring that is a permutation of the fixed coloring φ. Vic requests that Peggy open the blobs corresponding to the endpoints of some randomly chosen edge. Peggy does so, and then Vic checks that the commitments are as claimed and that the two colors are different. Notice that all Vic’s computations are polynomial-time, and so are Peggy’s, provided that she knows the existence of one 3-coloring φ.

Here is a very small example to illustrate.

Example 13.3

Suppose G is the graph (V, E), where

and

Suppose that Peggy knows the 3-coloring φ where φ(1) = 1, φ(2) = φ(4) = 2 and φ(3) = φ(5) = 3. Suppose also that the bit commitment scheme is defined as f(b, x) = 156897^bx² mod 321389, where b = 0, 1 and .

Suppose that Peggy chooses the permutation π = (1 3 2) in some round of the proof. Then she computes:

Figure 13.12  A computational zero-knowledge interactive proof system for Graph 3-colorability

She will encode this coloring in binary as the 10-tuple

0111101110

and then compute commitments of these ten bits. Suppose that she does this as follows:

Then Peggy gives Vic the ten values f(b, x) computed above.

Next, suppose that Vic chooses the edge 34 as his challenge. Then Peggy opens four blobs: the two that correspond to vertex 3 and the two that correspond to vertex 4. So Peggy gives Vic the ordered pairs

Vic will first check that the two colors are distinct: 10 encodes color 2 and 11 encodes color 3, so this is all right. Next, Vic verifies that the four commitments are valid and hence this round of the proof is completed successfully.

As in previous proof systems we have studied, Vic will accept a valid proof with probability 1, so we have completeness. What is the probability that Vic will accept if G is not 3-colorable? In this case, for any coloring, there must be at least one edge ij such that i and j have the same color. Vic’s chances of choosing such an edge are at least 1/m. Peggy’s probability of fooling Vic in all m² rounds is at most

Since (1 - 1/m)m → e^-1 as m ∞, there exists an integer m₀ such that (1 - 1/m)^m ≤ 2/e for m ≥ m⁰. Hence . Since (2/e)^m approaches zero exponentially quickly as a function of m = |E|, we have soundness as well.

Let’s now turn to the zero-knowledge aspect of the proof system. All that Vic sees in any given round of the protocol is an encrypted 3-colouring of G, together with the two distinct colours of the endpoints of one particular edge, as previously committed by Peggy. Since the colors are permuted in each round, it seems that Vic cannot combine information from different rounds to reconstruct the 3-coloring.

The proof system is not perfect zero-knowledge, but it does provide a weaker form of zero-knowledge called computational zero-knowledge. Computational zero-knowledge is defined exactly as perfect zero-knowledge, except that the relevant probability distributions of transcripts are required only to be polynomially indistinguishable (in the sense of Chapter 12) rather than identical.

We begin by showing how transcripts can be forged. We give an explicit algorithm that will forge transcripts that cannot be distinguished from those produced by an honest Vic. If Vic deviates from the protocol, then it is possible to construct a simulator which uses the algorithm V* as a restartable subroutine to construct forged transcripts. Both forging algorithms follow the pattern of the related algorithms for the Graph Isomorphism proof system.

Here, we consider only the case where Vic follows the protocol. A transcript T for the interactive proof of Graph 3-colorability would have the form

where A_j consists of 2n blobs computed by Peggy, the edge uv chosen by Vic, the colors assigned by Peggy in round j to u and v, and the four random numbers used by Peggy to encrypt the colors of these two vertices. A transcript is forged by means of the forging algorithm presented in Figure 13.13.

Proving (computational) zero-knowledge for Vic requires showing that the two probability distributions on transcripts (as produced by the Vic taking part in the protocol, and as produced by the simulator) are indistinguishable. We will not do this here, but we will make a couple of comments. Notice that the two probability distributions are not identical. This is because virtually all the R_ij’s in a forged transcript are blobs encrypting 1; whereas the R_ij’s on a real transcript will (usually) be encryptions of more equal numbers of 0’s and 1’s. However, it is possible to show that the two probability distributions cannot be distinguished in polynomial time, provided that the underlying bit commitment scheme is secure. More precisely, this means that the probability distribution on blobs encrypting color c are indistinguishable from the probability distribution on blobs encrypting color d if c ≠ d.

Readers familiar with NP-completeness theory will realize that, having given a zero-knowledge proof for one particular NP-complete problem, we can obtain a zero-knowledge proof for any other problem in NP. This can be done by applying a polynomial transformation from a given problem in NP to the Graph 3-coloring problem.

Figure 13.13  Forging algorithm for transcripts for Graph 3-colorability