Welcome to the resource topic for 2022/1515
Title:
Succinct Vector, Polynomial, and Functional Commitments from Lattices
Authors: Hoeteck Wee, David J. Wu
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 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 Boolean circuits of bounded depth. In this scheme, a user can commit 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 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 (and 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.
ePrint: https://eprint.iacr.org/2022/1515
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .