From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge,

The existence of non-interactive succinct arguments (namely, non-interactive computationally-sound proof systems where the verifier’s time complexity is only polylogarithmically related to the complexity of deciding the language) has been an intriguing question for the past two decades. The question has gained renewed importance in light of the recent interest in delegating computation to untrusted workers. Still, other than Micali’s CS proofs in the Random Oracle Model, the only existing candidate construction is based on an elaborate assumption that is tailored to the specific proposal [Di Crescenzo and Lipmaa, CiE ’08]. We modify and re-analyze that construction: • We formulate a general and relatively mild notion of extractable collision-resistant hash functions (ECRHs), and show that if ECRHs exist then the modified construction is a non-interactive suc-cinct argument (SNARG) for NP. Furthermore, we show that (a) this construction is a proof of knowledge, and (b) it remains secure against adaptively chosen instances. We call such arguments SNARGs of knowledge (SNARKs). • We describe some applications of SNARKs, for delegation of computations with long delegator input and with worker input, and for constructing zero-knowledge SNARKs as well as succinc