# 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

## 2 Answers

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? Dec 7, 2015 at 21:15
• Modular exponentiation is expensive. In terms of exponentiations, cost is exactly one for this particular accumulator. Dec 7, 2015 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. Dec 7, 2015 at 21:40
• And without the knowledge of the secret ϕ(n), is possible only add elements to accumulator (in a efficient way)? Dec 8, 2015 at 12:30
• Nope; it is possible, under some circumstances to delete in constant-time from an RSA accumulator without the trapdoor. See my full answer below. Feb 5, 2023 at 2:45

## Lattice-based accumulators

Yes, there exists an accumulator with $$O(1)$$ deletion time from lattices by Papamanthou et. al [PSTY13]. Specifically, given an old digest and the deleted element, one can easily compute the new digest. No auxiliary information is needed.

I do not know how its computational performance compares to RSA accumulators; likely more expensive. There was some (partial) exploration of its performance in [CPZ18], which you could investigate.

I do recall that its proof size is $$O(\log{n})$$, so it will be worse both asymptotically and concretely than RSA accumulator proof sizes.

## RSA accumulators

At the same time, note that there is also a way to update an RSA accumulator without the trapdoor.

Specifically, if you have a membership proof for the deleted element, then the updated accumulator is simply that membership proof.

It gets a little trickier if you want to update an RSA accumulator after two or more deletions. This requires a so-called "Shamir trick", which I'll explain below.

Let $$\mathsf{BatchDel}$$ denote the algorithm that updates the accumulator after two or more deletions.

Specifically, $$\mathsf{BatchDel}$$ takes an accumulator $$A_t$$ as input and deletes all the elements $$x_i$$ from it given a membership proof $$\pi_{x_i}^t$$ w.r.t. $$A_t$$ for each $$x_i$$

Then, $$\mathsf{BatchDel}$$ works as follows (screenshot from [BBF19]):

As you can see, $$\mathsf{BatchDel}$$ makes use of Shamir's trick, which in turn relies on computing Bezout coefficients (see screenshot below also from [BBF19]):

# References

[BBF19] Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains; by Boneh, Dan and Bünz, Benedikt and Fisch, Ben; in CRYPTO'19; 2019

[CPZ18] Edrax: A Cryptocurrency with Stateless Transaction Validation; by Alexander Chepurnoy and Charalampos Papamanthou and Yupeng Zhang; 2018; https://eprint.iacr.org/2018/968

[PSTY13] Streaming Authenticated Data Structures; by Papamanthou, Charalampos and Shi, Elaine and Tamassia, Roberto and Yi, Ke; in EUROCRYPT 2013; 2013