Updatable, Aggregatable, Succinct Mercurial Vector Commitment from Lattice

Vector commitments (VC) and their variants attract a lot of attention due to their wide range of usage in applications such as blockchain and accumulator. Mercurial vector commitment (MVC), as one of the important variants of VC, is the core technique for building more complicated cryptographic applications, such as the zero-knowledge set (ZKS) and zero-knowledge elementary database (ZK-EDB). However, to the best of our knowledge, the only post-quantum MVC construction is trivially implied by a generic framework proposed by Catalano and Fiore (PKC ’13) with lattice-based components which causes large auxiliary information and cannot satisfy any additional advanced properties, that is, updatable and aggregatable. A major difficulty in constructing a non-black-box lattice-based MVC is that it is not trivial to construct a lattice-based VC that satisfies a critical property called “mercurial hiding”. In this paper, we identify some specific features of a new falsifiable family of basis-augmented SIS assumption (BASIS) proposed by Wee and Wu (EUROCRYPT ’23) that can be utilized to construct the mercurial vector commitment from lattice satisfying updatability and aggregatability with smaller auxiliary information. We first extend stateless update and differential update to the mercurial vector commitment and define a new property, named updatable mercurial hiding. Then, we show how to modify our constructions to obtain the updatable mercurial vector commitment that satisfies these properties. To aggregate the openings, our constructions perfectly inherit the ability to aggregate in the BASIS assumption, which can break the limitation of weak binding in the current aggregatable MVCs. In the end, we show that our constructions can be used to build the various kinds of lattice-based ZKS and ZK-EDB directly within the existing framework.