# 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. – CodesInChaos Dec 7 '15 at 20:59
• Yes, I mean respect to number of elements. – 4nf3rt Dec 7 '15 at 21:08

## 1 Answer

Given the trapdoor, one would delete an element from RSA accumulator in constant time. In particular, produce an inverse to the element with extended Euclid algorithm and power-to accumulator to the inverse. The element in question would cancel-out from accumulator this way.

• But in general, deletion is slower than add an element? – 4nf3rt Dec 7 '15 at 21:15
• Modular exponentiation is expensive. In terms of exponentiations, cost is exactly one for this particular accumulator. – Vadym Fedyukovych Dec 7 '15 at 21:27
• 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. – Vadym Fedyukovych Dec 7 '15 at 21:40
• And without the knowledge of the secret ϕ(n), is possible only add elements to accumulator (in a efficient way)? – 4nf3rt Dec 8 '15 at 12:30