Paper 2026/2592

A Post Quantum Vector Commitment Scheme with Efficient Insertions and Deletions

Abstract

Vector Commitments (VCs) are a cryptographic primitive that allows users to commit to a tuple and later provide proofs about entries of the committed tuple. Literature on VCs provides many secure constructions with properties attractive for decentralized applications. These include fast commitment/proof update algorithms after a value in the committed vector changes, algorithms to aggregate position proofs, generating proofs for subvectors, commitment hiding, and many more. However, these works assume a static setting, where only vector values change and the length of the committed vector never changes. We initiate the study of designing VCs which support efficient updates to commitments and proofs after a change in vector length occurs (i.e. an insertion or a deletion of a vector value at an \textit{arbitrary} position). In order to construct such a primitive, we formalize a VC framework implicitly considered in VC based verifiable decentralized storage constructions. Parties control a subset of positions in the committed vector. A proof for an inserted vector value at a given position may only be generated via participation from enough honest parties. We call such primitives \textit{Multiparty Dynamic Vector Commitments}. Our work provides formal definitions for multiparty dynamic VC functionality and security. In particular, standard VC binding does not extend to our dynamic setting. This motivates us to define the \textit{dynamic multiparty binding} security notion. We also comment on how multiparty dynamic VCs can be applied to extend existing VC based instantiations of verifiable storage. Finally, we provide a vector commitment construction and show that it possesses multiparty dynamic binding under standard lattice assumptions.