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 ?

  • $\begingroup$ 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. $\endgroup$
    – tylo
    Dec 7 '16 at 11:49
  • $\begingroup$ 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 ? $\endgroup$
    – SpiderRico
    Dec 7 '16 at 12:37
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Dec 7 '16 at 12:58
  • $\begingroup$ 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 ? $\endgroup$
    – SpiderRico
    Dec 7 '16 at 13:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – tylo
    Dec 7 '16 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.