Paper 2023/846

Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency

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 17MB proof size for $2^{20}$ constraints, which is 15X smaller than currently the only publicly-verifiable lattice-based SNARK proposed by Albrecht et al.

Note: Changelog: - New author - Switch from decisional NTRU to statistical NTRU - Added a proof that coordinate-wise special soundness implies knowledge soundness in the interactive setting - Added a proof that coordinate-wise special soundness implies knowledge soundness in the random oracle model under Fiat-Shamir transformation - Small bug fixes