Efficient KZG-Based Univariate Sum-Check and Lookup Argument

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