Paper 2024/1647

Curve Forests: Transparent Zero-Knowledge Set Membership with Batching and Strong Security

Matteo Campanelli, Offchain Labs
Mathias Hall-Andersen, ZKSecurity
Simon Holmgaard Kamp, CISPA Helmholtz Center for Information Security
Abstract

Zero-knowledge for set membership is a building block at the core of several privacy-aware applications, such as anonymous payments, credentials and whitelists. We propose a new efficient construction for the batching variant of the problem, where a user intends to show knowledge of several elements (a batch) in a set without any leakage on the elements. Our construction is transparent—it does not requires a trusted setup—and based on Curve Trees by Campanelli, Hall-Andersen and Kamp (USENIX 2023). Our first technical contribution consists in techniques to amortize Curve Trees costs in the batching setting for which we crucially exploit its algebraic properties. Even for small batches we obtain speedups for proving, speedups for verification and reduction in proof size. Our second contribution is a modifications of a key technical requirement in Curve Trees (related to so called "permissible points") which arguably simplifies its design and obtains a stronger security property. In particular, our construction is secure even for the case where the commitment to the set is provided by the adversary (in contrast to the honest one required by the original Curve Trees).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Financial Cryptography and Data Security 2025
Keywords
curve treeszero knowledgeaccumulatorsmoneroset membershipbatching
Contact author(s)
binarywhalesinternaryseas @ gmail com
mathias @ hall-andersen dk
simon kamp @ cispa de
History
2025-02-15: last of 3 revisions
2024-10-12: received
See all versions
Short URL
https://ia.cr/2024/1647
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1647,
      author = {Matteo Campanelli and Mathias Hall-Andersen and Simon Holmgaard Kamp},
      title = {Curve Forests: Transparent Zero-Knowledge Set Membership with Batching and  Strong Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1647},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1647}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.