16
$\begingroup$

Let's say Alice and Bob are playing a game where Bob is trying to guess a number Alice has chosen.

Alice chooses a key $K$ and a number $N$ at random and performs $C=Commit(K, N)$ where $Commit(K, N)=h(h(K) \| h(N))$.
$h()$ is a collision-resistant hash function and $K$ and $N$ can be of any length.

Bob guesses $N'$ and sends it to Alice who responds with $K$ and $N$.

Bob can now do $C'=Decommit(K, N)$ which in our case is the same as Commit and verify that $C=C'$.

As I understand it the scheme above is perfectly hiding and computationaly binding. Is there a way to make the scheme both perfectly binding and perfectly hiding, or is there another scheme that has these properties?

I'm new to cryptography so I apologize in advance if I don't get some of the concepts right.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It is, heuristically, highly likely that your $Commit$ is not perfectly hiding. $\:$ In fact, it's not necessarily $\hspace{.5 in}$ even computationally hiding ($h$ might be such that the last bit of $h$'s output is always equal to the last $\hspace{.4 in}$ bit of $h$'s input). $\:$ However, your scheme is computationally binding. $\;\;$ $\endgroup$
    – user991
    Commented Mar 22, 2013 at 8:48
  • 1
    $\begingroup$ It is easy to show that (in the plain model) any perfectly binding commitment scheme is not even $\hspace{.8 in}$ statistically hiding (an unbounded receiver can brute force $K$ and $N$ to find $N\hspace{.02 in}$). $\:$ It is a folk $\hspace{.75 in}$ theorem that bit commitment (in the plain model) cannot even be both statistically hiding and $\hspace{.8 in}$ statistically binding, although I have never seen any proof of that. $\;\;$ $\endgroup$
    – user991
    Commented Mar 22, 2013 at 8:52
  • $\begingroup$ @RickyDemer That's a bummer. The protocol occurred to me during a lecture on bit commitment but I never got the chance to ask the professor. Thanks $\endgroup$
    – rath
    Commented Mar 22, 2013 at 8:57

1 Answer 1

Reset to default
8
$\begingroup$

As you noticed correctly, a hash function is kind-of computationally binding if you assume collision resistance. However, it is impossible to achieve perfect hiding property for hash functions, due to the potential loss of information.

Perfect hiding means, that a computationally unbound Alice COULD decomit any value: I.e. Pedersen commitments $c = g^xh^r$ can be decommited to any value, if you know the discrete logarithm $log_g h$.

In your hash function you have no guarantee for this: for a fixed pair of commitment and K there might not be $h(N)$ to fulfill the computation. Even replacing $h(N)$ with just $N$ does not imply this property.

In general, a scheme can not be both perfectly hiding and perfectly binding, because they are opposing principles: If Alice was computationally unbound, hiding means she can decomit ANY value, and binding means she could still decomit ONLY the original value.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Um, no. $\:$ Perfect hiding means, that if Alice was honest and Bob was computationally unbounded $\hspace{.6 in}$ then Bob's view is independent of Alice's value. $\;\;$ $\endgroup$
    – user991
    Commented Mar 22, 2013 at 17:08
  • 1
    $\begingroup$ Uhm, yes... that's the same coin from the other side. Decomitment to ANY value is possible. If Alice is comp. unbound, she can decomit anything. If Bob is unbound, he still can not figure out Alice input. $\endgroup$
    – tylo
    Commented Mar 22, 2013 at 17:13
  • $\begingroup$ No. $\:$ Consider the (completely insecure) commitment scheme where Alice chooses $k$ random bits, where if they're all zero then she sends length(her_value) additional random bits to Bob, otherwise she sends her_value to Bob, and Bob accepts a decommitment if and only if Alice presents randomness that matches the transcript of the commit phase. $\;\;$ $\endgroup$
    – user991
    Commented Mar 23, 2013 at 1:23
  • $\begingroup$ (Even a computationally bounded) Alice can decommit to any value by giving $k$ zeros and her message as her randomness, but that is not perfectly (or even computationally) hiding because Bob trivially has probability more than $\:1-(1/(2^k))\:$ of correctly guessing her_value. $\;\;$ $\endgroup$
    – user991
    Commented Mar 23, 2013 at 1:23
  • 1
    $\begingroup$ @RickyDemer: Your examples doesn't logically contradict what tylo wrote. $\neg p \wedge \neg q \wedge r$ does not contradict $p \rightarrow (q \rightarrow r)$. $\endgroup$
    – Henrick Hellström
    Commented Mar 23, 2013 at 10:21

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.