Join Log in
Score:5
constantine avatar Crypto

The rigorous proof in the commitment based on CRHF

cn flag
constantine

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.

91
1 + 0
Score:2
Marc Ilunga avatar Crypto
tr flag
Marc Ilunga

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.

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.