Is a Pedersen commitment still secure when r is either 0 or 1?

GeorgeT

5/1/24, 2:36 AM

Specifically if we know the $r$ takes values from the set $\{0,1\}$and $c=g^r*h^m$ does the hiding property still hold? I think I already managed to prove that the binding property holds due to the difficulty of the Dlog problem and my intuition says that the hiding property is compromised. But I can't seem to figure out a successful probabilistic hiding attack method that runs in polynomial time.

1 + 3

provable-security

commitments

Maeher

5/1/24, 6:29 AM

Just to be clear, you're asking if the commitment is still hiding/binding if instead of sampling $r$ uniformly from $\mathbb{Z}_q$ (with $q$ being the group order) you sample it uniformly from $\{0,1\}$?

Daniel S

5/1/24, 7:59 AM

May I ask how the question arises?

GeorgeT

5/1/24, 8:25 AM

@Maeher Yes, but I think I may have figured it out.

Score:3

Crypto

Maeher

5/1/24, 6:16 PM

No, it's not hiding.

Each message now only has two possible commitments, $h^m$ and $g\cdot h^m$. And conversely, each commitment $c$ can only be explained as a commitment of two possible messages, either $\log_h c$ and $\log_h (cg^{-1})$.

You can trivially break hiding by recomputing the two possible commitments for a message in question and checking if one of them is the commitment you're looking at. In the standard definition of hiding you can explicitly choose two messages that have no common commitment, thus breaking binding with probability $1$.

+ 2

GeorgeT

5/6/24, 7:40 PM

Yes, that's the same thing I concluded after an hour of more thought. I constructed an adversary that chooses the messages 0 and 1 and can differentiate between them with a probability negligibly smaller than 1 (for the rare case that there's overlap between the committed values). I guess your approach to choose messages guaranteeing a probability of 1 is even better. I'm still not sure how this gives information about m if the adversary didn't choose the messages, but it definitely breaks the classic definition of hiding.

Maeher

5/7/24, 7:38 AM

Well, there's a reason hiding is defined the way it is. It guarantees that the message remains hidden independent of the distribution of messages. In practice it's uncommon that the attached would be straight up able to *choose* the messages. But they might well be able to influence the distribution. Or the distribution might be low entropy from the get go. *If* the message is chosen uniformly from $\mathbb{Z}_q$, the hardness of dlog would prevent you from reconstructing the full message. But even in that case the commitment could leak some information *about* the message.

Elon Musk

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

EN: Is a Pedersen commitment still secure when r is either 0 or 1?

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.