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