How to Prove a Theorem So No One Else Can Claim It 论文

摘要

Goldwasser, Micali, and Rackoff [GMR] define for us what it means for a theorem to have a "zero-knowledge proof. " In brief, a zero-knowledge proof is an interactive probabilistic protocol that gives highly convincing (but not absolutely certain) evidence that a theorem is true and that the prover knows a proof (a "standard " proof in a given logical system), while providing not a single additional bit of information about the proof. GMR formalize this idea. We do not. Nevertheless, we hope that the reader who has not read their paper will still understand our proofs. Goldreich, Micali, and Wigderson [GMW] take another leap forward. They show that if one makes a reasonable assumption (that one-way functions1 exist), then it is possible to convert any standard constructive proof of any of the the-orems in a large natural class of theorems2 into a zero-knowledge proof that the theorem is true. GMW start by considering a particular NP-complete problem: Graph 3-Colorability. Instance. A graph G. Question. Can G be "properly " 3-colored (each node colored by one of 3 given colors so that no two adjacent nodes receive the same color). GMW show that a "prover " who knows how to 3-color a particular graph G can convince a verifier that (1) G is 3-colorable, and (2) the prover knows a 3-coloring, without giving away any additional information. In particular, the prover does not give away the slightest clue how to 3-color G. Supported, in part, by National Science Foundation Grant DCR 85-13926. ^ne-wayïunctions are 1-1 functionsTrom n-Rt integers to n-bitTintegers tEaT^inlBrmäUyp are easy to compute in the forward direction, but hard to invert on all but a small fraction of ra-bit integers. 2These theorems, which arise frequently in mathematics and computer science, are the yes-instances of decision problems IT in NP. A good reference to NP and the theory of NP-