Paper 2024/1943

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

Abstract

In this paper, we propose $$, a novel field-agnostic, transparent multilinear polynomial commitment scheme (MLPCS) designed to address key challenges in polynomial commitment systems. For a polynomial with $$ coefficients, $$ achieves $$ prover time, $$ verifier time, and $$ proof size, overcoming the limitations of $$ 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 $$ both theoretically optimal and practical for large-scale applications. Furthermore, $$ offers post-quantum security, providing robust protection against future quantum computing threats. We propose two constructions of $$: a field-agnostic $$ and a field-specific $$. Each construction demonstrates superior performance compared to the state-of-the-art techniques in their respective categories of MLPCS. First, the field-agnostic $$ 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 $$, the field-agnostic $$ achieves a proof size that is $$ smaller and a verification speed that is $$ faster, while maintaining a similar proof generation time compared to Brakedown. Furthermore, the field-specific $$ is evaluated against WHIR (ePrint 2024/1586), which is based on an FRI. With a 128-bit field and a coefficient size of $$, the field-specific $$ achieves a proof generation speed that is $$ faster, a proof size that is $$ smaller, and a verification speed that is $$ faster compared to WHIR.