Zero-knowledge proof

We can extend these ideas to a more realistic cryptography application. In this scenario, Peggy knows a Hamiltonian cycle for a large graph, G. Victor knows G but not the cycle (e.g., Peggy has generated G and revealed it to him.) Peggy will prove that she knows the cycle without revealing it. A Hamiltonian cycle in a graph is just one way to implement a zero knowledge proof; in fact any NP-complete problem can be used, as well as some other difficult problems such as factoring.^[2] However, Peggy does not want to simply reveal the Hamiltonian cycle or any other information to Victor; she wishes to keep the cycle secret (perhaps Victor is interested in buying it but wants verification first, or maybe Peggy is the only one who knows this information and is proving her identity to Victor).

To show that Peggy knows this Hamiltonian cycle, she and Victor play several rounds of a game.

• At the beginning of each round, Peggy creates H, an isomorphic graph to G (i.e. H is just like G except that all the vertices have different names). Since it is trivial to translate a Hamiltonian cycle between isomorphic graphs with known isomorphism, if Peggy knows a Hamiltonian cycle for G she also must know one for H.
• Peggy commits to H. She could do so by using a cryptographic commitment scheme. Alternatively, she could number the vertices of H, then for each edge of H write a small piece of paper containing the two vertices of the edge and then put these pieces of paper upside down on a table. The purpose of this commitment is that Peggy is not able to change H while at the same time Victor has no information about H.
• Victor then randomly chooses one of two questions to ask Peggy. He can either ask her to show the isomorphism betweenH and G (see graph isomorphism problem), or he can ask her to show a Hamiltonian cycle in H.
• If Peggy is asked to show that the two graphs are isomorphic, she first uncovers all of H (e.g. by turning all pieces of papers that she put on the table) and then provides the vertex translations that map G to H. Victor can verify that they are indeed isomorphic.
• If Peggy is asked to prove that she knows a Hamiltonian cycle in H, she translates her Hamiltonian cycle in G onto H and only uncovers the edges on the Hamiltonian cycle. This is enough for Victor to check that H does indeed contain a Hamiltonian cycle.

Completeness

If Peggy is honest, she can easily satisfy Victor’s demand for either a graph isomorphism (which she has) or a Hamiltonian cycle (which she can construct by applying the isomorphism to the cycle in G).

Zero-Knowledge

Peggy’s answers do not reveal the original Hamiltonian cycle in G. Each round, Victor will learn only H’s isomorphism to G or a Hamiltonian cycle in H. He would need both answers for a single H to discover the cycle in G, so the information remains unknown as long as Peggy can generate a unique H every round. If Peggy does not know of a Hamiltonian Cycle in G, but somehow knew in advance what Victor would ask to see each round then she could cheat. For example, if Peggy knew ahead of time that Victor would ask to see the Hamiltonian Cycle in H then she could generate a Hamiltonian cycle for an unrelated graph. Similarly, if Peggy knew in advance that Victor would ask to see the isomorphism then she could simply generate an isomorphic graph H (in which she also does not know a Hamiltonian Cycle). Victor could simulate the protocol by himself (without Peggy) because he knows what he will ask to see. Therefore, Victor gains no information about the Hamiltonian cycle in G from the information revealed in each round.

Soundness

If Peggy does not know the information, she can guess which question Victor will ask and generate either a graph isomorphic to G or a Hamiltonian cycle for an unrelated graph, but since she does not know a Hamiltonian cycle for G she cannot do both. With this guesswork, her chance of fooling Victor is 2⁻ⁿ, where n is the number of rounds. For all realistic purposes, it is infeasibly difficult to defeat a zero knowledge proof with a reasonable number of rounds in this way.