Welcome to the resource topic for 2025/1378
Title:
Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators
Authors: Wei Qi
Abstract:We study additive positive accumulators, which maintain a short digest of a growing set such that each value in the set can prove membership via a generated witness. Due to compactness of the digest, previously added values may require updated witnesses as the set grows.
In this paper, we establish a trade-off between the bit-length of the accumulator value and the number of witness updates, using techniques generalized from [MQR22]. Specifically, we show that if the accumulator value has bit-length poly(log n), where n is the number of accumulated values, then some values must incur Ω(log n/ log log n) witness updates, which matches the upper bound in [MQ23]. This improves upon the recent ω(1) lower bound of [BCCK25]. Our techniques and results also apply to Registration-based Encryption[GHMR18].
ePrint: https://eprint.iacr.org/2025/1378
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .