View article

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 …