Succinct Non-Interactive Arguments

Succinct non-interactive arguments (SNARGs) enable verifying correctness of a computation much faster than performing the computation itself. Succinct arguments are useful for constructing verifiable computation systems and for building privacy-preserving cryptocurrencies like Zerocash. In this work, we construct new SNARGs from lattice-based assumptions (thus yielding an argument system with post-quantum security), as well as the first quasi-optimal SNARG–that is, a SNARG that simultaneously minimizes both the prover complexity as well as the proof size (up to polylogarithmic factors).

Lattice-Based SNARGs and Their Application to More Efficient Obfuscation

Contributors: Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu

Abstract:

Succinct non-interactive arguments (SNARGs) enable verifying NP computations with substantially lower complexity than that required for classical NP verification. In this work, we first construct a lattice-based SNARG candidate with quasi-optimal succinctness (where the argument size is quasilinear in the security parameter). Further extension of our methods yields the first SNARG (from any assumption) that is quasi-optimal in terms of both prover overhead (polylogarithmic in the security parameter) as well as succinctness. Moreover, because our constructions are lattice-based, they plausibly resist quantum attacks. Central to our construction is a new notion of linear-only vector encryption which is a generalization of the notion of linear-only encryption introduced by Bitansky et al. (TCC 2013). We conjecture that variants of Regev encryption satisfy our new linear-only definition. Then, together with new information-theoretic approaches for building statistically-sound linear PCPs over small finite fields, we obtain the first quasi-optimal SNARGs.

We then show a surprising connection between our new lattice-based SNARGs and the concrete efficiency of program obfuscation. All existing obfuscation candidates currently rely on multilinear maps. Among the constructions that make black-box use of the multilinear map, obfuscating a circuit of even moderate depth (say, 100) requires a multilinear map with multilinearity degree in excess of 2100. In this work, we show that an ideal obfuscation of both the decryption function in a fully homomorphic encryption scheme and a variant of the verification algorithm of our new lattice-based SNARG yields a general-purpose obfuscator for all circuits. Finally, we give some concrete estimates needed to obfuscate this “obfuscation-complete” primitive. We estimate that at 80-bits of security, a (black-box) multilinear map with ≈212 levels of multilinearity suffices. This is over 280 times more efficient than existing candidates, and thus, represents an important milestone towards implementable program obfuscation for all circuits.

Resources:

BibTeX:
@inproceedings{BISW17,
  author     = {Dan Boneh and Yuval Ishai and Amit Sahai and David J. Wu},
  title      = {Lattice-Based {SNARGs} and Their Application to More Efficient Obfuscation},
  booktitle  = {{EUROCRYPT}},
  year       = {2017}
}

Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs

Contributors: Dan Boneh, Yuval Ishai, Amit Sahai, and David J. 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.

Resources:

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}
}