2
$\begingroup$

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?

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

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.

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

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.