Score:0

Crypto

Hiding property of Elgamal-like bit commitment

user1035648

6/2/24, 11:16 PM

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?"

2 + 4

elgamal-encryption

discrete-logarithm

commitments

Marc Ilunga

6/2/24, 11:37 PM

Where are you stuck in thinking about this? What information would be most helpful?

Mikero

6/3/24, 4:11 PM

Are you sure you haven't swapped the role of $x$ and $u$?

user1035648

6/4/24, 8:16 AM

@Mikero yes, I did. I edit it.

user1035648

6/4/24, 8:23 AM

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

Score:1

Crypto

Richard Thiessen

6/4/24, 11:00 AM

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.

+ 2

poncho

6/5/24, 3:38 PM

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

user1035648

6/5/24, 10:32 PM

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.

Score:1

Crypto

user1035648

6/5/24, 10:40 PM

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]

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.

+ 5

Richard Thiessen

6/6/24, 10:19 AM

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.

user1035648

6/6/24, 5:38 PM

@RichardThiessen so it means that this scheme is computationally hiding based on DDH assumption?

Richard Thiessen

6/6/24, 10:13 PM

Yes, you're exactly right.

user1035648

6/7/24, 9:13 AM

@RichardThiessen I've edited the answer. Is it correct? Specially, the part that tries to connect the attack to DDH assumption.

Richard Thiessen

6/7/24, 10:59 AM

Yup, that's correct.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Hiding property of Elgamal-like bit commitment

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.