2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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\}$? $\endgroup$
    – Maeher
    May 1, 2023 at 6:29
  • $\begingroup$ May I ask how the question arises? $\endgroup$
    – Daniel S
    May 1, 2023 at 7:59
  • $\begingroup$ @Maeher Yes, but I think I may have figured it out. $\endgroup$
    – GeorgeT
    May 1, 2023 at 8:25

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – GeorgeT
    May 6, 2023 at 19:40
  • $\begingroup$ 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. $\endgroup$
    – Maeher
    May 7, 2023 at 7:38

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.