2
$\begingroup$

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 ?

Improve this question
$\endgroup$
5
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 14:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.