Editing Zero-knowledge proof (section)

== Abstract examples ==
=== The Ali Baba cave ===
{{multiple image
| align             = right
| direction         = vertical
| header            = 
| width             = 150
| image1            = Zkip alibaba1.png
| caption1          = Peggy randomly takes either path A or B, while Victor waits outside.
| image2            = Zkip alibaba2.png
| caption2          = Victor chooses an exit path.
| image3            = Zkip alibaba3.png
| caption3          = Peggy reliably appears at the exit Victor names.
}}

There is a well-known story presenting the fundamental ideas of zero-knowledge proofs, first published in 1990 by [[Jean-Jacques Quisquater]] and others in their paper "How to Explain Zero-Knowledge Protocols to Your Children".<ref>{{cite book |first1=Jean-Jacques |last1=Quisquater |first2=Louis C. |last2=Guillou |first3=Thomas A. |last3=Berson |title=Advances in Cryptology — CRYPTO' 89 Proceedings |chapter=How to Explain Zero-Knowledge Protocols to Your Children |volume=435 |pages=628–631 |year=1990 |url=http://www.cs.wisc.edu/~mkowalcz/628.pdf |doi=10.1007/0-387-34805-0_60 |series=Lecture Notes in Computer Science |isbn=978-0-387-97317-3 }}</ref> The two parties in the zero-knowledge proof story are [[Alice and Bob#Cast of characters|Peggy]] as the prover of the statement, and [[Alice and Bob#Cast of characters|Victor]], the verifier of the statement.

In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general.

They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path.

However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path by which she had entered. Since Victor would choose A or B at random, she would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would be reduced to 1 in 2<sup>20</sup>, or 9.54{{times}}10<sup>−7</sup>.

Thus, if Peggy repeatedly appears at the exit Victor names, then he can conclude that it is extremely probable that Peggy does, in fact, know the secret word.

One side note with respect to third-party observers: even if Victor is wearing a hidden camera that records the whole transaction, the only thing the camera will record is in one case Victor shouting "A!" and Peggy appearing at A or in the other case Victor shouting "B!" and Peggy appearing at B. A recording of this type would be trivial for any two people to fake (requiring only that Peggy and Victor agree beforehand on the sequence of As and Bs that Victor will shout). Such a recording will certainly never be convincing to anyone but the original participants. In fact, even a person who was present as an observer at the original experiment should be unconvinced, since Victor and Peggy could have orchestrated the whole "experiment" from start to finish.

Further, if Victor chooses his As and Bs by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later. Thus, although this does not reveal the secret word to Victor, it does make it possible for Victor to convince the world in general that Peggy has that knowledge—counter to Peggy's stated wishes. However, digital cryptography generally "flips coins" by relying on a [[pseudo-random number generator]], which is akin to a coin with a fixed pattern of heads and tails known only to the coin's owner. If Victor's coin behaved this way, then again it would be possible for Victor and Peggy to have faked the experiment, so using a pseudo-random number generator would not reveal Peggy's knowledge to the world in the same way that using a flipped coin would.

Peggy could prove to Victor that she knows the magic word, without revealing it to him, in a single trial. If both Victor and Peggy go together to the mouth of the cave, Victor can watch Peggy go in through A and come out through B. This would prove with certainty that Peggy knows the magic word, without revealing the magic word to Victor. However, such a proof could be observed by a third party, or recorded by Victor and such a proof would be convincing to anybody. In other words, Peggy could not refute such proof by claiming she colluded with Victor, and she is therefore no longer in control of who is aware of her knowledge.

=== Two balls and the colour-blind friend ===

Imagine Victor is red-green [[color blindness|colour-blind]] (while Peggy is not) and Peggy has two balls: one red and one green, but otherwise identical. To Victor, the balls seem completely identical. Victor is skeptical that the balls are actually distinguishable. Peggy wants to ''prove to Victor that the balls are in fact differently coloured'', but nothing else. In particular, Peggy does not want to reveal which ball is the red one and which is the green.

Here is the proof system: Peggy gives the two balls to Victor and he puts them behind his back. Next, he takes one of the balls and brings it out from behind his back and displays it. He then places it behind his back again and then chooses to reveal just one of the two balls, picking one of the two at random with equal probability. He will ask Peggy, "Did I switch the ball?" This whole procedure is then repeated as often as necessary.

By looking at the balls' colours, Peggy can, of course, say with certainty whether or not he switched them. On the other hand, if the balls were the same colour and hence indistinguishable, Peggy's ability to determine whether a switch occurred would be no better than random guessing. Since the probability that Peggy would have randomly succeeded at identifying each switch/non-switch is 50%, the probability of having randomly succeeded at ''all'' switch/non-switches approaches zero.

Over multiple trials, the success rate would [[Law of large numbers|statistically converge]] to 50%, and Peggy could not achieve a performance significantly better than chance. If Peggy and Victor repeat this "proof" multiple times (e.g. 20 times), Victor should become convinced that the balls are indeed differently coloured.

The above proof is ''zero-knowledge'' because Victor never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.<ref>{{Cite news|url=https://www.linkedin.com/pulse/demonstrate-how-zero-knowledge-proofs-work-without-using-chalkias|title=Demonstrate how Zero-Knowledge Proofs work without using maths|last=Chalkias|first=Konstantinos|work=CordaCon 2017|access-date=2017-09-13|language=en}}</ref>

=== Where's Wally ===

One well-known example of a zero-knowledge proof is the "Where's Wally" example. In this example, the prover wants to prove to the verifier that they know where Wally is on a page in a ''[[Where's Wally?]]'' book, without revealing his location to the verifier.<ref name=Murtagh>{{cite news
  | last         = Murtagh
  | first        = Jack  
  | date         =  July 1, 2023
  | title        = Where's Wally? How to Mathematically Prove You Found Him without Revealing Where He Is
  | url          = https://www.scientificamerican.com/article/wheres-waldo-how-to-prove-you-found-him-without-revealing-where-he-is/
  | work         = [[Scientific American]]
  | access-date  = 2023-10-02
}}</ref>

The prover starts by taking a large black board with a small hole in it, the size of Wally. The board is twice the size of the book in both directions, so the verifier cannot see where on the page the prover is placing it. The prover then places the board over the page so that Wally is in the hole.<ref name=Murtagh/>

The verifier can now look through the hole and see Wally, but cannot see any other part of the page. Therefore, the prover has proven to the verifier that they know where Wally is, without revealing any other information about his location.<ref name=Murtagh/>

This example is not a perfect zero-knowledge proof, because the prover does reveal some information about Wally's location, such as his body position. However, it is a decent illustration of the basic concept of a zero-knowledge proof.