Paper 2023/1469

SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions

Abstract

Recent works on lattice-based extractable polynomial commitments can be grouped into two classes: (i) non-interactive constructions that stem from the functional commitment by Albrecht, Cini, Lai, Malavolta and Thyagarajan (CRYPTO 2022), and (ii) lattice adaptations of the Bulletproofs protocol (S&P 2018). The former class enjoys security in the standard model, albeit a knowledge assumption is desired. In contrast, Bulletproof-like protocols can be made secure under falsifiable assumptions, but due to technical limitations regarding subtractive sets, they only offer inverse-polynomial soundness error. This issue becomes particularly problematic when transforming these protocols to the non-interactive setting using the Fiat-Shamir paradigm. In this work, we propose the first lattice-based non-interactive extractable polynomial commitment scheme which achieves polylogarithmic proof size and verifier runtime (in the length of the committed message) under standard assumptions. At the core of our work lies a new tree-based commitment scheme, along with an efficient proof of polynomial evaluation inspired by FRI (ICALP 2018). Natively, the construction is secure under a “multi-instance version” of the Power-Ring BASIS assumption (Eprint 2023/846). We then fully reduce security to the Module-SIS assumption by introducing several re-randomisation techniques which can be of independent interest.

Note: Changelog: (08/10/23) - Added reduction from 2k-M-ISIS to Twin-k-M-ISIS and minor fixes. Changelog: (15/10/23) - Updated references. Changelog: (19/10/23) - Updated acknowledgements. Changelog: (25/11/23) - Fixed some references.