Inclusion and Exclusion proofs in RSA accumulators

Question

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?

Answer 1

No and Yes! For the inclusion proof you either need the trapdoor or the accumulated set. However, it is possible to generate exclusion proofs without knowing the trapdoor, i.e. the factorization of the modulus, $N=p\cdot q$, or the size of the group, i.e. $\phi(N)$.

Let $A$ denote the accumulator's current value, $x$ an item, $g$, a generator of the group and $\pi$ the inclusion/exclusion proofs. All arithmetics are done $\mod N$. Also note, that all items (accumulated elements) are primes.

$inclusionProof(A,x): \pi =A^{\frac{1}{x}}$. Note, that this is only computable if you know the order of the group or the accumulated set as computing $x$th root $\mod N$ is assumed to be hard without knowing the factorization of $N$.

Verifying inclusion proofs is easy, one just need to check whether $\pi^x=A$. Once the item is accumulated, one can easily update her inclusion witnesses.

Let $A=g^u$ be, then,

$exclusionProof(A,x):$ Since $x$ is not accumulated this implies that $gcd(u,x)=1,$ therefore one can compute $a,b$, so-called Bezout-coefficients, such that $ax+bu=gcd(x,u)=1$. Hence $\pi=(g^a,b).$ Verifying the proof is done by checking $(g^a)^x\cdot A^b=g^{ax+ub}=g$.

Batching inclusion/exclusion proofs is also achievable. See this recent result.

Answer 2

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.