OWP ⇒ Statistically hiding COM (NOVY)

Fully-black-box reduction · standard model · NOVY98 · security loss: polynomial: a cheating committer opening both ways with probability ε inverts the permutation with probability poly(ε, 1/n)

Statement

Every one-way permutation $\pi$ on $\{0,1{\}}^n$ yields an interactive bit-commitment scheme that is perfectly hiding and computationally binding, with $n-1$ rounds of interactive hashing — NOVY98.

Sketch

To commit to $\beta$, the committer samples $x\stackrel{\$}{\leftarrow }\{0,1{\}}^n$ and sets $y:=\pi (x)$; in round $i<n$ the receiver sends a uniform $h_i\in \{0,1{\}}^n$ linearly independent of $h_1,\dots ,h_{i-1}$ and the committer replies $⟨h_i,y⟩$. Exactly two strings $y_0<y_1$ are consistent with the answers, and the committer sends $\beta \oplus c$ where $y=y_c$; to open, it reveals $x$. The transcript is identically distributed whether $y=y_0$ or $y=y_1$, so hiding is perfect, and opening both ways requires preimages of both $y_0$ and $y_1$, which the interactive hashing makes as hard as inverting $\pi$ at a uniform point.

Notes

• Round complexity is optimal up to a logarithmic factor for this kind of construction: every fully-black-box construction of a statistically hiding commitment from a one-way permutation, or even a trapdoor permutation, on $n$ bits has $\Omega (n/\log n)$ rounds — HHRS07.
• With a perfectly hiding commitment, the GMW91 protocol for Graph 3-Colouring becomes a perfect zero-knowledge argument for $\mathbf{NP}$, which is NOVY98’s application; a statistically hiding one gives statistical zero knowledge — NOVY98.
• One-way functions suffice: OWF ⇒ statistically hiding COM — HR07.