0
$\begingroup$

An Elgamal-like bit commitment scheme:
Let $\langle g \rangle$ be a group of order $n$, where $n$ is a large prime.
Let $h\in_{R}\langle g \rangle\setminus\{1\}$ denotes a random group element such that $\log_{g} h$ is not know to any party, neither the sender nor the receiver.
$commit(u,x):=(g^{u},h^{u+x})$, where $u\in_{R}\mathbb{Z}_{n}$ and $x$ is the value we want to commit to it.

Elgamal-like bit commitment scheme is computationally hiding. The question is, "Is Elgamal-like bit commitment scheme computationally hiding under the discrete logarithm assumption, or decisional Diffie-Hellman (DDH) assumption?"

$\endgroup$
4
  • $\begingroup$ Where are you stuck in thinking about this? What information would be most helpful? $\endgroup$ Commented Jun 2, 2023 at 23:37
  • $\begingroup$ Are you sure you haven't swapped the role of $x$ and $u$? $\endgroup$
    – Mikero
    Commented Jun 3, 2023 at 16:11
  • $\begingroup$ @Mikero yes, I did. I edit it. $\endgroup$ Commented Jun 4, 2023 at 8:16
  • $\begingroup$ @MarcIlunga I think the scheme is computationally hiding based on discrete logarithm assumption, but I doubt. Maybe knowing discrete logarithm of $u$ be sufficient, but it's not necessary, i.e., it's computationally hiding based on decisional Diffie-Hellman (DDH) assumption. $\endgroup$ Commented Jun 4, 2023 at 8:23

2 Answers 2

1
$\begingroup$

Breaking DDH would allow verifying the opening of a commitment x without knowing u. If the space of possible x values is small (EG:{0,1}) then guess and check using DDH is sufficient.

Assume there is some algorithm for opening a commitment. It produces x from the commitment tuple. Given x we can compute H^u = H^(u+x)/H^x. H has a discrete log in base G so this is analogous to the DH assumption set with G^a=H, G^b=G^u and G^(a*b)=H^u=G^(a*u). An algorithm for opening a commitment must find G^(a*b) from G^a and G^b breaking CDH while verifying without u involves deciding if a given G^(a*b) value is correct requiring a solution to the DDH problem.

In the general case with the domain of x being large enough to make guess and check impractical hiding only breaks if the attacker can break DLOG. Either CDH or DLOG gets them H^u which allows finding H^x and then they need DLOG to recover x from that.

$\endgroup$
2
  • $\begingroup$ Your general case misses the point; if an attacker can compute the answer to "is this commitment a commitment to the value A", the commitment scheme is considered broken, just as much as a symmetric scheme would be if, an attacker given an encryption of A or encryption of B, could tell which it is. Practically speaking (as in the case that the committed value has large entropy), it could be safe - however we do have commitment schemes that are secure even if the value only has 1 bit of entropy, so there's little reason to use weaker schemes $\endgroup$
    – poncho
    Commented Jun 5, 2023 at 15:38
  • $\begingroup$ This answer is partially correct and mentions the connection between DDH assumption and the hiding property of this commitment scheme well. I've found a lecture notes that examines this question. $\endgroup$ Commented Jun 5, 2023 at 22:32
1
$\begingroup$

The decisional Diffie-Hellman (DDH) assumption is needed to prove hiding property of this ElGamal-like bit commitment scheme. This question was examined by this lecture notes [Lecture Notes Cryptographic Protocols, Version 1.8, February 4, 2023 Berry Schoenmakers]

enter image description here

Let $h\in_{R}\langle g \rangle\setminus\{1\}$ denotes a random group element such that $\log_{g} h$ is not known to any party, neither the sender nor the receiver.

Let say $h=g^r$ for some $r\in\mathbb{Z}_{n}$.
Now the reciever tries to obtain some information about $x$ from commit value $commit(u,x)=(g^{u},h^{u+x})$ where $u\in_{R}\mathbb{Z}_{n}$ and $x\in\{0,1\}$.
If $x=0$, $commit(u,x)=(g^{u},h^{u})$ that in DDH tuple form we can write $(h=g^{r},g^{u},h^{u}=g^{ru})$.
If $x=1$, $commit(u,x)=(g^{u},h^{u+1})$ that in tuple form we can write $(h=g^{r},g^{u},h^{u+1}=g^{ru}g^{r})$. Since nobody knows discrete logarithm of $h=g^{r}$, we can look at $h^{u+1}=g^{ru}g^{r}=g^{ru}h$ as a random element $g^{z}\in\langle g \rangle$ too.
So the receiver ends up to distinguish $(h=g^{r},g^{u},h^{u}=g^{ru})$ from $(h=g^{r},g^{u},h^{u+1}=g^{z})$, i.e., the decidsional Diffie-Helman (DDH) problem.

$\endgroup$
6
  • 1
    $\begingroup$ DDH and CDH are strictly stronger assumptions than DL in the sense that if the DL assumption breaks then CDH and DDH also fail. The CDH assumption contains DL since an attacker that can find discrete logs can calculate G^(a*b) by finding a and b, The DDH assumption contains CDH since an attacker can verify G^(a*b) by recomputing the value with their CDH oracle. $\endgroup$ Commented Jun 6, 2023 at 10:19
  • $\begingroup$ @RichardThiessen so it means that this scheme is computationally hiding based on DDH assumption? $\endgroup$ Commented Jun 6, 2023 at 17:38
  • $\begingroup$ Yes, you're exactly right. $\endgroup$ Commented Jun 6, 2023 at 22:13
  • $\begingroup$ @RichardThiessen I've edited the answer. Is it correct? Specially, the part that tries to connect the attack to DDH assumption. $\endgroup$ Commented Jun 7, 2023 at 9:13
  • $\begingroup$ Yup, that's correct. $\endgroup$ Commented Jun 7, 2023 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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