1
$\begingroup$

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$?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for your replay!But I only know that the Schnorr signature can prove to the verifier that the prover knows the private key corresponding to the public key. But I don't know how to prove that one of the two private keys is known based on two public keys, without revealing which. $\endgroup$
    – user105684
    Jul 28, 2023 at 8:01
  • $\begingroup$ @user105684 a ring signature proves it. My preferred implementation is this: Section 3.3 - Spontaneous Anonymous Group (SAG) signatures" $\endgroup$
    – knaccc
    Jul 28, 2023 at 9:35
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks for your replay! but i don’t know what is the symbols rΔa and rΔb. and when i verify VΔa + Sσ = s1⋅G + c⋅Va ,i can't garantee the correctness. $\endgroup$
    – user105684
    Jul 28, 2023 at 7:31
  • $\begingroup$ Please could you add in an explanation as to why this method works? Also, I tried writing out the algebra, and unless I've made a mistake, I'm not sure why it would ever verify. $\endgroup$
    – knaccc
    Jul 28, 2023 at 10:13
  • $\begingroup$ rΔa and rΔb are random blinding factors used for the commitments VΔa and VΔb, respectively. These blinding factors are used to hide the values (a - σ) and (b - σ) in the commitments, making the scheme zero-knowledge. For example lets say the verifier would check the responses from the prover for multiple challenges (c1, c2, ..., cn) and corresponding commitments (VΔa1, VΔa2, ..., VΔan), (VΔb1, VΔb2, ..., VΔbn), and (Sσ1, Sσ2, ..., Sσn).. prover should provide valid responses for each challenge, and the verifier must check all verification equations for each challenge-response pair. $\endgroup$ Jul 28, 2023 at 12:16
  • 2
    $\begingroup$ Thankyou!!! but when i try your Verification algorithm( VΔa + Sσ = s1⋅G + c⋅Va ). I get G⋅a+H⋅rΔa in the left and G(rΔa+c⋅ra+a⋅c)+ H⋅ra⋅c in the right. This obviously cannot gerantee the correctness. Did I make a mistake? $\endgroup$
    – user105684
    Jul 28, 2023 at 14:49
  • $\begingroup$ You may replace the equation verification with these two equation : VΔa + Sσ = s1⋅G + c⋅Va + (a - σ)⋅G Similarly, for the second equation: VΔb + Sσ = s2⋅G + c⋅Vb + (b - σ)⋅G With these equations, the verifier can ensure the validity of the DZKP proof. $\endgroup$ Jul 29, 2023 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.