Zero-knowledge proof

Peggy randomly takes either path A or B, while Victor waits outside

Victor chooses an exit path

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".[7] The two parties in the in a 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 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²⁰, or 9.56 × 10⁻⁷.

Thus, if Peggy repeatedly appears at the exit Victor names, 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 A's and B's 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 would be unconvinced, since Victor and Peggy might have orchestrated the whole "experiment" from start to finish.

Further, if Victor chooses his A's and B's 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.

Notice that 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.

Imagine your friend "Victor" is red-green colour-blind (while you are not) and you have 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. You want to prove to Victor that the balls are in fact differently coloured, but nothing else. In particular, you do not want to reveal which ball is the red one and which is the green.

Here is the proof system. You give 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 you, "Did I switch the ball?" This whole procedure is then repeated as often as necessary.

By looking at the balls' colours, you 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, there is no way you could guess correctly with probability higher than 50%.

Since the probability that you 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 ("soundness"). If you and your friend repeat this "proof" multiple times (e.g. 20 times), your friend should become convinced ("completeness") that the balls are indeed differently coloured.

The above proof is zero-knowledge because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.[8]

One well-known example of a zero-knowledge proof is the "Where's Waldo" example. In this example, the prover wants to prove to the verifier that they know where Waldo is on a page in a Where's Waldo? book, without revealing his location to the verifier.[9]

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.[9]

The verifier can now look through the hole and see Waldo, but they 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.[9]

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

We can apply these ideas to a more realistic cryptography application. Peggy wants to prove to Victor that she knows the discrete log of a given value in a given group.[11]

For example, given a value ${\displaystyle y}$, a large prime ${\displaystyle p}$ and a generator ${\displaystyle g}$, she wants to prove that she knows a value ${\displaystyle x}$ such that ${\displaystyle g^{x}{\bmod {p}}=y}$, without revealing ${\displaystyle x}$. Indeed, knowledge of ${\displaystyle x}$ could be used as a proof of identity, in that Peggy could have such knowledge because she chose a random value ${\displaystyle x}$ that she didn't reveal to anyone, computed ${\displaystyle y=g^{x}{\bmod {p}}}$ and distributed the value of ${\displaystyle y}$ to all potential verifiers, such that at a later time, proving knowledge of ${\displaystyle x}$ is equivalent to proving identity as Peggy.

The protocol proceeds as follows: in each round, Peggy generates a random number ${\displaystyle r}$, computes ${\displaystyle C=g^{r}{\bmod {p}}}$ and discloses this to Victor. After receiving ${\displaystyle C}$, Victor randomly issues one of the following two requests: he either requests that Peggy discloses the value of ${\displaystyle r}$, or the value of ${\displaystyle (x+r){\bmod {(p-1)}}}$.

