5
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ 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?? $\endgroup$ – fgrieu Nov 27 '15 at 17:20
  • 1
    $\begingroup$ 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. $\endgroup$ – 4nf3rt Dec 4 '15 at 17:10
  • $\begingroup$ I have a doubt: the RSA Accumulator is like an incremental hashing function? $\endgroup$ – 4nf3rt Dec 14 '15 at 11:24
3
$\begingroup$

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*}

To answer your first question,

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$.

To answer your second question,

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 :)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maeher Jan 31 '18 at 1:36
  • $\begingroup$ 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. $\endgroup$ – Alin Tomescu Jan 31 '18 at 9:53
  • $\begingroup$ 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. $\endgroup$ – Maeher Jan 31 '18 at 9:57
  • $\begingroup$ 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. $\endgroup$ – Alin Tomescu Jan 31 '18 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.