Succinct non-Interactive arguments

Succinct non-interactive arguments (SNARGs), also known as "CS proofs" [Micali, FOCS 1994], enable verifying NP statements with much lower complexity than required for classical NP verification (in fact, with complexity that is independent of the NP language at hand). In particular, SNARGs provide strong solutions to the problem of verifiably delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase, independent of the statement to be proven later. In this thesis we present two main results: (1) A general methodology for the construction of preprocessing SNARGs. (2) A transformation, based on collision-resistant hashing, that takes any SNARG having a natural proof of knowledge property (i.e., a SNARK) as input and "bootstrapps" it to obtain a complexity-preserving SNARK, i.e., one without expensive preprocessing and where the prover's time and space complexity is essentially the same as that required for classical NP verification. These results provide the first publicly-verifiable complexity-preserving SNARK in the plain model. At the heart of our transformations is recursive composition of SNARKs and, more generally, new techniques for constructing and using proof-carrying data (PCD) systems, which extend the notion of a SNARK to the distributed setting. Concretely, to bootstrap a given SNARK, we recursively compose the SNARK to obtain a "weak" PCD system for shallow distributed computations, and then use the PCD framework to attain stronger, complexity-preserving SNARKs and PCD systems.

Department dc:contributor.department

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

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Chiesa, Alessandro

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/93057

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/93057