0
$\begingroup$

I am aware that in the Pedersen commitment scheme, the relationship between g and h must be unknown in terms of discrete logarithms. Knowing the relationship would be insecure as it would break the hiding property. I used the following simple "attack" to try and understand:

  1. c = g^m * h*r
  2. The attacker knows g = h^x, so the commitment c is simplified to c = h^xm+r
  3. Knowing c and x, the attacker can start guessing values for m and r

However, randomly picking m and r and checking if they fit the commitment to find the right m seems to have a probability that is going to be very (negligibly) low. It is pretty much a brute-force attack but can't figure out why knowing the relationship between g and h must be unknown in terms of discrete logarithms if the danger is negligible.

This question doesn't go into detail on this topic Pedersen commitment so I wanted more detail on it.

$\endgroup$

1 Answer 1

4
$\begingroup$

Knowing the relationship would be insecure as it would break the hiding property

Here's the issue you're running into. It doesn't break the hiding property; even if the relationship between $g$ and $h$ was well-known, you still can't recover $x$ from $g^xh^r$ (assuming $r$ was chosen randomly and uniformly). For any potential committed value $x'$, there's a $r'$ that makes it work.

Instead, it breaks the binding property. If the committer knew the relationship, for example, the value $a$ s.t. $g = h^a$, then he could open the commitment any way he likes. For example, if he has published a commitment $C = g^xh^r$, he could open it as an arbitrary value $y$ by publishing $y$ and $r - a(y-x)$. The verifier would check the value of $g^y h^{r - a(y-x)} = g^yh^rg^{-(y-x)} = g^xh^r = C$, and so the opening would verify.

This property is what ensures us that opening the commitment in two different ways is hard. If the committer could open it in two different ways, that would allow him to deduce the discrete log of $h$ (to the base of $g$); we believe that problem is hard, and so the problem of opening a commitment in two different ways is also hard.

$\endgroup$
1
  • $\begingroup$ Thanks, it is much clearer now! $\endgroup$
    – clemdcz
    Jan 2 at 23:30

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.