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.
On the other hand, if the balls were the same colour and hence indistinguishable, your ability to determine whether a switch occurred would be no better than random guessing.
Over multiple trials, the success rate would statistically converge to 50%, and you could not achieve a performance significantly better than chance.
[9] The prover starts by taking a large black board with a small hole in it, the size of Waldo.
[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.
An interactive proof system with (P,V) for a language L is zero-knowledge if for any probabilistic polynomial time (PPT) verifier
The auxiliary string z in the definition plays the role of "prior knowledge" (including the random coins of
The protocol proceeds as follows: in each round, Peggy generates a random number r, computes C = gr mod p and discloses this to Victor.
By executing a large-enough number of rounds, the probability of a cheating prover succeeding can be made arbitrarily low.
If the result is "heads", then he picks a random value r, computes C = gr mod p, and discloses C as if it is a message from Peggy to Victor.
On the other hand, if the coin flipping result is "tails", then Simon picks a random number r′, computes C′ = gr′ · y−1 mod p, and discloses C′ as if it is a message from Peggy to Victor.
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.
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.
To show that Peggy knows this Hamiltonian cycle, she and Victor play several rounds of a game: 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.
For all realistic purposes, it is infeasibly difficult to defeat a zero-knowledge proof with a reasonable number of rounds in this way.
[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.
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.
[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.
However, this additional layer of privacy can cause potentially undetected hyperinflation of Zerocash supply because fraudulent coins cannot be tracked.
[27] Zero-knowledge proofs by their nature can enhance privacy in identity-sharing systems, which are vulnerable to data breaches and identity theft.
When integrated to a decentralized identifier system, ZKPs add an extra layer of encryption on DID documents.
[28] Zero-knowledge proofs were first conceived in 1985 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in their paper "The Knowledge Complexity of Interactive Proof-Systems".
They also gave the first zero-knowledge proof for a concrete problem, that of deciding quadratic nonresidues mod m. Together with a paper by László Babai and Shlomo Moran, this landmark paper invented interactive proof systems, for which all five authors won the first Gödel Prize in 1993.
More generally, Russell Impagliazzo and Moti Yung as well as Ben-Or et al. would go on to show that, also assuming one-way functions or unbreakable encryption, there are zero-knowledge proofs for all problems in IP = PSPACE, or in other words, anything that can be proved by an interactive proof system can be proved with zero knowledge.
[33] It turns out that, in an Internet-like setting, where multiple protocols may be executed concurrently, building zero-knowledge proofs is more challenging.
The line of research investigating concurrent zero-knowledge proofs was initiated by the work of Dwork, Naor, and Sahai.
Blum, Feldman, and Micali showed that a common random string shared between the prover and the verifier is enough to achieve computational zero-knowledge without requiring interaction.
A list of zero-knowledge proof protocols and libraries is provided below along with comparisons based on transparency, universality, plausible post-quantum security, and programming paradigm.