Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage

Matteo Campanelli; Dario Fiore; Nicola Greco; Dimitris Kolonelos; Luca Nizzardo

Paper 2020/149

Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage

Matteo Campanelli, Dario Fiore, Nicola Greco, Dimitris Kolonelos, and Luca Nizzardo

Abstract

Vector commitments with subvector openings (SVC) [Lai-Malavolta, Boneh-Bunz-Fisch; CRYPTO'19] allow one to open a committed vector at a set of positions with an opening of size independent of both the vector's length and the number of opened positions. We continue the study of SVC with two goals in mind: improving their efficiency and making them more suitable to decentralized settings. We address both problems by proposing a new notion for VC that we call incremental aggregation and that allows one to merge openings in a succinct way an unbounded number of times. We show two applications of this property. The first one is immediate and is a method to generate openings in a distributed way. For the second one, we use incremental aggregation to design an algorithm for faster generation of openings via preprocessing. We then proceed to realize SVC with incremental aggregation. We provide two constructions in groups of unknown order that, similarly to that of Boneh et al. (which supports only one-hop aggregation), have constant-size public parameters, commitments and openings. As an additional feature, for the first construction we propose efficient arguments of knowledge of subvector openings which immediately yields a keyless proof of storage with compact proofs. Finally, we address a problem closely related to that of SVC: storing a file efficiently in completely decentralized networks. We introduce and construct verifiable decentralized storage (VDS), a cryptographic primitive that allows to check the integrity of a file stored by a network of nodes in a distributed and decentralized way. Our VDS constructions rely on our new vector commitment techniques.

Note: Updated title and presentation improvements

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in ASIACRYPT 2020
Keywords: distributed cryptography public-key cryptography implementation vector commitments
Contact author(s): matteo campanelli @ gmail com
dario fiore @ imdea org
dimitris kolonelos @ imdea org
History: 2020-09-11: last of 6 revisions; 2020-02-13: received; See all versions
Short URL: https://ia.cr/2020/149
License: CC BY

BibTeX

@misc{cryptoeprint:2020/149,
      author = {Matteo Campanelli and Dario Fiore and Nicola Greco and Dimitris Kolonelos and Luca Nizzardo},
      title = {Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/149},
      year = {2020},
      url = {https://eprint.iacr.org/2020/149}
}