Succinct Line-Point Zero-Knowledge from Homomorphic Secret Sharing

No ratings

Presented at Asiacrypt 2025

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.\r\n\r\nIn 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. \r\nSpecifically, under variants of group/lattice-based assumptions, we show the followings: \r\n\r\ni) 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.\r\n\r\nii) 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}|)$.\r\n\r\nIn 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.