Paper 2022/696
On the Impossibility of Algebraic Vector Commitments in Pairing-Free Groups
Abstract
Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, algebraic constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes. In spite of their popularity, algebraic vector commitments remain poorly understood objects. In particular, no construction in standard prime order groups (without pairing) is known. In this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize. Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases. This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Vector Commitment Black-box separation Generic Group Model
- Contact author(s)
-
catalano @ dmi unict it
dario fiore @ imdea org
rosario @ protocol ai
emanuele giunta @ imdea org - History
- 2022-06-02: approved
- 2022-06-01: received
- See all versions
- Short URL
- https://ia.cr/2022/696
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/696, author = {Dario Catalano and Dario Fiore and Rosario Gennaro and Emanuele Giunta}, title = {On the Impossibility of Algebraic Vector Commitments in Pairing-Free Groups}, howpublished = {Cryptology ePrint Archive, Paper 2022/696}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/696}}, url = {https://eprint.iacr.org/2022/696} }