Coin Flipping

Functionality description

Coin flipping is a cryptographic primitive which allows two mistrustful parties, Alice and Bob, to remotely generate a random bit, such that none of the two parties can bias the outcome beyond a specified probability.

In order to explicit the protocol properties, let us first define and upper-bound Alice and Bob's probabilities of forcing their opponent to declare outcome $i$ as:

$P_{A}^{(i)}\leq 1/2+\epsilon _{A}^{(i)}$ Alice forces Bob to declare $i$

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{B}^{(i)} \leq 1/2 + \epsilon_B^{(i)} } Bob forces Alice to declare $i$

Properties

• A coin flipping scheme is fair when it outputs bit $0$ with probability ${\frac {1-\Delta }{2}}$ and bit $1$ with probability ${\frac {1-\Delta }{2}}$, where $\Delta$ is the honest probability that the protocol aborts.
• A coin flipping scheme is secure with bias $\epsilon$ when none of the parties can force any outcome with probability higher than ${\frac {1}{2}}+\epsilon$, where $\epsilon =\max {\Bigg \{}\epsilon _{A}^{(0)},\epsilon _{A}^{(1)},\epsilon _{B}^{(0)},\epsilon _{B}^{(1)}{\Bigg \}}$ .
• A coin flipping scheme is balanced when $\epsilon _{A}^{(0)}=\epsilon _{A}^{(1)}=\epsilon _{B}^{(0)}=\epsilon _{B}^{(1)}$.

Protocols

Strong coin flipping (SCF)

In SCF, two parties remotely wish to agree on a random bit such that none of the parties can bias any outcome with a probability higher than $1/2+\epsilon$, where $\epsilon$ is the protocol bias. SCF is fundamental in multiparty computation, online gaming and more general randomized consensus protocols involving leader election.

Using quantum mechanics, information-theoretically secure SCF is possible, but with a fundamental lower bound on the achievable bias:

$\epsilon \geqslant {\frac {1}{\sqrt {2}}}-{\frac {1}{2}}\approx 0.207.$

Weak coin flipping (WCF)

In WCF, two parties wish to agree on a random bit in the same manner as SCF, but given that they both have known, preferred, opposite outcomes. In other words, the outcome of the flip will designate a winner and a loser. In the classical world, WCF arises from SCF with two unconstrained biases (Alice and Bob can always choose to lose with probability $P_{A}^{(1)}=P_{B}^{(0)}=1$):

$P_{A}^{(0)}\leqslant {\frac {1}{2}}+\epsilon _{A}^{(0)}$ Alice forces Bob to declare $0$

$P_{A}^{(1)}=1$ Alice forces Bob to declare $1$

$P_{B}^{(0)}=1$ Bob forces Alice to declare $0$

$P_{B}^{(1)}\leqslant {\frac {1}{2}}+\epsilon _{B}^{(1)}$ Bob forces Alice to declare $1$

With quantum mechanics, on the other hand, WCF is crucial to the construction of optimal quantum SCF and quantum bit commitment schemes. Crucially and unlike quantum SCF, quantum WCF may reach biases arbitrarily close to zero:

$\epsilon \rightarrow 0.$

References

contributed by Mathieu Bozzio