Paper 2025/1903

Serval: Slack-Free ℓ2-Sound Polynomial Commitments from Lattices

Abstract

Polynomial commitment schemes (PCSs) are a core primitive in modern proof systems, especially SNARKs. Lattice-based PCSs are a natural post-quantum alternative, but existing constructions typically enforce lattice smallness only up to a multiplicative slack in the extracted $\ell_2$ norm. We present Serval, a lattice-based PCS with \emph{slack-free} $\ell_2$ soundness (norm-preserving extraction) under standard SIS/LWE-type assumptions. Following the norm-proof paradigm of Lyubashevsky~\etal (Crypto~'22), we reduce exact $\ell_2$ enforcement to a self-inner-product argument plus a binary validation that avoids modular wraparound. Our main technical insight is a reduction that rewrites the binary check as inner-product-shaped constraints that match the algebraic form of the PCS evaluation and commitment-consistency checks. This alignment yields a unified divide-and-conquer protocol that proves all constraints simultaneously in $O(\log L)$ rounds, giving succinct evaluation proofs and efficient verification. At $L = 2^{20}$ and matched security parameters ($\lambda = 128$), our instantiated proof size is $8 \times$ smaller than Fenzi~\etal (JoC~'24) and $85 \times$ smaller than SLAP (Eurocrypt~'24), while remaining compatible with the recent construction of Cini~\etal (Crypto~'24).

Note: This is an optimization work of https://eprint.iacr.org/2025/922. The updates include the addition of implementations, norm proofs, and other improvements.