CryptoDB
Efficient KZG-based Univariate Sum-check and Lookup Argument
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | PKC 2024 |
| Abstract: | We propose a novel KZG-based sum-check scheme, dubbed $\mathsf{Losum}$, with \emph{optimal} efficiency. Particularly, its proving cost is \emph{one} multi-scalar-multiplication of size $k$---the number of non-zero entries in the vector, its verification cost is \emph{one} pairing plus one group scalar multiplication, and the proof consists of only \emph{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}$++. |
BibTeX
@inproceedings{pkc-2024-33708,
title={Efficient KZG-based Univariate Sum-check and Lookup Argument},
publisher={Springer-Verlag},
author={Yuncong Zhang and Shi-Feng Sun and Dawu Gu},
year=2024
}