Succinct non-Interactive arguments
Author(s)
Chiesa, Alessandro
DownloadFull printable version (10.40Mb)
Other Contributors
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.
Advisor
Silvio Micali.
Terms of use
Metadata
Show full item recordAbstract
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.
Description
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. Cataloged from PDF version of thesis. Includes bibliographical references (pages 143-150).
Date issued
2014Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer SciencePublisher
Massachusetts Institute of Technology
Keywords
Electrical Engineering and Computer Science.