OWF ⇒ Statistically hiding COM (Haitner–Reingold)

Fully-black-box reduction · standard model · HR07 · security loss: polynomial

Statement

Every one-way function yields an interactive bit-commitment scheme that is statistically hiding and computationally binding — HR07.

Notes

• Statistical zero-knowledge arguments for $\mathbf{NP}$ from any one-way function came first — NOV06 — and follow from HR07’s commitments as in NOVY98.
• HR07’s protocol has polynomially many rounds; inaccessible entropy gives a simpler and more efficient construction — HRVW09. Every fully-black-box construction, even from a one-way permutation on $n$ bits, has $\Omega (n/\log n)$ rounds — HHRS07.
• For one-way permutations, interactive hashing gives the construction directly: OWP ⇒ statistically hiding COM — NOVY98.
• With collision-resistant hashing, two messages suffice: CRHF ⇒ statistically hiding COM — DPP97.