Paper 2017/240
Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
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 2^100. 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 approximately 2^12 levels of multilinearity suffices. This is over 2^80 times more efficient than existing candidates, and thus, represents an important milestone towards implementable program obfuscation for all circuits.
Note: Add additional related work, conclusions
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2017
- Keywords
- quasi-optimal SNARGsobfuscationlattices
- Contact author(s)
- dwu4 @ cs stanford edu
- History
- 2017-03-18: last of 3 revisions
- 2017-03-11: received
- See all versions
- Short URL
- https://ia.cr/2017/240
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/240,
author = {Dan Boneh and Yuval Ishai and Amit Sahai and David J. Wu},
title = {Lattice-Based SNARGs and Their Application to More Efficient Obfuscation},
howpublished = {Cryptology ePrint Archive, Paper 2017/240},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/240}},
url = {https://eprint.iacr.org/2017/240}
}
