How to prove that a Pedersen commitment has the same value as at least one of a set of other Pedersen commitments, without revealing which

Question

A prover has two pedersen commitments, $V_{a}=G\cdot a+H\cdot r_a$ and $V_{b}=G\cdot b+H\cdot r_b$, which commit the values $a$ and $b$ respectively.

The prover has another commitment $S_{\sigma}=G\cdot \sigma$ (which has no $H$ component). The verifier is provided with $V_a, V_b$ and $S_\sigma$. How can the prover prove that $\sigma \in \{a, b\}$ without revealing $a,b$ and $\sigma$?

Answer 1

Both prover and verifier independently calculate $P_a = V_a\ - S_{\sigma}$ and $P_b = V_b\ - S_{\sigma}$.

If $a\overset{?}{=} \sigma$, then $P_a=r_a\cdot H$.

If not, then $P_a=(a-\sigma) \cdot G + r_a\cdot H$.

Notice that in the first case, $P_a$ is a multiple of $H$, where that multiple $r_a$ will be known to the prover.

In the second case, $P_a$ is still a multiple of $H$, because all group elements are multiples of other group elements. However, that multiple is unknowable, because $G$ and $H$ are chosen such that the discrete log of $G$ w.r.t. $H$ is not known.

The same applies to $P_b$.

Therefore, proving that $\sigma \in \{a, b\}$ is the same as treating both $P_a$ and $P_b$ as public keys on the base point $H$, and demonstrating that at least one of the private keys is known.

The proof will be any kind of anonymous group signature (such as a Schnorr-based ring signature) which demonstrates that one of the two private keys is known, without revealing which.

Note that this approach can be used even if $S_{\sigma}$ is a full Pedersen commitment with an $H$ component.

Answer 2

To prove that σ belongs to the set {a, b} without revealing the values of a, b, and σ, the prover can use the technique of zero-knowledge proofs. In this case, a proof based on the Disjunctive Zero-Knowledge Proof (DZKP) protocol [the protocol can be found here] 1 can be used.

Here's a step-by-step show you on how the prover can prove that σ∈{a, b}:

1. Setup:

• The prover and verifier agree on the generator points G and H, which are known to both parties.
• The prover commits to values a and b using Pedersen commitments: Va = G⋅a + H⋅ra and Vb = G⋅b + H⋅rb.
• The prover also has another commitment Sσ = G⋅σ (with no H component).

2. Commitment Phase: The prover sends the commitments Va, Vb, and Sσ to the verifier.

3. Challenge Phase: The verifier selects a random challenge value c and sends it to the prover.

4. Response Phase: Now, the prover needs to provide responses to the verifier's challenge c. To do this, the prover calculates the Pedersen commitments for the differences Δa = a - σ and Δb = b - σ as follows:

• Δa commitment: VΔa = G⋅(a - σ) + H⋅rΔa
• Δb commitment: VΔb = G⋅(b - σ) + H⋅rΔb

Next, the prover computes two scalar values, s1 and s2, as responses to the challenge:

• s1 = rΔa + c⋅ra
• s2 = rΔb + c⋅rb

5. Final Step: The prover sends the responses s1 and s2 to the verifier.

6. Verification: The verifier checks if the following conditions hold:

• VΔa + Sσ = s1⋅G + c⋅Va + (a - σ)⋅G (equality involving points)
• VΔb + Sσ = s2⋅G + c⋅Vb + (b - σ)⋅G (equality involving points)

If both equations are satisfied, the verifier can be confident that σ∈{a, b}. The prover has proven that they know the values a and b, such that σ is either equal to a or b, without revealing the actual values of a, b, or σ.

The zero-knowledge property of this proof ensures that the verifier learns nothing about a, b, or σ, except for the fact that σ belongs to the set {a, b}. This way, the prover can keep their values private while still convincing the verifier of the validity of their claim.