Paper 2024/1943

$\textsf{LiLAC}$: Linear Prover, Logarithmic Verifier and Field-agnostic Multilinear Polynomial Commitment Scheme

Abstract

In this paper, we propose $\textsf{LiLAC}$, a novel field-agnostic, transparent multilinear polynomial commitment scheme (MLPCS) designed to address key challenges in polynomial commitment systems. For a polynomial with $N$ coefficients, $\textsf{LiLAC}$ achieves $\mathcal{O}(N)$ prover time, $\mathcal{O}(\log N)$ verifier time, and $\mathcal{O}(\log N)$ proof size, overcoming the limitations of $\mathcal{O}(\log^2 N)$ verification time and proof size without any increase in other costs. This is achieved through an optimized polynomial commitment strategy and the recursive application of the tensor IOPP, making $\textsf{LiLAC}$ both theoretically optimal and practical for large-scale applications. Furthermore, $\textsf{LiLAC}$ offers post-quantum security, providing robust protection against future quantum computing threats. We propose two constructions of $\textsf{LiLAC}$: a field-agnostic $\textsf{LiLAC}$ and a field-specific $\textsf{LiLAC}$. Each construction demonstrates superior performance compared to the state-of-the-art techniques in their respective categories of MLPCS. First, the field-agnostic $\textsf{LiLAC}$ is compared against Brakedown (CRYPTO 2023), which is based on a tensor IOP and satisfies field-agnosticity. In experiments conducted over a 128-bit field with a coefficient size of $2^{30}$, the field-agnostic $\textsf{LiLAC}$ achieves a proof size that is $3.7\times$ smaller and a verification speed that is $2.2\times$ faster, while maintaining a similar proof generation time compared to Brakedown. Furthermore, the field-specific $\textsf{LiLAC}$ is evaluated against WHIR (ePrint 2024/1586), which is based on an FRI. With a 128-bit field and a coefficient size of $2^{30}$, the field-specific $\textsf{LiLAC}$ achieves a proof generation speed that is $2.8\times$ faster, a proof size that is $27\%$ smaller, and a verification speed that is $14\%$ faster compared to WHIR.