19
edits
Changes
Jump to navigation
Jump to search
New page: 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 ...
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 [[party|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 graph|regular]] [[planar graph]]s ''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 [[challenge]]s 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.
[[Category:Cryptography]]
To construct a zero-knowledge proof, one must postulate the existence of two [[party|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 graph|regular]] [[planar graph]]s ''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 [[challenge]]s 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.
[[Category:Cryptography]]