Welcome to the resource topic for 2024/618
Title:
Efficient KZG-based Univariate Sum-check and Lookup Argument
Authors: Yuncong Zhang, Shi-Feng Sun, Dawu Gu
Abstract:We propose a novel KZG-based sum-check scheme, dubbed \mathsf{Losum}, with optimal efficiency. Particularly, its proving cost is one multi-scalar-multiplication of size k—the number of non-zero entries in the vector, its verification cost is one pairing plus one group scalar multiplication, and the proof consists of only one group element.
Using \mathsf{Losum} as a component, we then construct a new lookup argument, named \mathsf{Locq}, which enjoys a smaller proof size and a lower verification cost compared to the state of the arts \mathsf{cq}, \mathsf{cq}+ and \mathsf{cq}++. Specifically, the proving cost of \mathsf{Locq} is comparable to \mathsf{cq}, keeping the advantage that the proving cost is independent of the table size after preprocessing. For verification, \mathsf{Locq} costs four pairings, while \mathsf{cq}, \mathsf{cq}+ and \mathsf{cq}++ require five, five and six pairings, respectively. For proof size, a \mathsf{Locq} proof consists of four \mathbb{G}_1 elements and one \mathbb{G}_2 element; when instantiated with the BLS12-381 curve, the proof size of \mathsf{Locq} is 2304 bits, while \mathsf{cq}, \mathsf{cq}+ and \mathsf{cq}++ have 3840, 3328 and 2944 bits, respectively. Moreover, \mathsf{Locq} is zero-knowledge as \mathsf{cq}+ and \mathsf{cq}++, whereas \mathsf{cq} is not. \mathsf{Locq} is more efficient even compared to the non-zero-knowledge (and more efficient) versions of \mathsf{cq}+ and \mathsf{cq}++.
ePrint: https://eprint.iacr.org/2024/618
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 .