Martin R. Albrecht
King’s College London and SandboxAQ

Giacomo Fenzi
EPFL

Oleksandra Lapiha
Royal Holloway University of London

Ngoc Khanh Nguyen
King’s College London

Keywords:

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 in the random oracle model. 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 interactive version of the construction is secure under a “multi-instance version” of the Power-Ring BASIS assumption (Eprint 2023/846). We then base security on the Module-SIS assumption by introducing several re-randomisation techniques which can be of independent interest.