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?

  • $\begingroup$ A witness is usually (e.g. zero-knowledge arguments, accumulators, or verifiable computation) used to convince a verifier of something that the prover knows, but the verifier doesn't. Inherently, there is some asymmetry between the prover's and the verifier's "knowledge". In the setting you describe, everybody can compute a witness and there is no prover that has any extra secret knowledge. So why would a verifier need a witness instead of checking whether some element is in $x$ by itself. If this question is not about privacy, but just about efficiency, then what about bloom filters? $\endgroup$ – ZeroKnowledge Apr 13 at 16:35
  • $\begingroup$ The asymmetry is there: the verifier doesn't know if $x_i$ is in the set, the prover does. The prover can compute $w_i$ and provide it to the verifier to prove that $x_i$ is in the set. But you are right, this is more about efficiency than privacy. Bloom filters won't work, however: at the acceptable rate of false positives, they require too much storage. $\endgroup$ – irakliy Apr 13 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.