Suppose a set of $u_1, u_2, ..., u_N$ users each knows an associated secret $x_1, x_2, ..., x_N$ they do not wish to reveal. We have a public $f(x)$ such as the discrete logarithm $f(x)=g^x\,\mathrm{mod}\,p$, which produces a set of publicly available values $v = \lbrace f(x_1), f(x_2), ..., f(x_N) \rbrace$ used for verification. Is there a way for any given $u_i$ to prove that they are in possession of $x_i$ such that $f(x_i) \in v$, without revealing which $f(x_i)$ (or $x_i$), as a means of providing anonymity? The usual ZKP requires that $x_i$ and $f(x_i)$ are publicly associated.


There is a technique called set membership proof. I am not an expert in this area, but it seems closely related. See the excerpts below:

Given a set $\Phi=\{\varphi_1,\ldots,\varphi_n\}$ and a commitment $C,$ a typical approach to the set membership problem is to use a zero-knowledge proof of the form:

“$C$ is a commitment to the element $\varphi_1$ OR $\ldots$ OR it is a commitment to $\varphi_n$.”

Even though there exist efficient algebraic $\Sigma$ (Sigma) protocols for handling a single such OR clause, such a proof still has length which is proportional to $n$. In many practical situations, the set $\Phi$ is often specified in advance by the verifying party. In other words, $\Phi$ can be considered a common input to both Prover and Verifier, and thus we might ask whether it is possible to prove a commitment is a commitment to an element of $\phi$ without having to explicitly list $\Phi$ in the proof.

The paper Camenisch et al with the above passage is available here, so start by looking at algebraic $\Sigma$ protocols if your $n$ is small, or to their techniques if it is large.

| improve this answer | |
  • 1
    $\begingroup$ I discovered this myself too. Thanks for the helpful pointers. $\endgroup$ – rino Jun 7 '18 at 12:49

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.