Overview

In cryptography, a zero-knowledge proof (also known as a ZK proof or ZKP) is a protocol in which one party (the prover) can convince another party (the verifier) that some given statement is true, without conveying to the verifier any information beyond the mere fact of that statement's truth. The intuition behind the nontriviality of zero-knowledge proofs is that it is trivial to prove possession of the relevant information simply by revealing it; the hard part is to prove this possession without revealing this information (or any aspect of it whatsoever).

In light of the fact that one should be able to generate a proof of some statement only when in possession of certain secret information connected to the statement, the verifier, even after having become convinced of the statement's truth by means of a zero-knowledge proof, should nonetheless remain unable to prove the statement to further third parties.

Zero-knowledge proofs can be interactive, meaning that the prover and verifier exchange messages according to some protocol, or noninteractive, meaning that the verifier is convinced by a single prover message and no other communication is needed. In the standard model, interaction is required, except for trivial proofs of BPP problems. In the common random string and random oracle models, non-interactive zero-knowledge proofs exist. The Fiat–Shamir heuristic can be used to transform certain interactive zero-knowledge proofs into noninteractive ones.

The red card proof

One example of a math-free zero-knowledge proof is if Peggy wants to prove to Victor that she has drawn a red card from a standard deck of 52 playing cards, without revealing which specific red card she holds. Victor observes Peggy draw a card at random from the shuffled deck, but she keeps the card face-down so he cannot see it.

To prove her card is red without revealing its identity, Peggy takes the remaining 51 cards from the deck and systematically shows Victor all 26 black cards (the 13 spades and 13 clubs) one by one, placing them face-up on the table. Since a standard deck contains exactly 26 red cards and 26 black cards, and Peggy has demonstrated that all the black cards remain in the deck, Victor can conclude with certainty that Peggy's hidden card must be red.

This proof is zero-knowledge because Victor learns only that Peggy's card is red, but gains no information about whether it is a heart or diamond, or which specific red card she holds. The proof would be equally convincing whether Peggy held the Ace of Hearts or the Two of Diamonds. Furthermore, even if the interaction were recorded, the recording would not reveal Peggy's specific card to future observers, maintaining the zero-knowledge property.

Where's Waldo

Another well-known example of a zero-knowledge proof is the "Where's Waldo" example. In this example, the prover has a page from a Where's Waldo? children's book, which shows many hundreds of cartoon people, where only one of them is the visually distinctive character of Waldo. The prover wants to prove to the verifier that they know where Waldo is on the page, without revealing his location to the verifier.

The prover starts by taking a large black board with a small hole in it, the size of Waldo. 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 Waldo is in the hole.

The verifier can now look through the hole and see Waldo, but cannot see any other part of the page. Therefore, the prover has proven to the verifier that they know where Waldo is, without revealing any other information about his location.

The Ali Baba cave

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". The two parties in the zero-knowledge proof story are Peggy as the prover of the statement, and 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 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.

External observation

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.