Graph Isomorphism

An example might go a long way to explain this concept; this one comes from graph theory [619,622]. A graph is a network of lines connecting different points. If two graphs are identical except for the names of the points, they are called isomorphic. For an extremely large graph, finding whether two graphs are isomorphic can take centuries of computer time; it’s one of those NP-complete problems discussed in Section 11.1.

Assume that Peggy knows the isomorphism between the two graphs, G₁ and G₂. The following protocol will convince Victor of Peggy’s knowledge:

(1)  Peggy randomly permutes G₁ to produce another graph, H, that is isomorphic to G₁. Because Peggy knows the isomorphism between H and G₁, she also knows the isomorphism between H and G₂. For anyone else, finding an isomorphism between G₁ and H or between G₂ and H is just as hard as finding an isomorphism between G₁ and G₂.

(2)  Peggy sends H to Victor.

(3)  Victor asks Peggy either to:

(a)  prove that H and G₁ are isomorphic, or

(b)  prove that H and G₂ are isomorphic.

(4)  Peggy complies. She either:

(a)  proves that H and G₁ are isomorphic, without proving that H and G₂ are isomorphic, or

(b)  proves that H and G₂ are isomorphic, without proving that H and G₁ are isomorphic.

(5)  Peggy and Victor repeat steps (1) through (4) n times.

If Peggy does not know an isomorphism between G₁ and G₂, she cannot create graph H which is isomorphic to both. She can create a graph that is either isomorphic to G₁ or one that is isomorphic to G₂. Like the previous example, she has only a 50 percent chance of guessing which proof Victor will ask her to perform in step (3).

This protocol doesn’t give Victor any useful information to aid him in figuring out an isomorphism between G₁ and G₂. Because Peggy generates a new graph H for each round of the protocol, he can get no information no matter how many rounds they go through the protocol. He won’t be able to figure out an isomorphism between G₁ and G₂ from Peggy’s answers.

In each round, Victor receives a new random permutation of H, along with an isomorphism between H and either G₁ or G₂. Victor could just as well have generated this by himself. Because Victor can create a simulation of the protocol, it can be proven to be zero-knowledge.

Hamiltonian Cycles

A variant of this example was first presented by Manuel Blum [196]. Peggy knows a circular, continuous path along the lines of a graph that passes through each point exactly once. This is called a Hamiltonian cycle. Finding a Hamiltonian cycle is another hard problem. Peggy has this piece of information—she probably got it by creating the graph with a certain Hamiltonian cycle—and this is what she wants to convince Victor that she knows.

Peggy knows the Hamiltonian cycle of a graph, G. Victor knows G, but not the Hamiltonian cycle. Peggy wants to prove to Victor that she knows this Hamiltonian cycle without revealing it. This is how she does it:

(1)  Peggy randomly permutes G. She moves the points around and changes their labels to make a new graph, H. Since G and H are topologically isomorphic (i.e., the same graph), if she knows the Hamiltonian cycle of G then she can easily find the Hamiltonian cycle of H. If she didn’t create H herself, determining the isomorphism between two graphs would be another hard problem; it could also take centuries of computer time. She then encrypts H to get H´. (This has to be a probabilistic encryption of each line in H, that is, an encrypted 0 or an encrypted 1 for each line in H.)

(2)  Peggy gives Victor a copy of H´.

(3)  Victor asks Peggy either to:

(a)  prove to him that H´ is an encryption of an isomorphic copy of G, or

(b)  show him a Hamiltonian cycle for H.

(4)  Peggy complies. She either:

(a)  proves that H´ is an encryption of an isomorphic copy of G by revealing the permutations and decrypting everything, without showing a Hamiltonian cycle for either G or H, or

(b)  shows a Hamiltonian cycle for H by decrypting only those lines that constitute a Hamiltonian cycle, without proving that G and H are topologically isomorphic.

(5)  Peggy and Victor repeat steps (1) through (4) n times.

If Peggy is honest, she can provide either proof in step (4) to Victor. However, if she does not know a Hamiltonian cycle for G, she cannot create an encrypted graph H´ which can meet both challenges. The best she can do is to create a graph that is either isomorphic to G or one that has the same number of points and lines and a valid Hamiltonian cycle. While she has a 50 percent chance of guessing which proof Victor will ask her to perform in step (3), Victor can repeat the protocol enough times to convince himself that Peggy knows a Hamiltonian cycle for G.

Parallel Zero-Knowledge Proofs

The basic zero-knowledge protocol involves n exchanges between Peggy and Victor. Why not do them all in parallel:

(1)  Peggy uses her information and n random numbers to transform the hard problem into n different isomorphic problems. She then uses her information and the random numbers to solve the n new hard problems.

(2)  Peggy commits to the solution of the n new hard problems.

(3)  Peggy reveals to Victor the n new hard problems. Victor cannot use these new problems to get any information about the original problems or its solutions.

(4)  For each of the n new hard problems, Victor asks Peggy either to:

(a)  prove to him that the old and new problems are isomorphic, or

(b)  open the solution she committed to in step (2) and prove that it is a solution to the new problem.

(5)  Peggy complies for each of the n new hard problems.

Unfortunately, it’s not that simple. This protocol does not have the same zero-knowledge properties as the previous protocol. In step (4), Victor can choose the challenges as a one-way hash of all the values committed to in the second step, thus making the transcript nonsimulatable. It is still zero-knowledge, but of a different sort. It seems to be secure in practice, but no one knows how to prove it. We do know that in certain circumstances, certain protocols for certain problems can be run in parallel while retaining their zero-knowledge property [247,106,546,616].