Paper 2014/580

The Hunting of the SNARK

Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer

Abstract

The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08]. We formulate a general and relatively natural notion of an \emph{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 \emph{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. Going beyond $\ECRH$s, we formulate the notion of {\em extractable one-way functions ($\EOWF$s)}. Assuming the existence of a natural variant of $\EOWF$s, we construct a $2$-message selective-opening-attack secure commitment scheme and a 3-round zero-knowledge argument of knowledge. Furthermore, if the $\EOWF$s are concurrently extractable, the 3-round zero-knowledge protocol is also concurrent zero-knowledge. Our constructions circumvent previous black-box impossibility results regarding these protocols by relying on $\EOWF$s as the non-black-box component in the security reductions.

Note: This paper is a merge of Bitansky-Canetti-Chiesa-Tromer11 and Goldwasser-Lin-Rubinstein11. It include results on zero-knowledge protocols from extractable one-way functions, which do not appear in the public eprint versions of either BCCT11 or GLR11.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. ITCS 2012
Keywords
extractable functionsknowledge assumptionsknowledge of exponentcollision-resistant hash functionszero knolwedge
Contact author(s)
nirbitan @ tau ac il
History
2014-07-25: received
Short URL
https://ia.cr/2014/580
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/580,
      author = {Nir Bitansky and Ran Canetti and Alessandro Chiesa and Shafi Goldwasser and Huijia Lin and Aviad Rubinstein and Eran Tromer},
      title = {The Hunting of the SNARK},
      howpublished = {Cryptology ePrint Archive, Paper 2014/580},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/580}},
      url = {https://eprint.iacr.org/2014/580}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.