# Why is the Pedersen commitment computationally binding?

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?

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).
• Minor addition: The reason the sender can't compute $r'$ is because the $a$ value, such that $h = g^a \mod p$, is supposed to be discarded and forgotten once $h$ has been generated. If the sender is also the one who generated the system parameters, the sender might technically cheat and keep $a$. – Henrick Hellström Aug 13 '13 at 15:26
• @HenrickHellström: actually, according to the original Pedersen paper, $a$ was generated by the receiver (I suspect because if someone else generated it, the receiver couldn't be certain that whoever did it didn't collude with the sender) – poncho Aug 13 '13 at 16:53
• @HenrickHellström I got your point, I thought $a$ was a value known by the sender. Thanks! – LRM Aug 14 '13 at 8:19