Paper 2020/149

Vector Commitment Techniques and Applications to Verifiable Decentralized Storage

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

Abstract

Vector commitments with subvector openings (SVC) [Lai-Malavolta and 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 propose a new SVC construction in groups of unknown order that, similarly to that of Boneh et al. has constant-size public parameters, commitments and openings, but in addition enjoys new features. First, our SVC has incremental aggregation: one can merge openings in a succinct way an unbounded number of times. Thanks to incremental aggregation we obtain: faster generation of openings via preprocessing, and a method to generate openings in a distributed way. Second, we propose efficient arguments of knowledge of subvector openings for our SVC, which immediately yields a keyless proof of storage with compact proofs. Finally, we introduce and contruct 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.