Paper 2025/1378

Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators

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 the 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. Specifically, we show that if the accumulator value has bit-length \( \mathsf{poly}(\log n) \), where \( n \) is the number of accumulated values, then some values must incur \( \Omega(\log n / \log \log n) \) witness updates. This improves upon the recent \( \omega(1) \) lower bound of [BCCK25] and matches the upper bound in [MQ23]. Building on the framework of [MQR22], we introduce a new combinatorial structure that removes the fixed-update-time assumption. Our approach also applies to Registration-based Encryption [GHMR18], thereby resolving the open problem left in [MQR22]: it shows that the tight lower bound on decryption-update frequency continues to hold even without any fixed-update-time assumption.