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
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
functional commitment polynomial commitment vector commitment lattices
Contact author(s)
wee @ di ens fr
dwu4 @ cs utexas edu
History
2022-11-07: approved
2022-11-02: received
See all versions
Short URL
https://ia.cr/2022/1515
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.