AntMan: Interactive Zero-Knowledge Proofs with Sublinear Communication
AntMan: Interactive Zero-Knowledge Proofs with Sublinear Communication
复制标题
DOI：
10.1145/3548606.3560667
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Chenkai Weng;Kang Yang;Zhaomin Yang;Xiang Xie;Xiao Wang
中科院分区：
文献类型：
--
作者：
Chenkai Weng;Kang Yang;Zhaomin Yang;Xiang Xie;Xiao Wang
最近关于交互式零知识(ZK)协议的工作提供了一种新的高效和可扩展的范例。然而，这些协议存在通信开销高的问题，通常与电路大小成线性关系。在本文中，我们提出了两个新的ZK协议，其通信与电路大小呈次线性关系，同时保持了相似的计算效率。(1)设计了一个ZK协议，该协议可以证明任意电路C在通信O(B+|C|)个域元素(具有自由加法门)时B次执行，而最好的前人工作需要通信O(B|C|)个域元素。我们的协议是由一种称为信息论多项式认证码的新工具实现的，它可能是独立感兴趣的。(2)对该协议进行了优化实现，具有较高的实用性。例如，在B=2048，|C|=221，在50 Mbps带宽和16个线程的情况下，基于矢量不经意线性评估(VOLE)的最先进的ZK协议QuickSilver每秒只能证明71万个多门(MGPS)，每个门发送一个字段元素；在相同的硬件配置下，我们的协议可以证明15.74MGPS(提高22倍)，每个门发送0.0061个字段元素(提高164倍)。(3)对上述思想进行了扩展，构造了一个ZK协议，该协议可以证明通信O(|C|3/4)中任意回路C的一次执行。这是第一个采用次线性通信的ZK协议，适用于基于VOLE的ZK系列中的任意电路。
Recent works on interactive zero-knowledge (ZK) protocols provide a new paradigm with high efficiency and scalability. However, these protocols suffer from high communication overhead, often linear to the circuit size. In this paper, we proposed two new ZK protocols with communication sublinear to the circuit size, while maintaining a similar level of computational efficiency. (1) We designed a ZK protocol that can prove B executions of any circuit C in communication O(B + |C|) field elements (with free addition gates), while the best prior work requires a communication of O(B|C|) field elements. Our protocol is enabled by a new tool called as information-theoretic polynomial authentication code, which may be of independent interest. (2) We developed an optimized implementation of this protocol which shows high practicality. For example, with B=2048, |C|=221, and under 50 Mbps bandwidth and 16 threads, QuickSilver, a state-of-the-art ZK protocol based on vector oblivious linear evaluation (VOLE), can only prove 0.71 million MULT gates per second (mgps) and send one field element per gate; our protocol can prove 15.74 mgps (22x improvement) and send 0.0061 field elements per gate (164x improvement) under the same hardware configuration. (3) Extending the above idea, we constructed a ZK protocol that can prove a single execution of any circuit C in communication O(|C|3/4). This is the first ZK protocol with sublinear communication for an arbitrary circuit in the VOLE-based ZK family.