Structure-Preserving Compressing Primitives: Vector Commitments and Accumulators

bstract. Compressing primitives such as accumulators and vector commitments, allow to represent large data sets with some compact, ideally constant-sized value. Moreover, they supportoperations like proving membership or non-membership with minimal, ideally also constantsized, storage and communication overhead. In recent years, these primitives have found numerous practical applications, with many constructions based on various hardness assumptions.So far, however, it has been elusive to construct these primitives in a strictly structure-preservingsetting, i.e., in a bilinear group in a way that messages, commitments and openings are all elements of the two source groups. Interestingly, backed by existing impossibility results, not evenconventional commitments with such constraints are known in this setting. However, in manypractical applications it would be convenient or even required to be structure-preserving, e.g.,to commit or accumulate group elements.In this paper we investigate whether strictly structure-preserving compressing primitives canbe realized. We close this gap by presenting the first strictly structure-preserving commitmentthat is shrinking (and in particular constant-size). We circumvent existing impossibility resultsby employing a more structured message space, i.e., a variant of the Diffie-Hellman messagespace. Our main results are constructions of structure-preserving vector commitments as wellas structure-preserving accumulators. We first discuss generic constructions and then presentconcrete constructions under the Diffie-Hellman Exponent assumption. To demonstrate theusefulness of our constructions, we discuss various applications.