IACR News item: 30 July 2025
Wei Qi
ePrint Report
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].
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].
Additional news items may be found on the IACR news page.