Welcome to the resource topic for 2024/1943
Title:
\textsf{LiLAC}: Linear Prover, Logarithmic Verifier and Field-agnostic Multilinear Polynomial Commitment Scheme
Authors: Kyeongtae Lee, Seongho Park, Byeongjun Jang, Jihye Kim, Hyunok Oh
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.
ePrint: https://eprint.iacr.org/2024/1943
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .