# Why is one scheme “hiding” while the other one is OK?

I'm presented with these 2 following commitment schemes $Commit(x;r) = (c,k)$.

1. This is presented as bad (not hiding)

$Commit(x;r) = (H(x), x)$

So, not hiding means that attacker can deduce $x$ from $H(x)$ in that case. I don't see how this is possible except for an exhaustive search of $H$ ? If this is why the scheme is bad, then can't we do the same for any kind of commitment ? Or is it because $k = x$ ? Since $k$ should arrive to receiver only after he sends his value, I don't see how this is a problem.

2. This is presented as ok

$Commit(x;r) = (H(r||x), (x, r))$ where $||$ denotes the concatenation of strings.

It seems to me that by the same logic we can find $x||r$ and deduce something about x.

So, what exactly is the difference between these 2 schemes and why is one not hiding while the other one is ok ?

• Imagine you just have commitments to yes and no. Would that still be hiding? In the second case you would want to specify the choice of $r$ to some dregree, e.g. a random string with $x$ bit.
– tylo
Dec 7, 2016 at 11:49
• Thanks for your input. Your first sentence isn't very clear to me though. As far as I can understand, if the commitment is just yes or no we can deduce that $x$ is in form of a question. Is that what you mean ? Dec 7, 2016 at 12:37
• No, then the first scheme isn't hiding, if the message space is small: The attacker can just hash both messages and he can figure out which one it was.
– tylo
Dec 7, 2016 at 12:58
• Ah I see. Then my first approach is correct then, right ? Attacker still has to do an exhaustive search on the set of inputs. Then we're talking about computationally hiding. Basically, it is much harder to find a collision on the 2nd one as we use a salt. Is that correct ? Dec 7, 2016 at 13:01
• Well, "computationally hiding" usually refers to some computationally hard problem - not to exhaustive search. Relating this to the message space is usually a bad idea, unless you have a statement about the distribution of the message space. So no, basically you have no hiding property at all for the first one. For the second one, in that form I wouldn't call that hiding either in its current form - not without saying how $r$ is chosen.
– tylo
Dec 7, 2016 at 14:55