How to prove I know an x without revealing x or f(x)?

Question

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.

Answer 1

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.