OT ⇒ Optimally fair coin flipping (Moran–Naor–Segev)

Standard model · MNS09 · security loss: additive: the bias $O(1/r)$ with an ideal dealer, plus the simulation advantage of the secure computation replacing it

Statement

If OT exists, then for every polynomial $r$ there is an $r$-round two-party coin-flipping protocol with bias $O(1/r)$, matching Cleve’s lower bound — MNS09.

Sketch

A secure computation deals both parties, round by round, values that are independent uniform bits before a secret uniform round $i^{\ast }\in [r]$ and equal to the outcome from $i^{\ast }$ on; when a party aborts, the other outputs its last value. An aborting party changes the outcome only by aborting at $i^{\ast }$ itself, which its view lets it guess with probability $O(1/r)$, so the bias is $O(1/r)$ — MNS09.

Notes

• The protocol uses general secure computation, which OT provides (OT ⇒ MPC), to deal the parties shares of a sequence of values that switch at a secret uniform round from independent coins to the final output — MNS09.
• No fully-black-box construction from one-way functions alone reaches this bias with $o(n/\log n)$ rounds, for the input length $n$ of the one-way function — DLMM11.