Interactive and zero-knowledge proofs

An interactive proof involves two parties, the prover and the verifier. The goal of the proof is for the prover to convince the verifier that some instance of a decision problem is true. A zero-knowledge proof is an interactive proof where the only information learned by the verifier of the proof is the outcome of the proof. This thesis contains a theoretical overview of interactive and zero-knowledge proofs and describes experiments with implementations of some of them. Two examples of interactive proofs from number theory are given, a protocol for quadratic non-residues and a protocol for subgroup non-membership. The third example of an interactive proof is a protocol for determining the truth value of a quantified Boolean formula. This interactive proof was implemented and the details of that implementation, plus a test of the implementation derived from game theory, are included. There is also a discussion of quantum interactive proofs. The two examples of perfect zero-knowledge proofs that are included are protocols for quadratic residues and for subgroup membership. These protocols were also implemented, and those details are included. For each protocol, there is a discussion of the complexity status of the problems addressed by the protocol. There is also a brief discussion of the history and applications of interactive and zero-knowledge proofs.