Updatable, Aggregatable, Succinct Mercurial Vector Commitment from Lattice

Abstract

<p>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 <em>large</em> auxiliary information and <em>cannot satisfy</em> any additional advanced properties, that is, updatable and aggregatable.</p><p>A major difficulty in constructing a <em>non-black-box</em> 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 <em>satisfying</em> updatability and aggregatability with <em>smaller</em> auxiliary information. We <em>first</em> extend stateless update and differential update to the mercurial vector commitment and define a <em>new</em> 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 <em>weak</em> 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.</p>