Paper 2011/495

Vector Commitments and their Applications

Dario Catalano and Dario Fiore

Abstract

We put forward the study of a new primitive that we call {\em Vector Commitment} (VC, for short). Informally, VCs allow to commit to an ordered sequence of $q$ values $(m_1, \ldots, m_q)$ in such a way that one can later open the commitment at specific positions (e.g., prove that $m_i$ is the $i$-th committed message). For security, Vector Commitments are required to satisfy a notion that we call \emph{position binding} which states that an adversary should not be able to open a commitment to two different values at the same position. Moreover, what makes our primitive interesting is that we require VCs to be {\em concise}, i.e. the size of the commitment string and of its openings has to be independent of the vector length. We show two realizations of VCs based on standard and well established assumptions, such as RSA, and Computational Diffie-Hellman (in bilinear groups). Next, we turn our attention to applications and we show that Vector Commitments are useful in a variety of contexts, as they allow for compact and efficient solutions which significantly improve previous works either in terms of efficiency of the resulting solutions, or in terms of "quality" of the underlying assumption, or both. These applications include: Verifiable Databases with Efficient Updates, Updatable Zero-Knowledge Databases, and Universal Dynamic Accumulators.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Full version of the paper that is going to appear in the proceedings of PKC 2013
Keywords
Vector CommitmentsCommitmentsAccumulatorZero-Knowledge DatabasesVerifiable Databases
Contact author(s)
fiore @ cs nyu edu
History
2012-12-10: last of 3 revisions
2011-09-13: received
See all versions
Short URL
https://ia.cr/2011/495
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/495,
      author = {Dario Catalano and Dario Fiore},
      title = {Vector Commitments and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2011/495},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/495}},
      url = {https://eprint.iacr.org/2011/495}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.