Re: Need Graph Isomorphism Algorithm De-bunked

Francois Grieu wrote:
I can make a handwaving argument that if two graphs
produce the same hash, either they are isomorphic,
or two different inputs to the cryptographic hash
produced the same output during the course of the
algorithm, thus the scheme is collision-resistant.
The idea is that at the end of step j in Compute,
and assuming no collision in the cryptographic hash,
A[u] is representative of the structure of a sub-graph
encompassing at least j steps away from vertex u.

Thanks for the careful work on this! The formal description helps a
lot. The sorting of values and before hashing neighbor values is a
nice improvement (let's us stop worring about simple XOR collisions).
Also, the various speed improvements you suggest sound good for making
an actual useful algorithm. O(n^3) is too slow in practice to be
useful. If this algorithm is proven out, I'm confident a sub-O(N^2)
average-case algorithm can be developed.

I think we agree on the handwaving argument. If this could be
formalized into a convincing proof, I'd be convinced that the overall
algorithm works. I think we will very likely to fail to complete this
proof, since in reality isomorphism detection is proably
computationally hard, or somebody would have come up with a fast
algorithm by now.

So, this is where I'm stuck. I have not found a counter example graph
by hand, and I haven't been able to prove that "at the end of step j in
Compute, and assuming no collision in the cryptographic hash, A[u] is
representative of the structure of a sub-graph encompassing at least j
steps away from vertex u". Perhaps a proof by induction? I'm also not
getting much sleep, but I'll work on it.

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Then the algorithm fails. ... the hashes with universal hashes. ... there isn't a collision, the algorithm always reports the correct result. ... though the graphs are different, ...
    (sci.crypt)
  • Re: Collision in SHA-0
    ... All hash algorithms produce collisions. ... brute force attack, it is perfectly ok for any hash algorithm to ... collision, you can claim an algorithm "broken". ...
    (sci.crypt)
  • Re: Hash Collisions
    ... >algorithm may generate is finite, we know that no hash algorithm can be ... is the significance of finding any single random collision ... Greg Rose ...
    (sci.crypt)
  • Re: Whats the additional value of EnumMap ?
    ... >> You mean, exactly like HashMap does? ... > He probably means the algorithm is optimized for never having a hash ... > collision, so it never has to check the list of values at each bucket. ...
    (comp.lang.java.programmer)
  • Re: Trailing bytes in an OS-X file
    ... the probablilty of a "collision" is relatively big. ... Relative to a good cryptographic hash perhaps, ... chance of virtually any other explanation of the problem very small. ...
    (uk.comp.sys.mac)