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.

Does any of you know what is the difference between the Pedersen commitment and the commitment that uses the ElGamal encryption scheme?

For the sake of completeness, I recall what both of them look like.

Given two public and large primes $p$ and $q$ such that $q∣(p−1)$, and a (also public) generator $g$ of the order-$q$ subgroup of $\mathbb{Z}^{⋆}_p$, and given two random (secret) values $a,r \in Z_q$, we have that in order to commit to a message $m \in \mathbb{Z}_q$, we just have to compute the commitment $c=g^m h^r \pmod{p}$, where $h=g^a \pmod{p}$. Then, to open the commitment, we need the values $m$ and $r$ to be revealed, so that the commitment receiver can verify the commitment.

In the ElGamal encryption (for example, in the exponential version, which looks more like the Pedersen commitment) we also have a generator $g$ of a multiplicative group $G$ of order $q$, a private $x \in \mathbb{Z}_q$, and a public $h=g^x$. In order to encrypt a message $m$, we take a random $r \in \mathbb{Z}_q$ and compute $(g^r, g^m h^r)$. To me, the second part of the tuple looks very much like the Pedersen commitment.

The fact that any encryption scheme can be used as a commitment scheme is well-known. However, I often see the Pedersen commitment mentioned as something completely different to the commitment that uses an ElGamal encryption, and I was wondering whether here is any difference between the two, or they are actually the same.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

The main difference is that Pedersen commitments are unconditionally hiding, as given $g^mh^r$ represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out $m$.

In exponential ElGamal encryption, since you publish $(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but only computational hiding. Note that an unbounded adversary can simply try all possible $r\in Z_q$ till it matches $g^r$ and then with this knowledge try all possible $m\in Z_q$ till it matches $g^mh^r$.

Now, if you would only publish the second component in ElGamal, i.e., $g^mh^r$, as commitment and discard the first, this actually is a Pedersen commitment (as the setting you use is identical - i.e., working in a prime order $q$ subgroup or $Z_p^*$). The problem is, that when using this modified type of ElGamal encryption and the person computing the commitment knows the secret key $x$ with $h=g^x$, the ciphertext component $g^mh^r$ is no longer a binding commitment. Observe that you then can choose an arbitrary $m'\in Z_q$ and solve the equation

$m+xr\equiv m'+xr' \pmod q$

for the only unknown $r'\in Z_q$, which implies that

$g^mh^r = g^{m'}h^{r'} \mod p$

holds and thus, the commitment to $(m,r)$ can be opened to other arbitrary values $(m',r')$ (thus not binding at all).

Note that in fact it is essential for Pedersen commitment that the parameters $g$ and $h$ need to be computed by a trusted third party such that the discrete log $a$ between $g$ and $h$ is unknown. Otherwise you would have the same problem as with this "take the second ciphertext component of ElGamal encryption" as commitment. If you want to have such a property you obtain a trapdoor commitment with trapdoor $a$ (which allows you to arbitrarily open the commitment if you know the trapdoor $a$ as discussed above).

Edit:

As Ricky Demer mentioned in his comments I assumed that the commitment is non-interactive. If the receiver chooses the parameters for the commitment scheme and sends them to the sender, then unconditional hiding is given (it must only be ensured that the sender does not know the dlog between $g$ and $h$).

As tylo mentioned in the comments it is also interesting to look at the binding properties of both approaches.

Pedersen commitments are computational binding under the dlog assumptions as seen above.

The exponential ElGamal version - publishing $(g^r,g^mh^r)$ - is, however, unconditionally binding as the first component $g^r$ uniquely determines $r$. Thus, this means that also $m$ in $g^mh^r$ is uniquely determined.

share|improve this answer
    
Pedersen commitment only needs a trusted third party if it needs to be equivocable and/or non-interacitve. (Although, in either of those cases, it will be both equivocable and non-interacitve.) $\hspace{1.65 in}$ –  Ricky Demer Nov 24 '13 at 21:45
    
@RickyDemer By non-interactive vs. interactive you mean with or without common reference string? But maybe that is out of scope of this question? By "computed by a trusted third party" I simply wanted to point out that the dlog should be unknown to the sender (for a non-trapdoor/non-equivocable commitment), but clearly, instead of requiring a TTP, sender and receiver clould also jointly compute the parameters such that they can be sure that dlog between $g$ and $h$ is unknown. –  DrLecter Nov 25 '13 at 8:55
1  
No, by non-interactive vs. interactive I mean the receiver doesn't vs. does send anything/something $\hspace{.22 in}$ to the committer. $\:$ If it doesn't need to be equivocable, then the receiver could just choose the parameters on its own and let the sender verify the conditions that imply the unconditional hiding property. $\;\;\;$ –  Ricky Demer Nov 25 '13 at 9:00
1  
The first part of the ElGamal commitment fixates the message, and thus it is unconditionally binding and computationally hiding; the hiding property still holds even if $\log_{g} h$ is known (assuming dlog is hard) –  tylo Nov 25 '13 at 10:44
    
@RickyDemer ok, yes that's true! @ tylo you are totally correct! I focused on hiding in the answer and did not focus on binding at all (will make an edit). thx for that! –  DrLecter Nov 25 '13 at 10:54

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.