Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi mathvariant="sans-serif">p</mml:mi> <mml:mi mathvariant="sans-serif">o</mml:mi> <mml:mi mathvariant="sans-serif">l</mml:mi> <mml:mi mathvariant="sans-serif">y</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> is the number of accumulated values, then some values must incur <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mi>log</mml:mi> <mml:mi>log</mml:mi> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> witness updates. This improves upon the recent <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ω</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> 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.