Welcome to the resource topic for 2023/846
Title:
Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency
Authors: Giacomo Fenzi, Ngoc Khanh Nguyen
Abstract:Polynomial commitments schemes are a powerful tool that enables one party to commit to a polynomial p of degree d, and prove that the committed function evaluates to a certain value z at a specified point u, i.e. p(u) = z, without revealing any additional information about the polynomial. Recently, polynomial commitments have been extensively used as a cryptographic building block to transform polynomial interactive oracle proofs (PIOPs) into efficient succinct arguments.
In this paper, we propose a lattice-based polynomial commitment that achieves succinct proof size and verification time in the degree d of the polynomial. Extractability of our scheme holds in the random oracle model under a natural ring version of the BASIS assumption introduced by Wee and Wu (EUROCRYPT 2023). Unlike recent constructions of polynomial commitments by Albrecht et al. (CRYPTO 2022), and by Wee and Wu, we do not require any expensive preprocessing steps, which makes our scheme particularly attractive as an ingredient of a PIOP compiler for succinct arguments.
We further instantiate our polynomial commitment, together with the Marlin PIOP (Eurocrypt 2020), to obtain a publicly-verifiable trusted-setup succinct argument for Rank-1 Constraint System (R1CS). Performance-wise, we achieve 26 MB proof size for 2^{20} constraints, which is 10X smaller than currently the only publicly-verifiable lattice-based SNARK proposed by Albrecht et al.
ePrint: https://eprint.iacr.org/2023/846
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 .