## Succinct Non-Interactive ArgumentsSuccinct 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 ## Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
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 2
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
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 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} } |