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”?

  • 1
    $\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
  • 1
    $\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
  • 1
    $\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

As shown recently$^1$ in [BBF], this can be carried out using universal accumulators [BdM].

Their construction is in the discrete-log setting in groups of unknown order (e.g., RSA group or class groups) and the size of both proofs of membership and non-membership is independent of the size of the set committed to. The security proof is in the generic group model under an "adaptive root" assumption. The main components of their construction is a hash function $H$ that maps strings to primes and a proof of exponentiation [W]. A long overview can be found in this blog-post. A shorter overview is given below.

Overview of the construction. Let's fix a group $G$ of prime order $p$ with a generator $g$. Loosely speaking, the value of the accumulator for a set $S$ is $$\pi:=g^{\Pi_{s\in S}H(s)}.$$ To prove membership of an element $s^*$ in $S$, the prover gives out the co-factor, i.e., the product of all elements in $S$ except $s^*$: $$\pi^*:=g^{\Pi_{s\in S\setminus\{s^*\}}H(s)}.$$ Given $\pi$ and $\pi^*$, the verifier simply checks whether $\pi=(\pi^*)^{H(s)}$.

Proving non-membership of an element $s^*$ in $S$ is trickier and requires an application of Bézout's identity that is due to Shamir [S]. Since $H$ maps elements to primes, with high probability $h^*=H(s^*)$ and $h=\Pi_{s\in S}H(s)$ will be co-prime and therefore there exists two numbers $a,b\in\mathbb{N}$ such that $ah^*+bh=1$. The proof now is $\pi^*:=(g^a,b)$ and the verifier checks whether $$(g^a)^{h^*}\cdot\pi^b=g.$$

$^1$ The ideas were probably known before, but I couldn't find an earlier reference.

[BBF]: Boneh, Bünz and Fisch, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Crypto 19

[BdM]: Benaloh and de Mare, One-way Accumulators: A Decentralized Alternative to Digital Signatures, Eurocrypt 93

[S]: Shamir, On the generation of cryptographically strong pseudorandom sequences., TOCS 83

[W]: Wesolowski, Efficient verifiable delay functions, Eurocrypt 19

| improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.