Re: Need Graph Isomorphism Algorithm De-bunked

Bill Cox wrote:
I don't understand that there's a problem with auto-morphism. If two
nodes end up with the same hash, then the graph with those nodes
exchanged is isomorphic to the original graph, which is as it should be.
And the nodes of any other graph isomorphic to that graph will generate
the same node hash values with the same duplicate values.

--Mike Amling

Automorphism isn't a problem if I'm only trying to detect that graphs
are isomorphic. However, if I want to report the node correspondence,
the automorphic nodes have to be resolved. For example two simple
isomorphic rings of nodes will have several possible valid mappings
(about 2*(N-1)). All the nodes will wind up with the same label, but I
can't just make a random mapping and expect it to be valid.

Oh, now I get it.

What I do
in this case is just assign the first pair of nodes, and then do
another hash iteration with the assigned nodes acting as start-nodes.
In the case of the rings, the rest of the nodes will then all get
unique hash values, so they can be matched up correctly. This seems to
work so far.

Is this the pairing algorithm?
1. Pair any node that has a hash value that is unique within graph 1 to the one and only node in graph 2 with that value.
2. If all nodes have been paired, stop. If no nodes have been paired, go to step 7.
3. Assign a fresh arbitrary value to each node in graph 1 that has already been paired. Assign the same value to its counterpart in graph 2.
4. Get a fresh arbitrary value for each pool of unpaired nodes that had the same hash value in step 1, and assign it to each member of the pool (in both graphs).
5. Run the hash propagation through n iterations, starting with the values assigned in steps 3 and 4, where n is the graph diameter or something.
6. If any node in graph 1 has a hash value after step 5 that is unique within its graph, go to step 1.
7. Arbitrarily pick one unpaired node from graph 1 and pair it with an arbitrary node from graph 2 that has the same hash value. Go to step 3.

I can see how one might wonder if step 7 is dangerous if reached by falling through step 6. But I think it's safe because equal hash values would be generated only for nodes that are connected to the paired part of the graph in equivalent ways.


Being able to report the correspondence is important, both in the
real-world, and to detect counter-examples that cause the algorithm to
fail. Once the actual isomorphism mapping is reported, I do a simple
check to see if it's valid. I'm hoping to catch a counter example this
way, but I'm still dealing with bugs, and it's unfortunate, but true
that I have other work to do!

One possible result from this effort so far... Even if graph
isomorphism isn't in P, I think it's not a good idea to use exact graph
isomorphism for cryptography. It seems VERY hard to generate a pair of
graphs that are difficult to match! Any ideas for generating difficult
to match graphs would be appreciated!

I'm worried about the classic Zero Knowledge proof a Hamiltonian circuit. (See the example in http://en.wikipedia.org/wiki/Zero-knowledge_proof). It looks like the article is wrong when it says "Because of the nature of the isomorphic graph and Hamiltonian cycle problems, (namely, that they are NP), Victor gains no information about the Hamiltonian cycle in G from the information revealed in each round." If graph isomorphism is in RP (as well as NP), I would hardly conclude that V is getting no knowledge about the circuit in G by being shown the circuit in H.

--Mike Amling
.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... graph and Hamiltonian cycle problems,, Victor ... If graph isomorphism is in RP (as ... about the circuit in G by being shown the circuit in H. ... the prover either sends keys to unlock only edges that form a Hamiltonian circuit or sends the permutation of the nodes that constitutes the isomorphism and keys to unlock all edges. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... exchanged is isomorphic to the original graph, which is as it should be. ... the same node hash values with the same duplicate values. ... Once the actual isomorphism mapping is reported, ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The proof that isomorphic graphs give identical hash, ... We'll be running this version of the algorithm, ... [values of each node in sorted order ]. ... value'@the same for graph G'. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... which correctly differentiates all of the examples you've ... The proof that isomorphic graphs give identical hash, ... [values of each node in sorted order ]. ... note value'@the same for graph G'. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... an accidental hash collision, I think we can get rid of any ... The algorithm is stated for an undirected graph only ... a "result" bit string, initially empty. ... For each node, assign to longhash its value, followed ...
    (sci.crypt)