Paper 2021/1207

Non-Malleable Vector Commitments via Local Equivocability

Lior Rotem
Gil Segev
Abstract

Vector commitments (VCs), enabling to commit to a vector and locally reveal any of its entries, play a key role in a variety of both classic and recently-evolving applications. However, security notions for VCs have so far focused on passive attacks, and non-malleability notions considering active attacks have not been explored. Moreover, existing frameworks that may enable to capture the non-malleability of VCs seem either too weak (non-malleable non-interactive commitments that do not account for the security implications of local openings) or too strong (non-malleable zero-knowledge sets that support both membership and non-membership proofs). We put forward a rigorous framework capturing the non-malleability of VCs, striking a careful balance between the existing weaker and stronger frameworks: We strengthen the framework of non-malleable non-interactive commitments by considering attackers that may be exposed to local openings, and we relax the framework of non-malleable zero-knowledge sets by focusing on membership proofs. In addition, we strengthen both frameworks by supporting (inherently-private) updates to entries of committed vectors, and discuss the benefits of non-malleable VCs in the context of both UTXO-based and account-based stateless blockchains, and in the context of simultaneous multi-round auctions (that have been adopted by the US Federal Communications Commission as the standard auction format for selling spectrum ranges). Within our framework we present a direct approach for constructing non-malleable VCs whose efficiency essentially matches that of the existing standard VCs. Specifically, we show that any VC can be transformed into a non-malleable one, relying on a new primitive that we put forth. Our new primitive, locally-equivocable commitments with all-but-one binding, is evidently both conceptually and technically simpler compared to multi-trapdoor mercurial trapdoor commitments (the main building block underlying existing non-malleable zero-knowledge sets), and admits more efficient instantiations based on the same number-theoretic assumptions.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2021
Keywords
Non-MalleabilityVector Commitments
Contact author(s)
lrotem @ cs stanford edu
segev @ cs huji ac il
History
2023-08-30: revised
2021-09-17: received
See all versions
Short URL
https://ia.cr/2021/1207
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1207,
      author = {Lior Rotem and Gil Segev},
      title = {Non-Malleable Vector Commitments via Local Equivocability},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1207},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1207}},
      url = {https://eprint.iacr.org/2021/1207}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.