Interactive Proofs and Applications
Sbafi Goldwasser · 1990
Proofs whose correctness can be verified efficiently play a central role in complexity theory. The famous complexity class NP consists of those sets for which proofs of membership exist. For example, the set of all satisfiable Boolean formulas is in NP. A short proof that a boolean formula (j) is satisfiable would be a truth assignment to the boolean variables which makes 0 true. Formally, NP = {L cz {o, 1}* s.t. 3 a polynomial time computable function fL and constant c > 0 such that x G {0,1} is in L if and only if 3y G {0,1} such that fL(x,y) = 1}. How about proving that there is no assignment which makes (j> true? It is generally believed that no short proof exists. Still, by some very recent work, we now know of procedures which can convince us quickly and beyond a shadow of a doubt that a formula </3 is not satisfiable. Such procedures, introduced by Goldwasser, Micali, and Rackoff [GMR], and in somewhat different form by Babai [Ba] are called interactive proofs . Informally, an interactive proof-system is a method by which one algorithm of unlimited resources, called the prover, convinces another algorithm which runs in polynomial time, called the verifier, of the truth of a proposition. The verifier may toss coins, ask repeated questions of the prover, and run efficient tests upon the prover's responses before deciding whether to be convinced or not. Interactive proofs do not yield proofs in the strict mathematical sense: the verifier may be incorrectly convinced with an exponentially small, though non-zero probability. Formally, a set L is said to have an interactive proof-system if for all x in L, there exists a prover that can convince the verifier that x is in L with high probability, and for all x not in L, no prover can convince the verifier that x is in L with better than negligible probability. The class IP denotes the sets for which interactive proofs of membership exist. Essentially, this procedure adds two new ingredients to the classical notion of proof (which can be written down and does not require active participation of the verifier) : randomness and interaction with the prover.