2
$\begingroup$

I am a bit stuck on the following claim:

The ElGamal commitment scheme is information theoretically binding

As far as I understand, an adversary $A$ would win the binding game if it is able to find an $x\prime\neq x$ such that $C(x)=C(x\prime)$.

$C(x)=C(x\prime)$ implies:

$$ (g^r,h^rx)=(g^{r\prime},h^{r\prime}x\prime)$$

How is this impossible to be found? Since generators are cyclic, it should be possible to find an $r\neq r\prime$ that with $g^r=g^{r\prime}$, or am I overseeing something?

$\endgroup$
2
$\begingroup$

How is this impossible to be found? Since generators are cyclic, it should be possible to find an $r\neq r'$ that with $g^r = g^{r'}$, or am I overseeing something?

Yes, you're probably thinking the wrong way, possibly like this: there are values $a,b$ with $a\neq b$ and $a^2 = b^2$. But if you look closely, in this case the base is the same and the exponent differs.

The main arguement here is: If the group order is $t$, and we have $r \neq r' \mod t$, then $g^{r} \neq g^{r'}$. Alternatively: set $x = r' - r \mod t$, which is non-zero modulo $t$. Then $g^{r'} = g^{r + x} = g^r \cdot g^x$. This can't be equal to $g^r$ if $x$ is not zero or a multiple of the group order.

With a fixed generator, the first element in the tuple fixes $r$ - even if you don't know what $r$ actually is. And that in return fixes $h^r$. And for a given ElGamal ciphertext this fixes $m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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