1
$\begingroup$

I have defined the following commitment scheme and would like to prove that it is statistically hiding and computationally binding, but I'm not sure if my proof is accurate:

For $h$, a collision resistant hash function, I defined the following scheme:

$C(b, 1^n)$:

$r \leftarrow U_n$ // random uniform string of length $n$

$s \leftarrow U_n$

Output $(h(s), r, \langle r, s \rangle \oplus b)$

Proofs:

Computationally binding:

Let $A$ be a PPT algorithm. Then:

$$ \Pr_{(s,s')\leftarrow A(1^n)}\big[ \langle r, s \rangle \oplus 0 = \langle r, s \rangle \oplus 1 \text{ }\wedge \text{ } h(s)=h(s')\big] \leq \Pr_{(s,s')\leftarrow A(1^n)}\big[ h(s)=h(s')\big] \leq negl(n)$$

where the last transition is since the $h$ is assumed to be a collision resistant hash function.

Statistically hiding (~ denotes statistically indistinguishable from):

$$ C(0) = (h(s), r, \langle r, s \rangle \oplus 0) = (h(s), r, \langle r, s \rangle) \sim (h(s), r, U) \sim (h(s), r, U\oplus 1) \sim (h(s), r, \langle r, s \rangle \oplus 1)=C(1)$$

I am mainly concerned with the computationally binding part since this is not a family of hash functions, so the last transition doesn't feel right.

Is this right? Any comments would be greatly appreciated.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

The binding should be fine. You cannot change $b$ for the same commitment without changing $<r,s>$. Since $r$ is part of commitment, you can only change $s$ which should be infeasible because $h$ is collision resistant. What do you mean by $h$ is not a family of hash functions? Why should it be?

I am less confident about the hiding part. If $h$ does not need to be pre-image resistant, we can just define $h$ as $h(s)=s$ and the commitment is not hiding at all. I therefore assume you really mean a secure hash function. So the question is "Is it possible for $h$ to reveal enough information about $s$ that given a random $r$ and $h(s)$ gives a significant advantage in distinguishing $<r,s> \oplus 1$ from $<r,s> \oplus 0$ and still be a secure hash function?" Because if such a hash function exists the part after your "=" in the first line of your proof does not hold.

EDIT:

$<r,s>$ is a hardcore predicate of $f(s,r)=h(s),r$ so no such $h$ does exist as long as $h$ is secure hash function (both one way and collision resistant). But it only makes it computationally hiding not necessarily statistically hiding.

$\endgroup$
5
  • $\begingroup$ Thanks. I'm not sure I understand the first part since I'm not familiar with the definition of "secure hash function" (unless you mean collision resistant hash function, which $h$ is). Would it help if I assumed all elements in the range of $h$ had the same number of pre-images? Also, if I can find a way to prove that the first and last $\sim$ are correct, then after the $=$ would hold, right? (trying to understand where you think the issue is that needs to be addresses in the second part of your response starting with "So the question is.."). $\endgroup$
    – Anon
    Commented Jun 12, 2022 at 8:05
  • $\begingroup$ @Anon secure hash function is both collision resistant and pre-image resistant $\endgroup$ Commented Jun 12, 2022 at 8:48
  • 1
    $\begingroup$ Since $h(s)$ has the the same domain as $s$, your second assumption would make $h$ a one way permutation. I do not see how this would help. Yes, if you can prove that the indistinguishability holds for any hash function as long as it is both pre-image and collision resistant, then you can prove it is at least computationallyy hiding. To prove that it is statistically hiding you have to show that distribution of $h(s),r,<r,s> $ and $h(s),r,<r,s> \oplus 1 $ are almost identical. Proving your first $\sim$ after = suffices because statistically similar to random bit is enough $\endgroup$ Commented Jun 12, 2022 at 8:55
  • $\begingroup$ What if I demand that $h$ maps from size $n$ to size $n/2$? Then, in particular, it cannot be the identity function so there's no case where $h(s)=s$. Might that now alleviate the issue you mentioned? $\endgroup$
    – Anon
    Commented Jun 12, 2022 at 10:39
  • $\begingroup$ @Anon, that was not my main point. I just mentioned it to demonstrate that $h$ needs to be both collision resistant and pre-image resistant. See my last paragraph that I added. $\endgroup$ Commented Jun 12, 2022 at 10:54

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.