Welcome to the resource topic for 2025/1866
Title:
Succinct Line-Point Zero-Knowledge Arguments from Homomorphic Secret Sharing
Authors: Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan, Mengmeng Zhou
Abstract:Dittmer, Ishai and Ostrovsky (ITC’21) proposed {\em line-point zero-knowledge proof} (LPZK), a simple ``commit-and-prove’’ system, motivated by practical protocols for compressing correlated pseudorandomness used in secure multiparty computation (MPC). Typically, LPZK admits concretely efficient ZK protocols with a streaming, linear time prover, {\em but a linear size proof}. A natural question raised in the context is how far can we go in minimizing the proof size, while maintaining the prover efficiency. Though a recent work by Lin, Xing and Yao (ASIACRYPT’24) gives an interactive LPZK with a sublinear proof size O(n+d^2\log{|\mathcal{C}|}), it is still far from being {\em succinct}, where n,d,|\mathcal{C}| are referred to as input size, circuit depth, and circuit size, respectively.
In this work, we beat the proof size barrier and propose {\em succinct LPZK arguments}, by distilling techniques from orthogonal studies on homomorphic secret sharing and succinct garbling.
Specifically, under variants of group/lattice-based assumptions, we show the followings:
i) There exist succinct LPZK arguments with common reference string (CRS) size O(n^{2/3}), proof size O(n^{2/3}), prover time O(n^{4/3}+|\mathcal{C}|), verification time O(n+|\mathcal{C}|), and negligible soundness error, where both the prover and the verifier executions and be run in a streaming fashion.
ii) The above proof size can be further optimized to O(1), at the cost of a larger CRS size O(n), and prover time increased to O(n^{2}+|\mathcal{C}|).
In general, our succinct LPZK arguments pave a new way for building designated-verifier zero-knowledge succinct non-interactive arguments of knowledge (dv-zkSNARKs), and new interesting features (e.g., streaming, constant sized proof with CRS size not proportional to the circuit size) are obtained for the first time along the way.
ePrint: https://eprint.iacr.org/2025/1866
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 .