Paper 2025/1866

Succinct Line-Point Zero-Knowledge Arguments from Homomorphic Secret Sharing

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.