It is well known that one can construct a simple commitment scheme in the random oracle model (ROM) by setting $\mathsf{Commit}(m;r) = H(r||m)$, where $m \in \{0,1\}^k$, $r \in \{0,1\}^{2k}$ and $H: \{0,1\}^* \to \{0,1\}^k$ is modelled as a Random Oracle. My question is: How can I formally prove that this scheme is statistically hiding? Intuitively, the RO is "compressing" and therefore there will be enough random strings $r, r'$ such that a challange commitment $c$ in the hiding experiment can have preimages of the form $r||m_0$ or $r'||m_1$ with similar high probability, so even an unbounded adversary has negligible advantage in the experiment. But that is merely an intuition and not a formal proof. I would be really thankful for some advice on how to prove the statement.

(Additionally I'm wondering if random strings $r$ of length $2k$ are enough to achieve statistically hiding. Maybe one can see in the proof that we need a longer random string.)


1 Answer 1


Statistical hiding for a commitment is not about the distribution of inputs associated with a given commitment output, but rather the distribution of commitment outputs associated with a given pair of messages.

What you need to show is that for any two fixed messages, the total variation distance between the two distributions of outputs is small. Now, the statistical distance is a metric and so the triangle inequality applies. A good choice for the third distribution is the uniform distribution on $2^k$ outputs. The random oracle model means that the total variation of the distribution of outputs for a fixed message has small total variation distance from uniform and so by the triangle inequality, the distribution of outputs for two fixed, distinct messages has small total variation distance.


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.