Zero-knowledge proof of 3-coloring of a map

I attended the three fascinating talks of Avi Wigderson on the occasion of the Wolfgang Pauli Lectures 2012 at ETH Zurich. Avi Wigderson is a renowned mathematician who won both the Nevanlinna Prize (1994) and the Gödel Prize (2009). Besides many interesting topics he also presented a simple zero-knowledge proof of the 3-coloring of a map. I describe here a slightly modified version of this proof.

There are two protagonists in this story: Alice and Bob. Bob struggles with the task to paint a map with 3 colors such that the neighboring countries have different colors. This is in fact a difficult task for maps with many countries because it is NP-complete. Bob asks Alice for help. After a short time Alice claims to have found a correct coloring. However, she does not want to show Bob the coloring but only convince him that she knows it. This is the essence of zero-knowledge proofs: the prover (Alice) shows that she knows the solution without revealing the solution to the verifier (Bob). The proof is an interaction between the prover and the verifier.

Alice writes the found colors on paper cards and lays them on the respective countries upside down, such that Bob cannot read them. Bob selects two neighboring countries, flips their cards and checks their colors. If Alice cheated and she does not have a correct solution then at least two neighbors have the same color. If there are e.g. 100 neighbors, then the probability to catch a false coloring is only 1/100 = 1%. The probability not to detect the fraud is high, namely 99%.

But now the game can be repeated. Of course, it cannot be that Bob just continues flipping the other cards because then he would learn the complete coloring. First, Alice withdraws all the cards from the map. Then, she permutes the colors. For example if she used the colors 1=red, 2=green, 3=blue for the first coloring, she takes now 1=green, 2=blue, 3=red for another feasible coloring. She produces new cards and lays them on the map upside down. Bob checks again two neighbors. The probability that he does not detect wrong coloring is again 0.99. However, the probability that he does not detect it in the first and in the second experiment is 0.99 * 0.99 = 0.9801. The probability that he does not detect a possible fraud in 500 trials is 0.99**500 = 0.0066, i.e. less than 1%. In other words, after 500 experiments Bob knows that Alice has got the solution with probability at least 99%.

As the experiment is repeated, Bob either detects a wrong coloring or increases his belief that Alice has indeed got a solution. At the same time he does not learn anything about the actual coloring. For Alice, it is important that she choses one of the six possible color permutation with the same probability 1/6. Otherwise, the neighbor countries would get some preferred color that could be learned by Bob.

Instead of using the one-sided cards, Alice could write the colors in a letter, put these letters into envelopes, seal the envelopes and address them with the names of the respective country. Bob would select the envelopes corresponding to two neighboring countries, open them and check the colors. It is important that once Alice produces the solution, she commits to it and cannot change it until Bob makes the check.

The computer implementation could work as follows. Suppose Alice and Bob are two computers in a computer network. Bob enumerates the countries 1, 2, 3, ... and encodes the map as a list of neighbors
(i, j), (i, k), (j, m), ....
He sends this list to Alice. Alice computes the country colors
c₁, c₂, c₃, ...,
where each c_i is one of the 3 colors. She encodes the colors using a different key k_i for each country such that she gets
y₁ = E(k₁, c₁),
y₂ = E(k₂, c₂),
y₃ = E(k₃, c₃),
etc.
She sends the message
[y₁, y₂, y₃, ...]
to Bob. After Bob has received this message he picks two neighbor countries (i, j) and requests the keys for them from Alice. Alice sends him the keys k_i, k_j. Bob decrypts y_i, y_j to get the country colors:
c_i = E^-1(k_i, y_i),
c_j = E^-1(k_j, y_j).
If the colors are the same (c_i = c_j) then Alice cheated and the game stops. If If the colors are different (c_i ≠ c_j) then the game goes to a next round. Alice permutes the colors and encrypts the country colors with new keys. She sends the encrypted country colors to Bob and so on.