Comment by azeirah | Hacker News Reader

Comment by azeirah | Hacker News Reader

Can someone explain to me the zero-knowledge proof example problem discussed on page 37, given two graphs G and H, prove that they are NOT isomorphic?

"But as noticed by Goldreich, Micali, and Wigderson [65], there is something Merlin can do instead: he can let Arthur challenge him. Merlin can say:"

Arthur, send me a new graph K, which you obtained either by randomly permuting the vertices of G, or randomly permuting the vertices of H. Then I guarantee that I will tell you, without fail, whether K ∼= G or K ∼= H.

I don't understand what it means for a graph to be isomorphic to another graph, and I do not understand how Merlin's challenging answer can provide a (zero-knowledge) proof to the given problem either.

An isomorphism between two graphs indicates that bijection exists between two graphs, or that there exists a method to permute one graph's vertices so that they are equal to another one.

What Merlin is saying to Arthur is that no matter what kind of graph K Arthur comes up with, it cannot be congruent to both G and H, or, that there exists no method to create a graph that is both G and H.

Lastly it is zero-knowledge because Arthur learns nothing of the relation between G and H, only that the K he computes is not both of them simultaneously.

Not sure if that helps.

A graph G is isomorphic to H if they are the same up to permuting the vertices. If you have a graph 1 -- 2 -- 3 (a path on 3 vertices, with 2 edges), it's structurally the same as 3 -- 1 -- 2, only the labels of the vertices are different, and that doesn't matter for a graph theorist. So we say the graphs are isomorphic.

I had a hard time understanding what it means when I was in undergraduate school, because it seems so trivial -- why can't I say that the graphs are simply the same, like 1 = 1 or {0} = {0}? You could say they are the same, but the interesting point is that it is not easy to decide whether they are the same if the two graphs G and H are big. Therefore, "graph isomorphism" is a computational problem in its own right.

Reply on news.ycombinator.com