I am reading about RSA accumulators from this video and few other sources. I had a confusion whether the complete set is needed to construct a proof of inclusion/exclusion in an RSA accumulator or is it possible to create the proof of inclusion/exclusion just by knowing the accumulator root and the value for which membership/non-membership proof has to be provided. Can someone please clarify this?


Assuming you don't know the trapdoor of the accumulator.

The answer depends, if the value is already present in the accumulator, then you need all the elements to generate the witness. If it is to be added, then the witness is the accumulator value before the addition of the new value.

eg. If you have elements $S_1 = \{x_1, x_2, ... x_k\}$, the accumulator is $A_{S_1} = g^{\prod_{i=0}^k x_i} $. Now if $y_1$ is to be added, the set will become $S_2 = \{x_1, x_2, ... x_k, y_1\}$ and the accumulator will become $A_{S_2} = g^{{\prod_{i=0}^k x_i} . y_1} $. The witness for $y_1$ is $A_{S_1}$.

But once you have witness for an element, updating the witness as the accumulator changes should take time proportional to changes in accumulator.


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.