I would like a proof that accomplishes the following:

$N$ strings are part of a set $S$. There is a do_proof function on set $S$ that produces a succinct witness statement $P$.

$$P = \text{do_proof}(S)$$

For some new string $X$ that is not part of set $S$, I have some proof

$$\text{prove_not_a_member}(X, P) = \text{True}$$

that proves that $X$ is not a member of $S$. Assume that $S$ is large and $P$ is constrained in size.

I was thinking about aggregate signatures but I'm not sure. Basically I am looking for a way to succinctly prove non-membership. It does not have to be zero-knowledge.

Is there a cryptographic solution to provide a “proof of exclusion”?

  • $\begingroup$ Could you please edit your question and add some details related to the exact scenario? Currently I am not really clear about the reason for not being able to use a “proof of membership”. – In that case a result is_a_member = false boils down to an alike “isn’t a member’ result and it would surely simplify many aspects of your problem. Things like group signatures and ring signatures come to mind, somewhat as described in the Proving membership of a group without revealing identity? Q&A $\endgroup$ – e-sushi Dec 16 '17 at 9:47
  • $\begingroup$ On the other side, there’s the Proof of non-membership on a Merkle tree? Q&A which could render your question a duplicate. $\endgroup$ – e-sushi Dec 16 '17 at 10:02
  • $\begingroup$ What, specifically, do you mean by "succint"? Constant size? Sub-linear in $|S|$? And can you tolerate some risk of failures (i.e. some $X \notin S$ such that the non-membership proof fails)? It seems to me that if you want a sub-linear proof, can't tolerate a non-negligible failure rate, and if $S$ has no special structure, then you're going to bump against Shannon's source coding theorem which basically says that there's no way to losslessly compress arbitrary random data. $\endgroup$ – Ilmari Karonen Dec 16 '17 at 21:23

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.