Paper 2024/618

Efficient KZG-based Univariate Sum-check and Lookup Argument

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 $$ as a component, we then construct a new lookup argument, named $$, which enjoys a smaller proof size and a lower verification cost compared to the state of the arts $$, $$+ and $$++. Specifically, the proving cost of $$ is comparable to $$, keeping the advantage that the proving cost is independent of the table size after preprocessing. For verification, $$ costs four pairings, while $$, $$+ and $$++ require five, five and six pairings, respectively. For proof size, a $$ proof consists of four $$ elements and one $$ element; when instantiated with the BLS12-381 curve, the proof size of $$ is $$ bits, while $$, $$+ and $$++ have $$, $$ and $$ bits, respectively. Moreover, $$ is zero-knowledge as $$+ and $$++, whereas $$ is not. $$ is more efficient even compared to the non-zero-knowledge (and more efficient) versions of $$+ and $$++.