# Inclusion and Exclusion proofs in RSA accumulators

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?

## 1 Answer

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.