I'm looking for a data structure that would allow anyone to compute a witness for an element without knowing all other elements within the accumulator/set. Specifically:
- Suppose there is a set of elements $X$ consisting of elements $x_1$, $x_2$ ... $x_n$ which are accumulated into $Acc(X)$.
- Suppose also that the only things I know about this set are $Acc(X)$ and that value $x_i$ is in the accumulator.
- From this data, I would like to generate a witness $w_i$ to prove that $x_i$ is present in the accumulator.
As an example, a data structure like a merkle tree would not work here because knowing just the root of the tree and one of the values in the tree, I would not be able to generate a proof for that value.
Similarly, an RSA accumulator would not work since I can't generate a proof for an element without knowing some other auxiliary info.
Does a data structure I'm looking for exist?
Edit: the only thing that I was able to find close to this is Efficient Asynchronous Accumulators for Distributed PKI. It doesn't fully satisfy the criteria I outlined above, but it does not require a witness to be re-computed on every add. The witness needs to be re-computed only in $Log(N)$, where $N$ is the number of updates after an element is added. Is there anything better than this construct?