Editing Zero-knowledge proof (section)

=== Hamiltonian cycle for a large graph ===
The following scheme is due to [[Manuel Blum]].<ref name="blum86">{{cite journal |first=Manuel |last=Blum |title=How to Prove a Theorem So No One Else Can Claim It |journal=ICM Proceedings |pages=1444–1451 |year=1986 |citeseerx=10.1.1.469.9048 |url=http://euler.nmt.edu/~brian/students/pope.pdf |url-status=live |archiveurl=https://web.archive.org/web/20230103032937/http://euler.nmt.edu/~brian/students/pope.pdf |archivedate=January 3, 2023 }}</ref>

In this scenario, Peggy knows a [[Hamiltonian path|Hamiltonian cycle]] for a large [[Graph (discrete mathematics)|graph]] {{mvar|G}}. Victor knows {{mvar|G}} but not the cycle (e.g., Peggy has generated {{mvar|G}} and revealed it to him.) Finding a Hamiltonian cycle given a large graph is believed to be computationally infeasible, since its corresponding decision version is known to be [[NP-complete]]. Peggy will prove that she knows the cycle without simply revealing it (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 {{mvar|H}}, a graph which is [[graph isomorphism|isomorphic]] to {{mvar|G}} (that is, {{mvar|H}} is just like {{mvar|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 {{mvar|G}} then she also must know one for {{mvar|H}}.
* Peggy commits to {{mvar|H}}. She could do so by using a cryptographic [[commitment scheme]]. Alternatively, she could number the vertices of {{mvar|H}}. Next, for each edge of {{mvar|H}}, on a small piece of paper, she writes down the two vertices that the edge joins. Then she puts all these pieces of paper face down on a table. The purpose of this commitment is that Peggy is not able to change {{mvar|H}} while, at the same time, Victor has no information about {{mvar|H}}.
* Victor then randomly chooses one of two questions to ask Peggy. He can either ask her to show the isomorphism between {{mvar|H}} and {{mvar|G}} (see [[graph isomorphism problem]]), or he can ask her to show a Hamiltonian cycle in {{mvar|H}}.
* If Peggy is asked to show that the two graphs are isomorphic, then she first uncovers all of {{mvar|H}} (e.g. by turning over all pieces of papers that she put on the table) and then provides the vertex translations that map {{mvar|G}} to {{mvar|H}}. Victor can verify that they are indeed isomorphic.
* If Peggy is asked to prove that she knows a Hamiltonian cycle in {{mvar|H}}, then she translates her Hamiltonian cycle in {{mvar|G}} onto {{mvar|H}} and only uncovers the edges on the Hamiltonian cycle. That is, Peggy only turns over exactly {{Math|{{abs|''V''(''G'')}}}} of the pieces of paper that correspond to the edges of the Hamiltonian cycle, while leaving the rest still face-down. This is enough for Victor to check that {{mvar|H}} does indeed contain a Hamiltonian cycle.

It is important that the commitment to the graph be such that Victor can verify, in the second case, that the cycle is really made of edges from {{mvar|H}}. This can be done by, for example, committing to every edge (or lack thereof) separately.

==== Completeness ====
If Peggy does know a Hamiltonian cycle in {{mvar|G}}, then she can easily satisfy Victor's demand for either the graph isomorphism producing {{mvar|H}} from {{mvar|G}} (which she had committed to in the first step) or a Hamiltonian cycle in {{mvar|H}} (which she can construct by applying the isomorphism to the cycle in {{mvar|G}}).

==== Zero-knowledge ====
Peggy's answers do not reveal the original Hamiltonian cycle in {{mvar|G}}. In each round, Victor will learn only {{mvar|H}}'s isomorphism to {{mvar|G}} or a Hamiltonian cycle in {{mvar|H}}. He would need both answers for a single {{mvar|H}} to discover the cycle in {{mvar|G}}, so the information remains unknown as long as Peggy can generate a distinct {{mvar|H}} every round. If Peggy does not know of a Hamiltonian cycle in {{mvar|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 {{mvar|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 {{mvar|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 {{mvar|G}} from the information revealed in each round.

==== Soundness ====
If Peggy does not know the information, then she can guess which question Victor will ask and generate either a graph isomorphic to {{mvar|G}} or a Hamiltonian cycle for an unrelated graph, but since she does not know a Hamiltonian cycle for {{mvar|G}}, she cannot do both. With this guesswork, her chance of fooling Victor is {{math|2<sup>−{{var|n}}</sup>}}, where {{mvar|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.