Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
If I use a hash function to construct the commitment scheme, can I say it is perfectly hiding?
In commit stage, $$ c = C(m, r)$$
In reveal stage, by revealing $r$ and verify $$c = C(m, r)$$
Because there is $m'$ and $r'$ exist for $$C(m, r) = C(m', r')$$ So it is perfectly hiding, and it can open it both ways, so it is computationally binding.
Am I correct?
No, the proposed commitment scheme is not perfectly hiding. Depending on what you require from the hash function, it may not be hiding at all.
If you only require collision resistance (which would be the standard security property of a hash function) you cannot prove the construction even computationally hiding. This is because a collision resistant hash function may leak some limited information about its input. E.g., it might leak the first bit of its input which immediately breaks hiding.
However, the construction you're looking at is a folklore commitment scheme in the Random Oracle Model, where $C$ is modeled as a random oracle. In this case, the construction is computationally hiding, but it is not perfectly hiding. The reason is the following: While you observation that, due to compression, there must exist some $m',r'$ such that $C(m,r)=C(m',r')$ this is not sufficient.
Perfect hiding would require that for any $m'$ there exists an $r'$, such that $C(m,r)=C(m',r')$. And this is generally not the case (and indeed unlikely) for a random function.
