## Publications## Quasi-Optimal SNARGs via Linear Multi-Prover Interactive ProofsDan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu ## ResourcesAbstract
Succinct non-interactive 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
λ, we measure the asymptotic cost of achieving soundness error
2 This work gives the first quasi-optimal SNARG for Boolean circuit
satisfiability from a concrete cryptographic assumption. Our construction
takes a two-step approach. The first is an information-theoretic construction
of a quasi-optimal linear multi-prover interactive proof (linear MIP) for
circuit satisfiability. Then, we describe a generic cryptographic compiler
that transforms our quasi-optimal linear MIP into a quasi-optimal SNARG by
relying on the notion of linear-only vector encryption over rings introduced
by Boneh et al. Combining these two primitives yields the first quasi-optimal
SNARG based on linear-only vector encryption. Moreover, our linear MIP
construction leverages a new Finally, we consider (designated-verifier) SNARGs that provide BibTeX
@inproceedings{BISW18, author = {Dan Boneh and Yuval Ishai and Amit Sahai and David J. Wu}, title = {Quasi-Optimal {SNARGs} via Linear Multi-Prover Interactive Proofs}, booktitle = {{EUROCRYPT}}, year = {2018} } |