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:

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_{A}^{(i)} \leq 1/2 + \epsilon_A^{(i)} } Alice forces Bob to declare 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 i}

$P_{B}^{(i)}\leq 1/2+\epsilon _{B}^{(i)}$ Bob forces Alice to declare 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 i}

Properties

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

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 \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 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_{A}^{(1)}=P_{B}^{(0)}=1} ):

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_{A}^{(0)} \leqslant\frac{1}{2}+\epsilon_A^{(0)} } Alice forces Bob to declare 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 0}

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_{A}^{(1)}=1 } Alice forces Bob to declare 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 1}

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}^{(0)}=1 } Bob forces Alice to declare 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 0}

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}^{(1)}\leqslant\frac{1}{2}+ \epsilon_B^{(1)} } Bob forces Alice to declare 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 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:

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 \epsilon \rightarrow 0. }

References

contributed by Mathieu Bozzio