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 non-deterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model (Micali in SIAM J Comput 30(4):1253–1298, 2000), prior to our work the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol (Di Crescenzo and Lipmaa in Proceedings of the 4th conference on computability in Europe, 2008). 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. Going beyond \(\hbox {ECRH}\)s, we formulate the notion of extractable one-way functions (\(\hbox {EOWF}\)s). Assuming the existence of a natural variant of \(\hbox {EOWF}\)s, we construct a two-message selective-opening-attack-secure commitment scheme and a three-round zero-knowledge argument of knowledge. Furthermore, if the \(\hbox {EOWF}\)s are concurrently extractable, the three-round zero-knowledge protocol is also concurrent zero knowledge. Our constructions circumvent previous black-box impossibility results regarding these protocols by relying on \(\hbox {EOWF}\)s as the non-black-box component in the security reductions.

+More

ie noninteractive computationally sound np em classemphasistypeitalic extractable oneway functionsem span classinlineequation idieq2hbox complexity security reductions of computation computability in europe span classcitationrefa crescenzo and lipmaas protocol succinct noninteractive em classemphasistypeitalic adaptive argument span classinlineequation idieq5hbox eowfspans proofs ecrhs twomessage selectiveopeningattacksecure commitment scheme random oracle model succinct twoparty secure computation threeround zeroknowledge argument relaxations

Ran Canetti,Alessandro Chiesa,Shafi Goldwasser,Nir Bitansky,Huijia Lin,Aviad Rubinstein,Eran Tromer,.The Hunting of the SNARK. 30 (4),989–1066.

Ran Canetti, et al."The Hunting of the SNARK" 30

Ran Canetti,Alessandro Chiesa,Shafi Goldwasser,Nir Bitansky,Huijia Lin,Aviad Rubinstein,Eran Tromer,"The Hunting of the SNARK"