COM ⇒ Coin flipping (Blum)

Fully-black-box reduction · standard model · Blu81 · security loss: the bias is at most the hiding advantage plus the binding advantage

Statement

A commitment scheme hiding for adversarial public parameters yields a coin-flipping protocol secure with abort: $B$ samples $\mathsf{pp}\leftarrow \mathsf{Gen}(1^{\lambda })$ and sends it, $A$ commits to a uniform bit $a$, $B$ replies with a uniform bit $b$, $A$ opens $a$, and both output $a\oplus b$, with $B$ outputting $\perp$ if the opening fails — Blu81, who instantiated the commitment from quadratic residuosity modulo Blum integers.

Sketch

Against a corrupt $B$, hiding for the $\mathsf{pp}$ that $B$ chose makes $b$ independent of $a$, so $a\oplus b$ is uniform. Against a corrupt $A$, binding for the honestly sampled $\mathsf{pp}$ fixes $a$ before $b$ is chosen, so the opened value is $a$ or the opening fails, and $a\oplus b$ is uniform unless $B$ outputs $\perp$.

Notes

• $A$ learns the outcome first and may abort, so the protocol is not fair; no protocol is (fair coin flipping) — Cle86. Running $r$ such flips in sequence and outputting their majority, with the honest party replacing the flips left after an abort by its own coins, gives bias $O(1/\sqrt{r})$ from one-way functions — Cle86.
• Conversely, coin flipping with bias at most a constant $c<1/2$ implies one-way functions (constant-bias coin flipping ⇒ OWF) — HO11 for bias about $0.207$, BHT14 for every constant $c<1/2$.
• With a commitment that is hiding and binding only for honestly sampled $\mathsf{pp}$, neither party can be trusted to sample it: an equivocable $\mathsf{pp}$ chosen by $A$ (Pedersen with known ${\log }_{g}h$) lets $A$ fix the output, and a $\mathsf{pp}$ chosen by $B$ may let $B$ read $a$; a commitment binding for every $\mathsf{pp}$ works with $A$ sampling it instead — standard.