Re: Need Graph Isomorphism Algorithm De-bunked

Bill Cox wrote:
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.

I agree. There is no way I would use graph isomorphism as a
hard-problem meant to secure important data. Somebody, please, show me
two graphs which are hard to compare!

The Wikipedia article may have distorted the ZK proof algorithm. In the ZK proof version at http://citeseer.ist.psu.edu/cachedpage/320165/25, the prover does not send the allegedly isomorphic graph unconditionally, but instead sends commitments of its edges. Then after the verifier responds, 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.

--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. ...
    (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, ... I'm worried about the classic Zero Knowledge proof a Hamiltonian circuit. ...
    (sci.crypt)
  • Re: number combinations of components
    ... >>>yeah, if one considers them distinct it would be 8. ... The background for this is graph theory, where a graph G consists of a ... but there are many cases where the phase will produce a circuit that ... > I want all the ways to compose these functions. ...
    (sci.math)
  • Re: Using the RM for ADTs
    ... I think we can generalise this to the task of representing ... equivalence relation defined by isomorphism ... in which all values are attribute values of circuit elements, ... different database values represent isomorphic circuits. ...
    (comp.databases.theory)
  • 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)