Why is the Pedersen commitment computationally binding?

Question

This is how the Pedersen commitment seems to work:

Let $p$ and $q$ be large primes such that $q \mid (p-1)$, let $g$ be a generator of the order-$q$ subgroup of $Z_p^{\star}$. Let $a$ be a random secret from $Z_q$, and $h=g^a \bmod p$.

The values $p$, $q$, $g$ and $h$ are public, while $a$ is secret.

To commit to a message $m \in Z_q$, the sender chooses a random $r \in Z_q$ and sends the commitment $c=g^mh^r \bmod p$ to the receiver; while in order to open the commitment, the sender reveals $m$ and $r$, and the receiver verifies that $c=g^mh^r \bmod p$.

Moreover, the Pedersen commitment scheme is known to be:

• information theoretically hiding: given a commitment $c$, every value $m$ is equally likely to be the value committed in $c$. For example, given $m$, $r$, and any $m^{\prime}$, there exists $r^{\prime}$ such that $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$. In fact, we have that $r^{\prime} = \frac{m-m^{\prime}}{a} + r$.

• computationally binding: if the sender can find different $m$ and $m^{\prime}$ both of which open the commitment $c$, so $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$, then he can solve the discrete logarithm $\log_g(h)=\frac{m^{\prime}-m}{r-r^{\prime}}$. If we assume the discrete logarithm is hard, the sender cannot open the commitment with another value.

My question concerns the computationally binding property:

We know, from the information theoretically hiding bullet point, that given $m$, $r$, and any $m^{\prime}$, the sender is able to compute an $r^{\prime}$ such that $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$. But doesn't this mean that he's been able to open the commitment with a different message $m^{\prime}$ without even having to compute a discrete logarithm?

Answer 1

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..."

Actually, that's not true, and the "information theoretically hiding" bullet point does not state that. What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value. In fact, the "computationally binding" bullet point specifically states that a real sender cannot (assuming he is unable to solve Discrete Log problems).

Instead of talking about the senders capabilities, the information theoretically hiding bullet point talks about the receiver; that is, even if the receiver had infinite computing power, he still cannot get any information from the commitment as to what is committed to (because all possible values are equally likely). Now, the Pedersen commitment scheme is asymmetric in this (because a computationally unbounded sender can change commitments); on the other hand, it turns out that a commitment scheme between two computationally unbounded parties is actually impossible; the Pedersen scheme is as close as we can come.