Paper 2018/133
QuasiOptimal SNARGs via Linear MultiProver Interactive Proofs
Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu
Abstract
Succinct noninteractive arguments (SNARGs) enable verifying NP computations with significantly less complexity than that required for classical NP verification. In this work, we focus on simultaneously minimizing the proof size and the prover complexity of SNARGs. Concretely, for a security parameter $\lambda$, we measure the asymptotic cost of achieving soundness error $2^{\lambda}$ against provers of size $2^\lambda$. We say a SNARG is quasioptimally succinct if its proof length is $\tilde{O}(\lambda)$, and that it is quasioptimal, if moreover, its prover complexity is only polylogarithmically greater than the running time of the classical NP prover. We show that this definition is the best we could hope for assuming that NP does not have succinct proofs. Our definition strictly strengthens the previous notion of quasioptimality introduced in the work of Boneh et al. (Eurocrypt 2017). This work gives the first quasioptimal SNARG for Boolean circuit satisfiability from a concrete cryptographic assumption. Our construction takes a twostep approach. The first is an informationtheoretic construction of a quasioptimal linear multiprover interactive proof (linear MIP) for circuit satisfiability. Then, we describe a generic cryptographic compiler that transforms our quasioptimal linear MIP into a quasioptimal SNARG by relying on the notion of linearonly vector encryption over rings introduced by Boneh et al. Combining these two primitives yields the first quasioptimal SNARG based on linearonly vector encryption. Moreover, our linear MIP construction leverages a new robust circuit decomposition primitive that allows us to decompose a circuit satisfiability instance into several smaller circuit satisfiability instances. This primitive may be of independent interest. Finally, we consider (designatedverifier) SNARGs that provide optimal succinctness for a nonnegligible soundness error. Concretely, we put forward the notion of "1bit SNARGs" that achieve soundness error 1/2 with only one bit of proof. We first show how to build 1bit SNARGs from indistinguishability obfuscation, and then show that 1bit SNARGs also suffice for realizing a form of witness encryption. The latter result highlights a twoway connection between the soundness of very succinct argument systems and powerful forms of encryption.
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2018
 Keywords
 quasioptimal SNARGslinear MIPslinear PCPs
 Contact author(s)
 dwu4 @ cs stanford edu
 History
 20180207: received
 Short URL
 https://ia.cr/2018/133
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/133, author = {Dan Boneh and Yuval Ishai and Amit Sahai and David J. Wu}, title = {QuasiOptimal SNARGs via Linear MultiProver Interactive Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2018/133}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/133}}, url = {https://eprint.iacr.org/2018/133} }