Score:3

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

ie flag

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.

Score:2
es flag

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.

user77340 avatar
ie flag
oh, this is the idea of ring confidential transaction(RingCT)! Seems this is correct. Thanks!
user77340 avatar
ie flag
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?
knaccc avatar
es flag
@user77340 yes, exactly
user77340 avatar
ie flag
the answer is unaccepted.
user77340 avatar
ie flag
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$.
knaccc avatar
es flag
@user77340 The problem is that if there are two known messages, $m_a$ and $m_b$, which may occur in the set, then you could calculate $c=m_a/m_b$ and then check if there are any pairs of $D_i$ values where the ratio between them is $c$. Therefore you undo the hiding/blinding property of the Pedersen commitments
user77340 avatar
ie flag
I see. Can I say that this attack could only work if there is any message leaked? Or if we can assume the messages would not be leaked, then it is also OK to let $D_i=xm_iG$? Since $D_i=xm_iG$ is simpler, it is preferred.
knaccc avatar
es flag
@user77340 The reason that the Pedersen Commitment needs a blinding factor $r_i$ is to prevent someone from discovering the message by brute-forcing the commitment. Therefore it would not make sense to go to the trouble of having a Pedersen commitment which uses a blinding factor to prevent brute forcing, only to then re-introduce the ability to use brute force via the $D_i$ VPRF output.
user77340 avatar
ie flag
ok, I see, thanks!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.