# Deletion in RSA Accumulator

I am studying RSA Dynamic Accumulators and I have a question: why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known? Is possible to calculate the deletion only with the RSA modulus $N$?

• The notion of RSA-based Dynamic Accumulator, and deletion for such, is not so common that you can dispense including in the question (preferably) a definition, or at least a reference. Is what you study: Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic An Efficient Dynamic and Distributed RSA Accumulator (arXiv:0905.1307, 2009)? Or??
– fgrieu
Nov 27, 2015 at 17:20
• I found this question (crypto.stackexchange.com/questions/5791/…) that explains why is important to keep the ϕ(n) secret, because with that value is simple to calculate the inverse, and then the deletion of an element. Dec 4, 2015 at 17:10
• I have a doubt: the RSA Accumulator is like an incremental hashing function? Dec 14, 2015 at 11:24

I'm assuming you are talking about the typical dynamic RSA accumulator from "Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials", by Camenicsh and Lysyanskaya (see PDF here).

First, recall that the accumulator over prime elements $$x_1, x_2, \dots, x_n$$ is computed in $$O(n)$$ time as: \begin{align*} A &= g^{x_1 x_2 \cdots x_n} \end{align*}

Second, recall that after removing some $$x_i$$ from the accumulator $$A$$, we end up with a new accumulator $$A'$$: \begin{align*} A' &= g^{x_1 x_2 \cdots x_{i-1} x_i \cdots x_n} \end{align*}

Why is it simpler to calculate the new accumulator value after a deletion if the secret $$\phi(N)$$ is known?

Because knowing $$\phi(N)$$ allows us to easily compute $$A'$$ from $$A$$ as follows: \begin{align*} A' &= A^{{x_i}^{-1} \bmod \phi(N)} \end{align*}

To understand this, recall that additions and multiplications are reduced modulo $$\phi(N)$$ "in the exponent." Also recall that numbers that are coprime with $$\phi(N)$$ (e.g., $$x_i$$) have multiplicative inverses $$\bmod \phi(N)$$ [1].

Note that you can compute $$A'$$ from $$A$$ directly, without needing to know the other accumulated elements $$x_j, j\ne i$$.

Is possible to calculate the deletion only with the RSA modulus $$N$$?

I'm assuming you mean "calculate the new accumulator." The answer is "yes," and you can probably see why. Remember that, just like we can compute $$A$$ in $$O(n)$$ time, we can also compute $$A'$$ in $$O(n)$$ time (i.e., by repeated exponentiations): \begin{align*} A' &= ((((((g^{x_1})^{x_2}) \cdots)^{x_{i-1}})^{x_i})\cdots)^{x_n}\\ &= g^{x_1 x_2 \cdots x_{i-1} x_i \cdots x_n} \end{align*}

Later edit: As @Maeher nicely pointed out, without the trapdoor you need to know the other elements $$x_j, j\ne i$$ in order to remove $$x_i$$, since removing is just recomputing the accumulator without $$x_i$$.

If you are interested in an accumulator where you can both add and remove without knowing the other elements, you can read the elegant work by Papamanthou et al on "Streaming Authenticated Data Structures" from EUROCRYPT'13 (PDF here). Computing new witnesses requires knowing at least part of the accumulated elements, since the construction is merely a different kind of Merkle tree. However, unlike a Merkle tree, existing witnesses can be updated given just the added/deleted elements (no need for additional sibling paths). Currently, this accumulator is based on lattices and will be less efficient.

Still, Qian et al implemented it in "Streaming Authenticated Data Structures: Abstraction and Implementation" at CCSW'14 (PDF behind paywall).

Hope this helps 2 years later :)

• In the second part of your answer, you seem to assume that all the $x_i$ are actually known. I would think that whether that is true or not heavily depends on the application. Jan 31, 2018 at 1:36
• Not sure what you mean by "known." Can you give me an example of a scheme that deletes an "unknown" value? Of course $x_i$ can be a commitment to $d_i$ such as $H(d_i, r_i)$, as long as you "tweak" the hash to be a prime number. Jan 31, 2018 at 9:53
• Sorry, I should not have used $i$ as the index. I'm taking about all the other $x_j$ for $j \neq i$. It is not clear to me why you should know all of those when deleting $x_i$ and it seem that you would have to. Jan 31, 2018 at 9:57
• Ah, I see what you mean! Yes, in the RSA accumulator if you want to delete an element but don't know the trapdoor, you need this so-called auxiliary information: all the elements in the accumulator. There is a lattice-based accumulator by Papamanthou et al that doesn't have this problem. See "Streaming Authenticated Data Structures" by Papamanthou, Shi, Tamassia and Yi. I will updated my answer to reflect this. Jan 31, 2018 at 10:02
• How do you use the trapdoor to prove membership using just the accumulator's value? Nov 29, 2019 at 21:31