CRHF ⇒ Statistically hiding COM

Fully-black-box reduction · standard model · DPP97, HM96 · security loss: none: two valid openings to different messages are a collision

Statement

A collision-resistant hash function family yields a two-message commitment scheme that is statistically hiding and computationally binding: the receiver sends a hash key $k$, and the committer sends a commitment computed with ${\mathsf{H}}_k$ — DPP97, HM96.

Sketch

Let ${\mathsf{H}}_k:\{0,1{\}}^n\to \{0,1{\}}^{n^{\prime }}$ compress by $n-n^{\prime }\ge |m|+2\log (1/\epsilon )$ bits; Merkle–Damgård iteration gives such a family from any collision-resistant one — Dam89. To commit to $m$, sample $x\stackrel{\$}{\leftarrow }\{0,1{\}}^n$ and a pairwise-independent $g:\{0,1{\}}^n\to \{0,1{\}}^{|m|}$, and send $({\mathsf{H}}_k(x),g,g(x)\oplus m)$; to open, reveal $x$. The input $x$ keeps average min-entropy $n-n^{\prime }$ given ${\mathsf{H}}_k(x)$, so by the leftover hash lemma $g(x)$ is $\epsilon$-close to uniform and hiding holds against unbounded receivers for every key; two openings $x\ne x^{\prime }$ to different messages share ${\mathsf{H}}_k(x)={\mathsf{H}}_k(x^{\prime })$ — standard.

Notes

• Efficiency: one hash evaluation; the commitment is $n^{\prime }+|m|$ bits plus the description of $g$, and an opening is $n$ bits — standard.
• One-way functions suffice with polynomially many rounds: OWF ⇒ statistically hiding COM — HR07. Every fully-black-box construction, even from a one-way permutation on $n$ bits, has $\Omega (n/\log n)$ rounds, against two messages from a CRHF — HHRS07.