Paper 2024/1619
Structure-Preserving Compressing Primitives: Vector Commitments and Accumulators
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
-
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} }