Paper 2011/443

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

Nir Bitansky, Ran Canetti, Alessandro Chiesa, 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 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.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
CS proofsproofs of knowledgeknowledge assumptionsknowledge of exponentknapsack
Contact author(s)
alexch @ csail mit edu
History
2011-12-01: last of 6 revisions
2011-08-15: received
See all versions
Short URL
https://ia.cr/2011/443
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/443,
      author = {Nir Bitansky and Ran Canetti and Alessandro Chiesa and Eran Tromer},
      title = {From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again},
      howpublished = {Cryptology ePrint Archive, Paper 2011/443},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/443}},
      url = {https://eprint.iacr.org/2011/443}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.