# Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs

**Authors:**

*D. Boneh, Y. Ishai, A. Sahai, and D. Wu*

** Abstract: **

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-λ against provers of
size 2λ. We say a SNARG is quasi-optimally succinct if its proof
length is Õ(λ), and that it is quasi-optimal, 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
quasi-optimality introduced in the work of Boneh et al. (Eurocrypt
2017).
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
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 (designated-verifier) SNARGs that provide optimal
succinctness for a non-negligible soundness error. Concretely, we put
forward the notion of “1-bit SNARGs” that achieve soundness error 1/2
with only one bit of proof. We first show how to build 1-bit SNARGs
from indistinguishability obfuscation, and then show that 1-bit SNARGs
also suffice for realizing a form of witness encryption. The latter
result highlights a two-way connection between the soundness of very
succinct argument systems and powerful forms of encryption.

** Reference:**

To appear in Eurocrypt 2018

**Full paper:**
pdf