Coin flipping

A two-party coin-flipping protocol lets two parties generate a common bit such that a party deviating from the protocol cannot bias the honest party’s output, beyond a stated bound, away from uniform — Blu81.

Syntax

A coin-flipping protocol is a pair of efficient interactive algorithms $(A,B)$ that run on input $1^{\lambda }$ for $r(\lambda )$ rounds, after which each outputs a bit or $\perp$:

• $⟨A(1^{\lambda }),B(1^{\lambda })⟩\to (c_A,c_B)\in (\{0,1\}\cup \{\perp \}{)}^2$.

Properties

Correctness

When both parties follow the protocol, $c_A=c_B\in \{0,1\}$ and the common bit is uniform.

Security

In the game below the adversary corrupts $A$ and tries to make the honest $B$ output a bit $b^{\ast }$ of its choice; the game with the roles exchanged is analogous.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{coin}}_{\calA}(\secpar)$}
\begin{algorithmic}
\State $(b^*, \stA) \gets \calA(1^\secpar)$
\State $c_B \gets$ the output of $B$ in $\langle \calA(\stA), B(1^\secpar) \rangle$
\Comment{An output $c_B = \bot$ loses the game}
\Return $[c_B = b^*]$
\end{algorithmic}
\end{algorithm}

A protocol is secure with abort if for all efficient $\mathcal{A}$, corrupting either party,

$$\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{A}}^{\mathrm{coin}}(\lambda )=1\right]\le \frac{1}{2}+\mathrm{negl}(\lambda ).$$

It is $\epsilon$-fair, or has bias at most $\epsilon$, if the honest party outputs a bit even when the other party aborts and $\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{A}}^{\mathrm{coin}}(\lambda )=1\right]\le 1/2+\epsilon (\lambda )$ for all efficient $\mathcal{A}$.

Variations

Fair coin flipping

Fair coin flipping asks for negligible bias without abort. It is impossible: in every $r$-round protocol an efficient fail-stop adversary, which only aborts early, biases the honest party’s output by $\Omega (1/r)$ — Cle86.

Optimally fair coin flipping

An $r$-round protocol is optimally fair if its bias is $O(1/r)$, matching Cleve’s bound — MNS09.

No fully-black-box construction from a one-way function is optimally fair with $r=o(n/\log n)$ rounds, for the input length $n$ of the one-way function — DLMM11. The round restriction is removed for function-oblivious constructions, whose honest output, for fixed random tapes, does not depend on which one-way function is used — DMM14.

Coin flipping with constant bias

A protocol has constant bias if its bias is at most a constant $c<1/2$; bias $1/2$ is trivial, since one party can choose the outcome — HO11.

Participates in

Builds on Coin flipping

• Constant-bias coin flipping ⇒ OWF (via Coin flipping with constant bias)

Produces Coin flipping

• COM ⇒ Coin flipping (Blum)
• OT ⇒ Optimally fair coin flipping (Moran–Naor–Segev) (via Optimally fair coin flipping)