Re: Need Graph Isomorphism Algorithm De-bunked

Bill Cox wrote:
I thought this forum might be a good place to post, since graph
isomorphism is commonly suggested for use in cryptography.

I've written a graph isomorphism program that determines if two graphs
are isomorphic. It runs in O(N^3).

Since graph isomorphism is a long studied problem with (AFAIK) no known
polynomial time solution, my algorithm is more than likely flawed. Any
help finding the flaws would be appreciated! The web site is

http://www.billrocks.org/ideas

First off, when you say

- For 2*D iterations, update each vertex's hash value, by hashing it with it's neighbor's hash values, and the iteration number.
- The hashing values for neighbors has to be symmetric (commutative) so that you don't need to know what order to hash them in. I just used XOR.

does that mean that you first XOR all a node's neighbors' current hashes together and then hash the result in with the node's current hash and the iteration number? XORing them seems like it loses information about pairs of neighbors that at the moment have the same hash value. How about addition? Or just concatenate the neighbors' hash values in nondecreasing order of hash value.



The original algorithm hashes for each node the sequence
node's own degree
set of neighbors' degrees
set of neighbors' sets of neighbors' degrees
....

It generates the same hash for each node of two non-isomorphic graphs if the two graphs have the same number of nodes and all the nodes on the graphs have the same degree. Coming up with two such graphs is so easy that I just did it.


The second algorithm is like the first except x is substituted for one node (call it A)'s degree. The second algorithm's calculated hash for a node B differs from the first's depending on the number of paths (and degrees of nodes along the paths and ...) from B to A as a function of path length (where path length corresponds to iteration number).
Since x is arbitrary, would it be useful to make a polynomial using an abstract x?


Does the canonical Zero-Knowledge proof of a Hamiltonian circuit use graphs for which an N**3 attack is feasible for a Verifier?

--Mike Amling
.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... together and then hash the result in with the node's current hash and ... XORing them seems like it loses information about ... pairs of neighbors that at the moment have the same hash value. ... It generates the same hash for each node of two non-isomorphic graphs ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... together and then hash the result in with the node's current hash and ... XORing them seems like it loses information about ... pairs of neighbors that at the moment have the same hash value. ... It generates the same hash for each node of two non-isomorphic graphs ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The algorithm produce a bit string from an undirected graph ... The output of isomorphic graphs is identical. ... throwing away the values and just keeping the lists. ... the hash is distinguishable from a random oracle. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... At the end of this message are three 25-vertices graphs ... the cost has raised to Ofor constant hash width; ... giving a longhash. ... The result of each "hash iteration" is the concatenation of ...
    (sci.crypt)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... I didn't describe the fix to the algorithm well at all. ... and when every vertex in both graphs have the same degree, ... no initial difference in the hash values, ... and matching vertices should wind up with ...
    (comp.theory)