Paper 2022/1515
Succinct Vector, Polynomial, and Functional Commitments from Lattices
Abstract
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 noninteractive latticebased 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 boundeddepth 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 noninteractive 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 constantdegree polynomials, or require a trusted online authority, or rely on nonfalsifiable assumptions. The security of our functional commitment scheme is based on a new falsifiable family of "basisaugmented" 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2023
 Keywords
 functional commitmentpolynomial commitmentvector commitmentlattices
 Contact author(s)

wee @ di ens fr
dwu4 @ cs utexas edu  History
 20230306: revised
 20221102: received
 See all versions
 Short URL
 https://ia.cr/2022/1515
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1515, 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{https://eprint.iacr.org/2022/1515}}, url = {https://eprint.iacr.org/2022/1515} }