COM ⇒ OWF

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

Statement

If a bit-commitment scheme that is both hiding and binding exists, possibly interactive and with either property computational, then a one-way function exists — IL89.

Sketch

If no one-way function exists, the map from the committer’s bit and coins (and the honest receiver’s coins) to the commit-phase transcript is distributionally invertible. Given an honest commitment to $b$, a sampled preimage carries a bit that hiding makes nearly independent of $b$, so with probability about $1/2$ it opens the same commitment to $1-b$, breaking binding — IL89.

Notes

• The proof distributionally inverts functions built from the committer’s algorithm, as in SKE ⇒ OWF — IL89.
• Conversely, one-way functions give statistically binding commitments, through OWF ⇒ PRG — HILL99 — and PRG ⇒ COM — Naor91, and statistically hiding ones (OWF ⇒ statistically hiding COM) — HR07.
• No commitment scheme is both statistically hiding and statistically binding, so one of the two properties is always computational — folklore.