Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators
Wei Qi · IACR Communications in Cryptology · 2026
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 p o l y ( log n ) , where n is the number of accumulated values, then some values must incur Ω ( log n / log log n ) witness updates. This improves upon the recent ω ( 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.