Welcome to the resource topic for 2024/1431
Title:
Interactive Line-Point Zero-Knowledge with Sublinear Communication and Linear Computation
Authors: Fuchun Lin, Chaoping Xing, Yizhou Yao
Abstract:Studies of vector oblivious linear evaluation (VOLE)-based zero-knowledge (ZK) protocols flourish in recent years. Such ZK protocols feature optimal prover computation and a flexibility for handling arithmetic circuits over arbitrary fields. However, most of them have linear communication, which constitutes a bottleneck for handling large statements in a slow network. The pioneer work AntMan (CCS’22), achieved sublinear communication for the first time within VOLE-based ZK, but lost the advantage of fast proving. In this work, we propose two new VOLE-based ZK constructions that achieve sublinear communication and linear computation, simultaneously. Let \mathcal{C} be a circuit with size S, input size n, and depth d. In particular, our first ZK, specialized for layered circuits, has communication O(n+d\log{S}), while our second ZK can be used to prove general circuits and has communication O(n+d\log{S}+d^2).
Our results are obtained by introducing the powerful sum-check techniques from the mature line of works on interactive proofs into the context of VOLE-based ZK for the first time. Reminiscent of the non-interactive line-point zero-knowledge proof system (ITC’21), we introduce an interactive line-point zero-knowledge (ILPZK) proof system, which closely connects with VOLE-based ZK protocols. In addition, our works also enrich the studies of ZK based on interactive proofs, with new interesting features (e.g., having information-theoretic UC-security, naturally supporting any field) achieved.
ePrint: https://eprint.iacr.org/2024/1431
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .