Re: Need Graph Isomorphism Algorithm De-bunked

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!

.

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, ... I'm worried about the classic Zero Knowledge proof a Hamiltonian circuit. ...
    (sci.crypt)
  • Re: Continued training with octahedron.
    ... I showed icosahedral graph by octahedron. ... There is Hamiltonian cycle count 2560 in the below table of link. ... this is equal to edge's cycle in octahedron. ... One ant is on a vertex of icosahedron. ...
    (sci.math)
  • 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: Continued training with octahedron.
    ... I showed icosahedral graph by octahedron. ... There is Hamiltonian cycle count 2560 in the below table of link. ... this is equal to edge's cycle in octahedron. ... One ant is on a vertex of icosahedron. ...
    (sci.math)