Paper 2024/1619

Structure-Preserving Compressing Primitives: Vector Commitments and Accumulators

Stephan Krenn, Austrian Institute of Technology
Omid Mir, Austrian Institute of Technology
Daniel Slamanig, Universität der Bundeswehr München, Germany
Abstract

Compressing primitives such as accumulators and vector commitments, allow to rep- resent large data sets with some compact, ideally constant-sized value. Moreover, they support operations like proving membership or non-membership with minimal, ideally also constant- sized, storage and communication overhead. In recent years, these primitives have found nu- merous 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-preserving setting, i.e., in a bilinear group in a way that messages, commitments and openings are all ele- ments of the two source groups. Interestingly, backed by existing impossibility results, not even conventional commitments with such constraints are known in this setting. However, in many practical 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 can be realized. We close this gap by presenting the first strictly structure-preserving commitment that is shrinking (and in particular constant-size). We circumvent existing impossibility results by employing a more structured message space, i.e., a variant of the Diffie-Hellman message space. Our main results are constructions of structure-preserving vector commitments as well as structure-preserving accumulators. We first discuss generic constructions and then present concrete constructions under the Diffie-Hellman Exponent assumption. To demonstrate the usefulness of our constructions, we discuss various applications.

Note: Fixed the proof in Theorem 1 and updated the applicaiton section

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Structure-PreservingVector CommitmentsAccumulators
Contact author(s)
stephan krenn @ ait ac at
omid mir @ ait ac at
daniel slamanig @ unibw de
History
2025-02-19: last of 2 revisions
2024-10-10: received
See all versions
Short URL
https://ia.cr/2024/1619
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1619,
      author = {Stephan Krenn and Omid Mir and Daniel Slamanig},
      title = {Structure-Preserving Compressing Primitives: Vector Commitments and Accumulators},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1619},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1619}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.