Victor can verify either answer; if he requested ${\displaystyle r}$, he can then compute ${\displaystyle g^{r}{\bmod {p}}}$ and verify that it matches ${\displaystyle C}$. If he requested ${\displaystyle (x+r){\bmod {(p-1)}}}$, he can verify that ${\displaystyle C}$ is consistent with this, by computing ${\displaystyle g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}}$ and verifying that it matches ${\displaystyle (C\cdot y){\bmod {p}}}$. If Peggy indeed knows the value of ${\displaystyle x}$, 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 ${\displaystyle x}$ when she does not: if she knows that Victor is going to request ${\displaystyle r}$, then she proceeds normally: she picks ${\displaystyle r}$, computes ${\displaystyle C=g^{r}{\bmod {p}}}$ and discloses ${\displaystyle C}$ to Victor; she will be able to respond to Victor's challenge. On the other hand, if she knows that Victor will request ${\displaystyle (x+r){\bmod {(p-1)}}}$, then she picks a random value ${\displaystyle r'}$, computes ${\displaystyle C'=g^{r'}\cdot \left(g^{x}\right)^{-1}{\bmod {p}}}$, and discloses ${\displaystyle C'}$ to Victor as the value of ${\displaystyle C}$ that he is expecting. When Victor challenges her to reveal ${\displaystyle (x+r){\bmod {(p-1)}}}$, she reveals ${\displaystyle r'}$, for which Victor will verify consistency, since he will in turn compute ${\displaystyle g^{r'}{\bmod {p}}}$, which matches ${\displaystyle C'\cdot y}$, since Peggy multiplied by the modular multiplicative inverse of ${\displaystyle 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 ${\displaystyle r}$ and disclosed ${\displaystyle C=g^{r}{\bmod {p}}}$, then she will be unable to produce a valid ${\displaystyle (x+r){\bmod {(p-1)}}}$ that would pass Victor's verification, given that she does not know ${\displaystyle x}$. And if she picked a value ${\displaystyle r'}$ that poses as ${\displaystyle (x+r){\bmod {(p-1)}}}$, then she would have to respond with the discrete log of the value that she disclosed – but Peggy does not know this discrete log, since the value 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 the ${\displaystyle x}$ value, one can use similar arguments as used in the above proof of completeness and soundness. Specifically, a simulator, say Simon, who does not know the ${\displaystyle x}$ value, can simulate the exchange between Peggy and Victor by the following procedure. Firstly, Simon randomly flips a fair coin. If the result is "head", he picks a random value ${\displaystyle r}$, computes ${\displaystyle C=g^{r}{\bmod {p}}}$, and discloses ${\displaystyle C}$ as if it is a message from Peggy to Victor. Then Simon also outputs a message "request the value of ${\displaystyle r}$" as if it is sent from Victor to Peggy, and immediately outputs the value of ${\displaystyle 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 "tail", Simon picks a random number ${\displaystyle r'}$, computes ${\displaystyle C'=g^{r'}\cdot \left(y\right)^{-1}{\bmod {p}}}$, and discloses ${\displaystyle C'}$ as if it is a message from Peggy to Victor. Then Simon outputs "request the value of ${\displaystyle (x+r){\bmod {(p-1)}}}$" as if it is a message from Victor to Peggy. Finally, Simon outputs the value of ${\displaystyle r'}$ 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.

Peggy proves to know the value of x (for example her password).

1. Peggy and Victor agree on a prime ${\displaystyle p}$ and a generator ${\displaystyle g}$ of the multiplicative group of the field ${\displaystyle \mathbb {Z} _{p}}$.
2. Peggy calculates the value ${\displaystyle y=g^{x}{\bmod {p}}}$ and transfers the value to Victor.
3. The following two steps are repeated a (large) number of times.
   1. Peggy repeatedly picks a random value ${\displaystyle r\in U[0,p-2]}$ and calculates ${\displaystyle C=g^{r}{\bmod {p}}}$. She transfers the value ${\displaystyle C}$ to Victor.
   2. Victor asks Peggy to calculate and transfer either the value ${\displaystyle (x+r){\bmod {(p-1)}}}$ or the value ${\displaystyle r}$. In the first case Victor verifies ${\displaystyle (C\cdot y){\bmod {p}}\equiv g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}}$. In the second case he verifies ${\displaystyle C\equiv g^{r}{\bmod {p}}}$.

The value ${\displaystyle (x+r){\bmod {(}}p-1)}$ can be seen as the encrypted value of ${\displaystyle x{\bmod {(}}p-1)}$. If ${\displaystyle r}$ is truly random, equally distributed between zero and ${\displaystyle (p-2)}$, this does not leak any information about ${\displaystyle x}$ (see one-time pad).

The following scheme is due to Manuel Blum.[12]

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.) 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 H, a graph which is isomorphic 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. Next, for each edge of 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 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 between H 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 over 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. That is, Peggy only turns over exactly ${\displaystyle |E(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 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 H. This can be done by, for example, committing to every edge (or lack thereof) separately.

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

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

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.

Research in zero-knowledge proofs has been motivated by authentication systems where one party wants to prove its identity to a second party via some secret information (such as a password) but doesn't want the second party to learn anything about this secret. This is called a "zero-knowledge proof of knowledge". However, a password is typically too small or insufficiently random to be used in many schemes for zero-knowledge proofs of knowledge. A zero-knowledge password proof is a special kind of zero-knowledge proof of knowledge that addresses the limited size of passwords.

In April 2015, the one-out-of-many proofs protocol (a Sigma protocol) was introduced.[14] In August 2021, Cloudflare, an American web infrastructure and security company decided to use the one-out-of-many proofs mechanism for private web verification using vendor hardware.[15]

One of the uses of zero-knowledge proofs within cryptographic protocols is to enforce honest behavior while maintaining privacy. Roughly, the idea is to force a user to prove, using a zero-knowledge proof, that its behavior is correct according to the protocol.[16][17] Because of soundness, we know that the user must really act honestly in order to be able to provide a valid proof. Because of zero knowledge, we know that the user does not compromise the privacy of its secrets in the process of providing the proof.

In 2016, the Princeton Plasma Physics Laboratory and Princeton University demonstrated a technique that may have applicability to future nuclear disarmament talks. It would allow inspectors to confirm whether or not an object is indeed a nuclear weapon without recording, sharing or revealing the internal workings which might be secret.[18]

Zero-knowledge proofs were applied in the Zerocoin and Zerocash protocols, which culminated in the birth of Zcoin[19] (later rebranded as Firo in 2020)[20] and Zcash cryptocurrencies in 2016. Zerocoin has a built-in mixing model that does not trust any peers or centralised mixing providers to ensure anonymity.[19] Users can transact in a base currency and can cycle the currency into and out of Zerocoins.[21] The Zerocash protocol uses a similar model (a variant known as a non-interactive zero-knowledge proof)[22] except that it can obscure the transaction amount, while Zerocoin cannot. Given significant restrictions of transaction data on the Zerocash network, Zerocash is less prone to privacy timing attacks when compared to Zerocoin. However, this additional layer of privacy can cause potentially undetected hyperinflation of Zerocash supply because fraudulent coins cannot be tracked.[19][23]

In 2018, Bulletproofs were introduced. Bulletproofs are an improvement from non-interactive zero-knowledge proof where trusted setup is not needed.[24] It was later implemented into the Mimblewimble protocol (which the Grin and Beam cryptocurrencies are based upon) and Monero cryptocurrency.[25] In 2019, Firo implemented the Sigma protocol, which is an improvement on the Zerocoin protocol without trusted setup.[26][14] In the same year, Firo introduced the Lelantus protocol, an improvement on the Sigma protocol, where the former hides the origin and amount of a transaction.[27]