Editing Coin Flipping (section)

==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 <math>1/2+\epsilon</math>, where <math>\epsilon</math> 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:

<math> \epsilon \geqslant \frac{1}{\sqrt{2}}-\frac{1}{2} \approx 0.207. </math>



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

<math> P_{A}^{(0)} \leqslant\frac{1}{2}+\epsilon_A^{(0)} </math> Alice forces Bob to declare <math>0</math>

<math> P_{A}^{(1)}=1 </math> Alice forces Bob to declare <math>1</math>

<math> P_{B}^{(0)}=1 </math> Bob forces Alice to declare <math>0</math>

<math> P_{B}^{(1)}\leqslant\frac{1}{2}+ \epsilon_B^{(1)} </math> Bob forces Alice to declare <math>1</math>


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:

<math> \epsilon \rightarrow 0. </math>