Zero-knowledge proof
A zero-knowledge proof (ZKP) is a proof of a conjecture which does not rely on the verifier's having any knowledge whether the conjecture is true or false. The concept of zero-knowledge proof is typically invoked in the field of cryptography, although zero-knowledge proofs have applications in other arenas as well.
To construct a zero-knowledge proof, one must postulate the existence of two parties, the Prover (traditionally called "Pat") and the Verifier (traditionally called "Victor"). The Prover's job is to convince the Verifier of the truth of his argument, while having zero knowledge of the field. A series of steps are postulated, at the end of which Victor is convinced (to within 1/f, thus accounting for the possibility of noise in the data) that Pat indeed believes the given conjecture to be true.
Example: ZKP of the Three-Color Theorem
Let the conjecture in this case be, "All 3-regular planar graphs G can be colored using only 3 colors." Pat believes this conjecture to be true. Victor does not know whether it is true or false. Therefore, a zero-knowledge proof from Pat to Victor is possible. Here is how we construct it:
- Pat draws a graph G satisfying the requirements above.
- Pat shows the graph to Victor, so that Victor is convinced that it is both 3-regular and planar.
- Victor chooses a planar subgraph H of G, and challenges Pat to color that subgraph using only three colors.
- Pat secretly 3-colors H.
- Victor chooses two vertices v1, v2 in H and asks Pat to reveal their colors. Pat tells Victor that (for example) v1 is red and v2 is green. If Pat had not actually 3-colored the graph, Pat would be unable some fraction of the time to name the colors of v1 and v2; therefore, Victor must necessarily accept that Pat did in fact three-color the given graph, and therefore all planar 3-regular graphs are 3-colorable. Pat has proven the conjecture to Victor's satisfaction, but (in accordance with the rules of ZKP) Victor is still in the dark as to how she did it.
