Paper 2022/1515

Succinct Vector, Polynomial, and Functional Commitments from Lattices

Hoeteck Wee, NTT Research, École Normale Supérieure - PSL
David J. Wu, The University of Texas at Austin

Vector commitment schemes allow a user to commit to a vector of values $\mathbf{x} \in \{0,1\}^\ell$ and later, open up the commitment to a specific set of positions. Both the size of the commitment and the size of the opening should be succinct (i.e., polylogarithmic in the length $\ell$ of the vector). Vector commitments and their generalizations to polynomial commitments and functional commitments are key building blocks for many cryptographic protocols. We introduce a new framework for constructing non-interactive lattice-based vector commitments and their generalizations. A simple instantiation of our framework yields a new vector commitment scheme from the standard short integer solution (SIS) assumption that supports private openings and large messages. We then show how to use our framework to obtain the first succinct functional commitment scheme that supports openings with respect to arbitrary bounded-depth Boolean circuits. In this scheme, a user commits to a vector $\mathbf{x} \in \{0,1\}^\ell$, and later on, open the commitment to any function $f(\mathbf{x})$. Both the commitment and the opening are non-interactive and succinct: namely, they have size $\textsf{poly}(\lambda, d, \log \ell)$, where $\lambda$ is the security parameter and $d$ is the depth of the Boolean circuit computing $f$. Previous constructions of functional commitments could only support constant-degree polynomials, or require a trusted online authority, or rely on non-falsifiable assumptions. The security of our functional commitment scheme is based on a new falsifiable family of "basis-augmented" SIS assumptions (BASIS) we introduce in this work. We also show how to use our vector commitment framework to obtain (1) a polynomial commitment scheme where the user can commit to a polynomial $f \in \mathbb{Z}_q[x]$ and subsequently open the commitment to an evaluation $f(x) \in \mathbb{Z}_q$; and (2) an aggregatable vector (resp., functional) commitment where a user can take a set of openings to multiple indices (resp., function evaluations) and aggregate them into a single short opening. Both of these extensions rely on the same BASIS assumption we use to obtain our succinct functional commitment scheme.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
functional commitmentpolynomial commitmentvector commitmentlattices
Contact author(s)
wee @ di ens fr
dwu4 @ cs utexas edu
2023-03-06: revised
2022-11-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hoeteck Wee and David J. Wu},
      title = {Succinct Vector, Polynomial, and Functional Commitments from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1515},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.