I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous proof that why even subject to $u(x)=m$, the still leaves distribution of $u$ look almost uniform to the adversary independent of $m$.

Thanks for any help, hint or reference.

enter image description here

What's more, if we change the construction in the picture. Let $c=(u,h(x),u(x)\oplus m)$, where $u$ is uniformly distributed over $\mathcal{U}$ and the other things are same. Then, we can use the leftover hash lemma to proof hiding. And the binding is still based on CRHF.


1 Answer 1


I believe this is the commitment scheme from Halevi and Micali in Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing.

The security analysis is given in section 3.1.

At a high level, they show that: given messages $m_1, m_2$; Define $C(m) = (u ,y)$ being the random variable corresponding to producing a commitment on $m$ (the scheme is randomized); and $y = h(x)$. Furthermore, the statistical distance between $C(m_1)$ and $C(m_2)$ defined as $$\Delta(C; m_1, m2) = \sum_{u,y}|\Pr[C(m_1) = (u,y)] - \Pr[C(m_2) = (u, y)]| \leq 2^k.$$ The argument is a bit technical and well described in the paper. But it boils down to: although $u(x) = m$, the distribution on $u$ with this constraint is statistically close to the distribution induced for a different $m'$. Therefore, reveals very little information on the message.


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.