Re: Need Graph Isomorphism Algorithm De-bunked

Third try at a paraphrase/modification/improvement/
simplification/perversion of Bill Cox's algorithm.


We want a computable, computationally collision and
preimage resistant hash function accepting a graph as
input, that is invariant under graph isomorphism
(for any graph, exchanging any vertices leaves the hash
unchanged); implying that computing and comparing two such
hashes is computationally enough to test for graph
isomorphism.

A graph G with n vertices will be expressed as an n*n bit
matrix, G[u,v] set meaning that an edge exists from
vertex u to vertex v.


Select a cryptographic hash with the desired output
width w, supposed collision and preimage resistant,
say SHA-w with w=256.

Have two arrays A and B of n variables each w-bit wide,
and an array P of n variables each ceil(log2(n))-bit wide.


Setup:
- for all u, 0<=u<n
- - set A[u] = G[u,u]
- - set P[u] = u
- - sort P such that A[P[u]] is non-decreasing

Compute:
- for all j, 0<j<n
- - for all u, 0<=u<n
- - - initialize the cryptographic hash
- - - enter A[u] into the cryptographic hash
- - - for all v, 0<=v<n, v!=u
- - - - if G[P[u],P[v]] is set
- - - - - enter A[v] into the cryptographic hash
- - - set B[u] to the result of the cryptographic hash
- - set A = B
- - sort P such that A[P[u]] is non-decreasing

Finish:
- initialize the cryptographic hash
- for all u, 0<=u<n
- - enter A[u] into the cryptographic hash
- output the result of the cryptographic hash


This graph hash is invariant under graph isomorphism
(by induction, corresponding vertices in two isomorphic
graphs have equal values of corresponding A[u] across
2 parallel runs of the algorithm)

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.

Once collision resistance is proved, preimage
resistance is inherited from the cryptographic hash,
merely by considering the Finish part.

The cost of the computation is O(n^3 * w)


In practice it seems that the cost can be reduced
greatly with a few tricks outlined below
- when sorting P during Compute, only sort the subintervals
where A[P[u]] was constant in the previous sort
- rather than entering in the cryptographic hash several
identical values of A belonging to the same subinterval
of P such that A[P[u]] was constant in the previous
sort, enter the concatenation of this value of A and
the number of such identical values on ceil(log2(n)) bits
- perform only d iterations of the outer loop in Compute,
where d is the maximum number of edges along the shortest
path between any two distinct connected vertices
- if more than half of the bits are set in G, first
complement G, compute the hash, then complement the
overall result
- if the graph is undirected, that is when G is symetric
along the diagonal, change "0<=v<n, v!=u" to "0<=v<u"


François Grieu

Disclaimer: I badly need sleep, this might be all wrong.
.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... to the order of the inputs, but still collision ... We make use of a cryptographic hash function ... Compute cryptographic hash of the n values A ... Result is unchanged under graph isomorphism. ...
    (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)
  • 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)