Can I prove set membership and uniqueness without revealing the element?

Assuming a publicly known set $\Psi$ with $N$ unique elements.

I have a set $\Sigma=\{\sigma_1,\sigma_2,...,\sigma_m\}$ where $m\leqslant N$. I would like to publicly prove that all the elements in $\Sigma$ are unique and are also elements of $\Psi$. I would like to do this without actually revealing the elements of $\Sigma$.

I happened upon this paper. If I understand it correctly, the above should be possible by publicizing commitments for every $\sigma$. However most of the paper is way over my head and I'm not really sure what commitment scheme I should use, what extra information should be made public and how exactly would a third party Verifier go about verifying the claim.

-

You can use the techniques in the paper you have linked to show that a list of commitments $C_1,\ldots,C_m$ to the elements in $\Sigma$ are elements in $\Psi$ (the commitment scheme of choice are information-theoretically hiding Pedersen commitments, which are also used in the linked paper) . Basically, this works by the "owner" of the set $\Psi$ publishing a Boneh-Boyen signature for each element in $\Psi$ and the prover commits to an element in $\Psi$ (using a Pedersen commitment) and proves in zero-knowledge that the in the commitment is indeed one for which there is a valid signature (this can be nicely done in $O(1)$). So, you can run this proof for every $C_i$ and thus this is a straighforward application of the results from the paper, where you simply make $m$ proofs of that kind.

So far no problem, the proof complexity for $\Sigma$ is $O(m)$.

The problem, however, lies within proving uniqueness. You would need to additionally prove that the values committed in $C_1,\ldots, C_m$ are mutually different, because the above proof would also work if all commitments $C_i$ are commitments to the same value in $\Psi$.

There are techniques to prove non-monotone relations about discrete logs, e.g., here, Section 5.2 or here, which allows to prove inequality of two discrete logarithms without revealing their values. I'm not sure if they are applicable to Pedersen commitments as well, but the most important issue is that they add an additional cost of $O(m^2)$ to your proof, as you have to prove the non-equality for $m(m-1)/2$ pairs of commitments. Maybe, there are however more efficient techniques which did not come to my mind.

-

Proving uniqueness

You can prove that the elements are unique in $O(m)$ time and space by pre-sorting them and then giving a zero-knowledge proof that they are in sorted order. Details follow.

Assume the elements of $\Sigma$ are integers in the range $[0,K-1]$, where $K$ is a constant chosen in advance and made public. Pick a large prime $p$ and a group element $g \in (\mathbb{Z}/p\mathbb{Z})^*$ of prime order $q$, such that $q > 2K$. The scheme is:

First, sort the elements of $\Sigma$, so $\sigma_1 < \sigma_2 < \cdots < \sigma_m$. Next, commit to all the elements, using a discrete log based commitment scheme with generator $g$; for instance, you might use Pedersen commitments. Finally, prove that the elements are in sorted value, i.e., that $\sigma_i < \sigma_{i+1}$ holds for all $i$.

You can prove they are in sorted order using a range proof for discrete logs: for all $i$, you show that $\sigma_i \in [0,K-1]$, and you show that $\sigma_{i+1} - \sigma_i \in [1,K-1]$ (again, considering the $\sigma_i$'s as integers). To prove that $\sigma_{i+1} - \sigma_i \in [1,K-1]$, it suffices to prove that $d_i = \sigma_{i+1} - \sigma_i \bmod q$ is in the range $[1,K-1]$: since you've proven that each $\sigma_i$ is in $[0,K-1]$, and since $q \ge 2K$, there can be no wrap-around modulo $q$. All that remains is how to describe that each $d_i$ is in the specified range.

One standard way to do a range proof is to express each $d_i$ in binary, i.e.,

$$d_i = \sum_j b_{i,j} 2^j.$$

Then you commit to all the $b_{i,j}$'s, use the homomorphic property of commitments to show that the $b_{i,j}$'s are consistent with the $d_i$'s (i.e., that the equation above holds), and show that $b_{i,j} \in \{0,1\}$ for each $i,j$. Of course, you can prove that the $d_i$'s were computed correctly by using the homomorphic property of discrete log-based commitment schemes: given the commitments $C(\sigma_{i+1})$ and $C(\sigma_i)$, anyone can compute a commitment $C(d_i)=C(\sigma_{i+1}-\sigma_i \bmod q)$ to $d_i$, even without knowing $\sigma_i,\sigma_{i+1}$.

When using this method of range proofs together with the idea above, it will give you a valid proof that the elements $\sigma_1,\dots,\sigma_m$ are mutually disjoint.

Proving it is a subset

You can show that $\Sigma \subseteq \Psi$ using the techniques in the paper you mentioned.

-
Neat idea ;) if the set is known you need to use Pedersen commitments. Otherwise, i.e. DL commitments, it is easy to figure out to what you have commited to. You leak all info then. –  DrLecter Apr 25 at 20:47
@DrLecter, I think you have a confusion/misconception about DL commitments. I'm not sure what specifically you have in mind when you mention "DL commitments", but any commitment scheme (whether information-theoretically hiding or computationally hiding) will conceal what was committed to -- nothing is leaked. It doesn't matter whether the value being committed to is low entropy or not; secure commitment schemes promise not to leak what was committed, even if the value has low entropy. If it's not hiding, it's not a secure commitment scheme. For instance, $C(x)=g^x$ isn't secure. –  D.W. Apr 25 at 21:02
@D.W.I dont think so. If you use a DL commitment to $a$ with generator $g$ it will be $g^a$. So yes, if you have a high entropy secret it works. But if $a$ comes from a known (poly bounded) set you are doomed. Yeah, your edit is true. But what do you then mean by a DL commitment which I see as a perfectly binding commitment (cause as you know in the classical model either the one OR the other property is perfect) ? :) –  DrLecter Apr 25 at 21:12
...with OR being exclusive ( and we are working in the classical - DL - and not noisy channel). –  DrLecter Apr 25 at 23:32
@DrLecter, yeah, you definitely have a misconception about commitment schemes. $g^a$ is not a secure commitment to $a$. It is not hiding (neither computationally hiding nor information-theoretically hiding). As a result, it is not classified as a secure commitment scheme. A secure commitment scheme must be both binding and hiding. Therefore, what you are talking about is not a DL commitment -- it's not a commitment at all; it's just a broken thing that doesn't work. Of course, when I mention using a commitment scheme, I assume you use a secure commitment scheme, not something broken. –  D.W. Apr 26 at 5:23