# Proof of computationally binding correct?

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.

The binding should be fine. You cannot change $$b$$ for the same commitment without changing $$$$. 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 $$ \oplus 1$$ from $$ \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:

$$$$ 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.

• 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..").
– Anon
Jun 12, 2022 at 8:05
• @Anon secure hash function is both collision resistant and pre-image resistant Jun 12, 2022 at 8:48
• 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 Jun 12, 2022 at 8:55
• 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?
– Anon
Jun 12, 2022 at 10:39
• @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. Jun 12, 2022 at 10:54