Paper 2023/1469

SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions

Martin R. Albrecht, King's College London, SandboxAQ
Giacomo Fenzi, École Polytechnique Fédérale de Lausanne
Oleksandra Lapiha, Royal Holloway University of London
Ngoc Khanh Nguyen, École Polytechnique Fédérale de Lausanne

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.

Available format(s)
Public-key cryptography
Publication info
latticessuccinct argumentszkSNARKszero-knowledge
Contact author(s)
martin albrecht @ kcl ac uk
giacomo fenzi @ epfl ch
sasha lapiha 2021 @ live rhul ac uk
khanh nguyen @ epfl ch
2023-11-25: last of 4 revisions
2023-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin R. Albrecht and Giacomo Fenzi and Oleksandra Lapiha and Ngoc Khanh Nguyen},
      title = {SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1469},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.