Interactive and zero-knowledge proofs

Show full item record

Title: Interactive and zero-knowledge proofs
Author: Noland, Molli
Abstract: 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.
Record URI: http://hdl.handle.net/1850/13725
Date: 1999-05-19

Files in this item

Files Size Format View
MNolandThesis05-19-1999.pdf 2.564Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse