Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
复制标题
基于格的 SNARG 及其在更有效的混淆中的应用
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
David J. Wu
中科院分区：
文献类型：
--
作者：
D. Boneh;Yuval Ishai;A. Sahai;David J. Wu
简洁的非交互参数（snarg）使验证\({{\mathsf {NP}}}\)计算的复杂性大大低于经典的\({{\mathsf {NP}}}\)验证。在这项工作中，我们给出了第一个具有准最优简洁性（其中参数大小在安全参数中是拟线性的）的基于格子的SNARG候选。我们的方法的进一步扩展产生了第一个snog（从任何假设），它在证明者开销（安全性参数中的多对数）和简便性方面都是准最优的。此外，由于我们的结构是基于晶格的，它们似乎可以抵抗量子攻击。我们构建的核心是纯线性向量加密的新概念，这是Bitansky等人（TCC 2013）引入的纯线性加密概念的概括。我们推测Regev加密的变体满足我们新的纯线性定义。然后，结合新的信息论方法在小有限域上构建统计健全的线性pcp，我们获得了第一个准最优snags。
Succinct non-interactive arguments (SNARGs) enable verifying \({{\mathsf {NP}}}\) computations with substantially lower complexity than that required for classical \({{\mathsf {NP}}}\) verification. In this work, we give the first 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.