# How to do a non-membership proof for a committed value?

Assume that the verifier is given three commitments $$C_i=g^{m_i}h^{r_i}, i=1,2,3$$. Now a prover knowing $$m_i, r_i, i=1,2,3$$ wants to prove $$m_3\neq m_1\wedge m_3\neq m_2$$. Specifically, the relation is follows: $$\{(m_i,r_i), i=1,2,3|C_i=g^{m_i}h^{r_i}\wedge m_3\neq m_1\wedge m_3\neq m_2)\}$$. A general relation can be written as follows: $$\{(m_i,r_i), i=1,2,..,n|C_i=g^{m_i}h^{r_i}, i=1,2,...,n\wedge m_n\notin\{m_1,m_2,...,m_{n-1}\})\}$$. Is there a proof system that can prove such the general relation? A trivial solution may be just doing $$n-1$$ times inequality proofs. Is there any simpler approach? Any reference papers? Thanks.

If you only care about blinding the commitment (to prevent brute-forcing), and do not need additively homomorphic commitments, you can do the following:

The prover has a key pair $$(x, X=xG)$$, and publishes the public key $$X$$.

For each member of the set, the prover publishes:

1. $$C_i=H_p(m_i) + r_iG$$, where $$H_p(m_i)$$ means to hash $$m_i$$ and interpret the result as a valid EC point.

2. $$D_i=xH_p(m_i)$$

3. $$E_i=xC_i$$

4. A DLEQ proof that $$X$$ and $$E_i$$ share the same private key $$x$$ on the points $$G$$ and $$C_i$$

5. A signature for the public key $$(E_i-D_i)$$ on the generator $$G$$.

Note that $$E_i-D_i==xH_p(m_i)+xr_iG-xH_p(m_i)==xr_iG$$.

The DLEQ proof (item 4) will prove that $$E_i$$ was calculated properly. What we're doing here is using a verifiable pseudo-random function (VPRF) that only the prover can query but that any observer can verify.

The signature (item 5) will only be possible if $$D_i$$ has also been calculated properly, since the signature will only be possible on the generator $$G$$ if there is no $$H_p()$$ component left over (because the EC discrete log w.r.t. $$G$$ is not knowable for any output of $$H_p()$$).

The end result is that we've created a VPRF output $$D_i$$ for each message $$m_i$$, and proven that each VPRF output has been declared correctly.

Now it will be immediately obvious if there are any commitments to the same message, since they will share the same $$D_i$$ values.

• oh, this is the idea of ring confidential transaction(RingCT)! Seems this is correct. Thanks! Commented Apr 4, 2022 at 22:50
• May I ask a question? For the signature in step 5, do you mean proving knowledge of the discrete log of Ei-Di on the generator H? Commented Apr 5, 2022 at 8:00
• @user77340 yes, exactly Commented Apr 5, 2022 at 9:12
• the answer is unaccepted. Commented Apr 5, 2022 at 14:20
• what is the problem if we just use $D_i=xm_iG$? Any attack? I don't see there is a problem proving the Pedersen Commitment is to the same $m_i$ as $D_i$. Commented Apr 6, 2022 at 1:05