Proving the range of a blinded value in a Pedersen commitment in zero knowledge

John N.

8/21/23, 1:33 PM

A prover has the following value: $$C = (h^ag^x)^b$$

and he needs to prove in zero knowledge to a verifier that $x < t$, for some public threshold $t$. The verifier knows $h$, $g$, $C$, and $t$. The prover knows everything. Essentially, it is the following relation:

$$\{(a,b,x)\ |\ C = (h^ag^x)^b \wedge x < t\}$$

I know this is possible for a value $s' = h^ag^x$ (using bulletproofs, for example), but I was wondering if it is also feasible given the extra blinding factor $b$. If so, could you explain how or point me to the relevant literature?

0 + 0

signature

zero-knowledge-proofs

commitments

homomorphic-signatures

knaccc

8/21/23, 2:02 PM

What's the motivation to blind the Pedersen Commitment twice? If your blinding factor $b$ is different between Pedersen Commitments, then they're no longer additively homomorphic

John N.

8/21/23, 2:15 PM

The blinding factor $b$ is actually the same across different commitments, but it's computed secretly via MPC. I need it to keep the commitments homomorphic and at the same time to prevent a user from tampering with the commitment of another user (e.g. with $C_i \cdot g^{x'}$. In my adversarial model some users are malicious).

knaccc

8/21/23, 2:30 PM

My first thoughts are that I don't think it's possible, because 1. The range proof could only work if $g^b$ is known by verifiers, and 2. Knowledge of $g^b$ allows the commitment tampering that you're trying to prevent. It's possible there is something more elaborate that could solve the problem. Why not just sign the commitments in order to prevent tampering?

knaccc

8/21/23, 2:46 PM

Another possibility is that verifiers take it on trust that a series of commitments to each of the powers of 2 (all blinded by $b$) have been genuinely declared. Those commitments could then be used in range proofs for any commitment blinded by $b$. All provers would need to know the blinding factor $x$ for each of those power-of-2 commitments.

John N.

8/21/23, 3:12 PM

I can sign each commitment but I also allow any user to add all the commitments together (by multiplying them). Since such user may be malicious, I cannot guarantee that the final commitment is also tamper-free, right?

knaccc

8/21/23, 3:15 PM

I don't fully understand your use case, so I'm not sure why, when a user adds commitments together, that they can't just declare which commitments were added together so that a verifier can check they were correctly added together

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proving the range of a blinded value in a Pedersen commitment in zero knowledge

TH: พิสูจน์ขอบเขตของมูลค่าที่มองไม่เห็นในความมุ่งมั่นของ Pedersen โดยไม่มีความรู้

RO: Demonstrarea intervalului unei valori orbite într-un angajament Pedersen în cunoștințe zero

RU: Доказательство диапазона ослепленного значения в обязательстве Педерсена при нулевом знании

VI: Chứng minh phạm vi của một giá trị mù quáng trong một cam kết của Pedersen với kiến thức bằng không

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.