No reduction from authenticated channels to fair coin flipping

Unconditional · against free reductions · Cle86

Statement

No two-party coin-flipping protocol over an authenticated channel without setup has negligible bias: for every $r$-round protocol an efficient fail-stop adversary, which runs the protocol honestly and only chooses when to abort, biases the honest party’s output by $\Omega (1/r)$ — Cle86. The adversary runs only the protocol’s own code, so the bound holds whatever hardness assumption the protocol relies on, and no reduction of any kind builds fair coin flipping from authenticated channels.

Notes

• The bound is tight: given OT, for every $r$ there is an $r$-round protocol with bias $O(1/r)$ (OT ⇒ optimally fair coin flipping) — MNS09.
• The same attack rules out completely fair two-party computation of Boolean XOR (no reduction from authenticated channels to fair MPC) — Cle86.