Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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 unbounder 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.

share|improve this answer
    
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
    
Quite right, thanks. I hope you didn't miss my main point, though. –  Henrick Hellström Aug 13 '13 at 17:25
    
@HenrickHellström I got your point, I thought $a$ was a value known by the sender. Thanks! –  LRM Aug 14 '13 at 8:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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