Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One
Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One
复制标题
提高线点零知识：以一倍的价格进行两次乘法
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
R. Ostrovsky
中科院分区：
文献类型：
--
作者：
Samuel Dittmer;Yuval Ishai;Steve Lu;R. Ostrovsky
用于向量不经意线性评估（VOLE）的快速协议的最新进展启发了一系列新的基于VOLE的轻量级指定验证器NIZK协议（Weng等人，S&P 2021，Baum等人，Crypto 2021，Dittmer等人，ITC 2021，Yang等人，CCS 2021）。特别地，Dittmer等人的线点零知识（Line-Point Zero Knowledge，LPZK）协议具有在给定随机VOLE相关的单个实例的情况下完全非密码的优点。我们提出了改进LPZK通过引入额外的结构的相关随机性。使用VOLE相关性的有效可实现变体，我们将LPZK的在线证明大小减少了大约2倍：从每个乘法门大约2个字段元素或随机预言变体中的1个元素分别减少到仅1个或1/2个元素。特别是，我们得到了第一个实用的VOLE为基础的NIZK，打破了1元素每乘法的障碍。我们实现了我们的协议的优化版本，并将其与其他最近基于VOLE的NIZK协议进行比较。在通信是瓶颈的典型情况下，我们比以前所有基于VOLE的协议获得至少2倍的性能改进。当证明器计算是瓶颈时，我们的性能至少比所有非LPZK协议高出2- 3倍，并且（我们的优化实现）LPZK大约高出30%，与普通电路评估相比，获得了2- 3倍的减速因子。
Recent advances in fast protocols for vector oblivious linear evaluation (VOLE) have inspired a family of new VOLE-based lightweight designated-verifier NIZK protocols (Weng et al., S&P 2021, Baum et al., Crypto 2021, Dittmer et al., ITC 2021, Yang et al., CCS 2021). In particular, the Line-Point Zero Knowledge (LPZK) protocol of Dittmer et al. has the advantage of being entirely non-cryptographic given a single instance of a random VOLE correlation. We present improvements to LPZK through the introduction of additional structure to the correlated randomness. Using an efficiently realizable variant of the VOLE correlation, we reduce the online proof size of LPZK by roughly 2x: from roughly 2 field elements per multiplication gate, or 1 element in the random oracle variant, to only 1 or 1/2 elements respectively. In particular, we get the first practical VOLE-based NIZK that breaks the 1-element-per-multiplication barrier. We implemented an optimized version of our protocol and compared it with other recent VOLE-based NIZK protocols. In the typical case where communication is the bottleneck, we get at least 2x performance improvement over all previous VOLE-based protocols. When prover computation is the bottleneck, we outperform all non-LPZK protocols by at least 2-3x and (our optimized implementation of) LPZK by roughly 30%, obtaining a 2-3x slowdown factor compared to plain circuit evaluation.
DOI：
10.1145/3319535.3363228
发表时间：
2019-11
期刊：
Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
影响因子：
--
作者：
Phillipp Schoppmann;Adrià Gascón;Leonie Reichert;Mariana Raykova
通讯作者：
Phillipp Schoppmann;Adrià Gascón;Leonie Reichert;Mariana Raykova
DOI：
10.1007/978-3-030-45727-3_19
发表时间：
2020-05
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
David Heath;V. Kolesnikov
通讯作者：
David Heath;V. Kolesnikov