# Deletion complexity in a RSA accumulator

My question is about the existence of a dynamic RSA accumulator with deletion of an element in O(1) time.

Do you know some practical implementation?

• When you say O(1) you mean with respect to the number of elements in the accumulator, right? Because the cost obviously increases with increasing modulus size. Dec 7, 2015 at 20:59
• Yes, I mean respect to number of elements. Dec 7, 2015 at 21:08

• It would be better to include a definition and refer to an implementation, giving a background to the answer above. Yes, accumulated value is $A_i$, equation (2) at Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic, An Efficient Dynamic and Distributed RSA Accumulator (arXiv:0905.1307, 2009). Thanx fgrieu. Please note a fast deletion was suggested with trapdoor access at the answer; without trapdoor one need to re-calculate the accumulator in $n$ exponentiations. Dec 7, 2015 at 21:40