Études in non-interactive zero-knowledge

N a ZERO-KNOWLEDGE PROOF [GMR85], Prover interactively convinces Verifier that theorem 7r is true in such a way that (a) a corrupt Prover cannot convince Verifier of a false theorem and (b) a corrupt Verifier cannot "learn" anything other than the fact that r is true. In a NON-INTERACTIVE ZERO-KNOWLEDGE PROOF [BFM88], the Prover must do the above by sending only a single message to Verifier! To make this possible, Prover and Verifier are not tabula rasa, but rather born with some setup information. Much in the fashion of a musical TUDE, in this thesis, we explore several variations on the setup assumptions for non-interactive zero-knowledge in order to enjoy a richer understanding. Our labor brings forth * various unconditional characterizations of computational and statistical NIZK proofs, * new constructions that have practical applications to non-malleable encryption and CCAz encryption, * new constructions which form the building blocks of "fair" versions of interactive zero-knowledge and collusion-free multi-party computation protocols, * and conceptual contributions which underlie the recent works on how cryptography can be used to achieve equilibrium in game theory.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Shelat, Abhi

Advisor dc:contributor.advisor

• Silvio Micali.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/35531

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/35531