If I use a hash function to construct the commitment scheme, can I say it is perfectly hiding?

  • $m$ is the message
  • $r$ is a random value

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.

| improve this answer | |
  • $\begingroup$ So it must be all $m'$ exists $r'$ fulfilling $๐ถ(๐‘š,๐‘Ÿ)=๐ถ(๐‘šโ€ฒ,๐‘Ÿโ€ฒ)$, then we can call it perfect hiding? $\endgroup$ – Jeff Lee Mar 23 at 13:12
  • $\begingroup$ @JeffLee That is a necessary condition, not a sufficient one. $\endgroup$ – Maeher Mar 23 at 13:16
  • $\begingroup$ Can I say so if we use $g=a^m b^r mod p$ for the C, it is perfectly hiding, but computationally hiding? $\endgroup$ – Jeff Lee Mar 23 at 13:23
  • $\begingroup$ It is perfectly hiding, but computationally binding (under the dlog assumption). $\endgroup$ – Geoffroy Couteau Mar 23 at 15:37

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.