We formulate a general and relatively natural notion of an extractable collision-resistant hash function (ECRH) and show that, if ECRHs exist, then a modified version of Di Crescenzo and Lipmaa's protocol is a succinct non-interactive argument for NP. Furthermore, the modified protocol is actually a succinct non-interactive adaptive argument of knowledge (SNARK). We then propose several candidate constructions for ECRHs and relaxations thereof.
We demonstrate the applicability of SNARKs to various forms of delegation of computation, to succinct non-interactive zero knowledge arguments, and to succinct two-party secure computation. Finally, we show that SNARKs essentially imply the existence of ECRHs, thus demonstrating the necessity of the assumption.
Category / Keywords: foundations / CS proofs, proofs of knowledge, knowledge assumptions, knowledge of exponent, knapsack Date: received 14 Aug 2011, last revised 30 Nov 2011 Contact author: alexch at csail mit edu Available formats: PDF | BibTeX Citation Note: revision history of main changes: (1) Aug 14: first draft (2) Aug 17: expanded and clarified section on alternative constructions of (blurry) ECRHs and delegation of computation (mostly Sections 7.4 and 9.1) (3) Sep 21: added section on how to obtain ZK-SNARKs and their application to succinct secure computation (Sections 8 and 9.2) (4) Nov 30: clarified necessity of assumption, improved overall presentation Version: 20111201:043431 (All versions of this report) Discussion forum: Show discussion | Start new discussion