Editing Zero-knowledge proof (section)

== Practical examples ==

=== Discrete log of a given value ===

These ideas can be applied to a more realistic cryptography application. Peggy wants to prove to Victor that she knows the [[discrete logarithm]] of a given value in a given [[group theory|group]].<ref>{{cite book |first1=David |last1=Chaum |first2=Jan-Hendrik |last2=Evertse |first3=Jeroen |last3=van de Graaf |title=Advances in Cryptology — EUROCRYPT '87 |chapter=An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations |volume=304 |pages=127–141 |doi=10.1007/3-540-39118-5_13 |series=Lecture Notes in Computer Science |year=1988 |isbn=978-3-540-19102-5 }}</ref>

For example, given a value {{Mvar|y}}, a large [[prime number|prime]] {{Mvar|p}}, and a generator <math>g</math>, she wants to prove that she knows a value {{Mvar|x}} such that {{Math|''g''<sup>''x''</sup> &equiv; ''y'' (mod ''p'')}}, without revealing {{Mvar|x}}. Indeed, knowledge of {{Mvar|x}} could be used as a proof of identity, in that Peggy could have such knowledge because she chose a random value {{Mvar|x}} that she did not reveal to anyone, computed {{Math|1=''y'' = ''g''<sup>''x''</sup> mod ''p''}}, and distributed the value of {{Mvar|y}} to all potential verifiers, such that at a later time, proving knowledge of {{Mvar|x}} is equivalent to proving identity as Peggy.

The protocol proceeds as follows: in each round, Peggy generates a random number {{Mvar|r}}, computes {{Math|1=''C'' = ''g''<sup>''r''</sup> mod ''p''}} and discloses this to Victor. After receiving {{Mvar|C}}, Victor randomly issues one of the following two requests: he either requests that Peggy discloses the value of {{Mvar|r}}, or the value of {{Math|(''x'' + ''r'') mod (''p'' &minus; 1)}}.

Victor can verify either answer; if he requested {{Mvar|r}}, he can then compute {{Math|''g''<sup>''r''</sup> mod ''p''}} and verify that it matches {{Mvar|C}}. If he requested {{Math|(''x'' + ''r'') mod (''p'' &minus; 1)}}, then he can verify that {{Mvar|C}} is consistent with this, by computing {{Math|''g''<sup>(''x'' + ''r'') mod (''p'' &minus; 1)</sup> mod ''p''}} and verifying that it matches {{Math|(''C'' &middot; ''y'') mod ''p''}}. If Peggy indeed knows the value of {{Mvar|x}}, then she can respond to either one of Victor's possible challenges.

If Peggy knew or could guess which challenge Victor is going to issue, then she could easily cheat and convince Victor that she knows {{Mvar|x}} when she does not: if she knows that Victor is going to request {{Mvar|r}}, then she proceeds normally: she picks {{Mvar|r}}, computes {{Math|1=''C'' = ''g''<sup>''r''</sup> mod ''p''}}, and discloses {{Mvar|C}} to Victor; she will be able to respond to Victor's challenge. On the other hand, if she knows that Victor will request {{Math|(''x'' + ''r'') mod (''p'' &minus; 1)}}, then she picks a random value {{Math|''r''&prime;}}, computes {{Math|''C''&prime; &equiv; ''g''<sup>''r''&prime;</sup> &middot; (''g''<sup>''x''</sup>)<sup>&minus;1</sup> mod ''p''}}, and discloses {{Math|''C''&prime;}} to Victor as the value of {{Mvar|C}} that he is expecting. When Victor challenges her to reveal {{Math|(''x'' + ''r'') mod (''p'' &minus; 1)}}, she reveals {{Math|''r''&prime;}}, for which Victor will verify consistency, since he will in turn compute {{Math|''g''<sup>''r''&prime;</sup> mod ''p''}}, which matches {{Math|''C''&prime; &middot; ''y''}}, since Peggy multiplied by the [[modular multiplicative inverse]] of {{Mvar|y}}.

However, if in either one of the above scenarios Victor issues a challenge other than the one she was expecting and for which she manufactured the result, then she will be unable to respond to the challenge under the assumption of infeasibility of solving the discrete log for this group. If she picked {{Mvar|r}} and disclosed {{Math|1=''C'' = ''g''<sup>''r''</sup> mod ''p''}}, then she will be unable to produce a valid {{Math|(''x'' + ''r'') mod (''p'' &minus; 1)}} that would pass Victor's verification, given that she does not know {{Mvar|x}}. And if she picked a value {{Math|''r''&prime;}} that poses as {{Math|(''x'' + ''r'') mod (''p'' &minus; 1)}}, then she would have to respond with the discrete log of the value that she disclosed{{snd}} but Peggy does not know this discrete log, since the value {{Mvar|C}} she disclosed was obtained through arithmetic with known values, and not by computing a power with a known exponent.

Thus, a cheating prover has a 0.5 probability of successfully cheating in one round. By executing a large-enough number of rounds, the probability of a cheating prover succeeding can be made arbitrarily low.

To show that the above interactive proof gives zero knowledge other than the fact that Peggy knows {{Mvar|x}}, one can use similar arguments as used in the above proof of completeness and soundness. Specifically, a simulator, say Simon, who does not know {{Mvar|x}}, can simulate the exchange between Peggy and Victor by the following procedure. Firstly, Simon randomly flips a fair coin. If the result is "heads", then he picks a random value {{Mvar|r}}, computes {{Math|1=''C'' = ''g''<sup>''r''</sup> mod ''p''}}, and discloses {{Mvar|C}} as if it is a message from Peggy to Victor. Then Simon also outputs a message "request the value of {{Mvar|r}}" as if it is sent from Victor to Peggy, and immediately outputs the value of {{Mvar|r}} as if it is sent from Peggy to Victor. A single round is complete. On the other hand, if the coin flipping result is "tails", then Simon picks a random number {{Math|''r''&prime;}}, computes {{Math|1=''C''&prime; = ''g''<sup>''r''&prime;</sup> &middot; ''y''<sup>&minus;1</sup> mod ''p''}}, and discloses {{Math|''C''&prime;}} as if it is a message from Peggy to Victor. Then Simon outputs "request the value of {{Math|(''x'' + ''r'') mod (''p'' &minus; 1)}}" as if it is a message from Victor to Peggy. Finally, Simon outputs the value of {{Math|''r''&prime;}} as if it is the response from Peggy back to Victor. A single round is complete. By the previous arguments when proving the completeness and soundness, the interactive communication simulated by Simon is indistinguishable from the true correspondence between Peggy and Victor. The zero-knowledge property is thus guaranteed.

=== 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.