Vector and Functional Commitments from Lattices

Chris Peikert, Zachary Pepin, and Chad Sharp

Abstract

Vector commitment (VC) schemes allow one to commit concisely to an ordered sequence of values, so that the values at desired positions can later be proved concisely. In addition, a VC can be statelessly updatable, meaning that commitments and proofs can be updated to reflect changes to individual entries, using knowledge of just those changes (and not the entire vector). VCs have found important applications in verifiable outsourced databases, cryptographic accumulators, and cryptocurrencies. However, to date there have been relatively few post-quantum constructions, i.e., ones that are plausibly secure against quantum attacks. More generally, functional commitment (FC) schemes allow one to concisely and verifiably reveal various functions of committed data, such as linear functions (i.e., inner products, including evaluations of a committed polynomial). Under falsifiable assumptions, all known functional commitments schemes have been limited to linearizable'' functions, and there are no known post-quantum FC schemes beyond ordinary VCs. In this work we give post-quantum constructions of vector and functional commitments based on the standard Short Integer Solution lattice problem (appropriately parameterized): \begin{itemize} \item First, we present new statelessly updatable VCs with significantly shorter proofs than (and efficiency otherwise similar to) the only prior post-quantum, statelessly updatable construction (Papamanthou \etal, EUROCRYPT 13). Our constructions use private-key setup, in which an authority generates public parameters and then goes offline. \item Second, we construct functional commitments for \emph{arbitrary (bounded) Boolean circuits} and branching programs. Under falsifiable assumptions, this is the first post-quantum FC scheme beyond ordinary VCs, and the first FC scheme of any kind that goes beyond linearizable functions. Our construction works in a new model involving an authority that generates the public parameters and remains online to provide public, reusable opening keys'' for desired functions of committed messages. \end{itemize}

Available format(s)
Publication info
Keywords
latticesSIS problemvector commitmentsfunctional commitmentsGSW fully homomorphic encryption
Contact author(s)
cpeikert @ umich edu
zapepin @ umich edu
cmlsharp @ umich edu
History
Short URL
https://ia.cr/2021/1254

CC BY

BibTeX

@misc{cryptoeprint:2021/1254,
author = {Chris Peikert and Zachary Pepin and Chad Sharp},
title = {Vector and Functional Commitments from Lattices},
howpublished = {Cryptology ePrint Archive, Paper 2021/1254},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1254}},
url = {https://eprint.iacr.org/2021/1254}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.