Efficient KZG-Based Univariate Sum-Check and Lookup Argument

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