Bilinear-map accumulator [1] is more efficient than the RSA accumulator [2] but do you know any disadvantage for the bilinear-map accumulator when compared to RSA accumulator?

  • 2
    $\begingroup$ I've added related articles. [1] is the source for Bilinear-map accumulator and [2] is the performance comparison article. $\endgroup$
    – kelalaka
    Feb 3, 2020 at 21:55
  • $\begingroup$ @kelalaka verification cost is o(1) or o(n) for rsa accumulator? I am confusing about that. $\endgroup$
    – jhdm
    Apr 20, 2020 at 7:12

1 Answer 1


I will list two disadvantages that come to mind.

  1. A bilinear accumulator requires a public parameter which is linear in size, which means you need to have an upper bound on the number of data elements you would commit to the accumulator. The RSA accumulator requires a public parameter which is constant-sized.

  2. A bilinear accumulator does not allow dynamic updates. If you have an accumulated digest $$A = g_1^{\prod\limits_{i=1}^N (s+d_i)}\;\;\; (s = \text{ the trapdoor}) $$ and need to insert a new element $d$, you would need to update the accumulated digest to $A^{s+d} = A^s*A^d$. But in order to compute $A^s$ without the trapdoor, you would need to know the coefficients of the polynomial $f(X):=\prod\limits_{i=1}^N (X+d_i)$. You would then compute the coefficients of $Xf(X)$ and use those to compute $A^s$. Thus, inserting a single element has a run time of $O(N)$.

  • $\begingroup$ update cost in rsa dynamic accumulator is O(1). Am i right? $\endgroup$
    – jhdm
    Apr 1, 2020 at 9:21
  • $\begingroup$ Yes, that is correct. $\endgroup$ Apr 13, 2020 at 6:13
  • $\begingroup$ if i cancel 5 certificate, so what is the corresponding verification cost. How can i calculate it $\endgroup$
    – jhdm
    Apr 18, 2020 at 14:41
  • $\begingroup$ For example if i have five revoked certificate, what is the corresponding value of verification cost? $\endgroup$
    – jhdm
    Apr 18, 2020 at 14:49
  • $\begingroup$ verification cost is also o(1) or o(n) for rsa accumulator? $\endgroup$
    – jhdm
    Apr 19, 2020 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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