Interactive and zero-knowledge proofs

Show simple item record

dc.contributor.advisor Radziszowski, Stanislaw
dc.contributor.advisor Wilcox, Theodore
dc.contributor.advisor Hart, David
dc.contributor.author Noland, Molli
dc.date.accessioned 2011-06-17T18:46:14Z
dc.date.available 2011-06-17T18:46:14Z
dc.date.issued 1999-05-19
dc.identifier.uri http://hdl.handle.net/1850/13725
dc.description.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. en_US
dc.language.iso en_US en_US
dc.subject Mathematics en_US
dc.subject.lcc QA9.54 .N65 1999
dc.subject.lcsh Proof theory en_US
dc.title Interactive and zero-knowledge proofs en_US
dc.type Thesis en_US
dc.description.college College of Science en_US
dc.description.department Department of Mathematical Sciences en_US

Files in this item

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

This item appears in the following Collection(s)

Show simple item record

Search RIT DML


Advanced Search

Browse