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 [1]. One can think of this functionality as agreeing on a coin flip over the phone. More explicitly, let us first define this functionality as the upper-bound on Alice and Bob’s probabilities of forcing their opponent to declare a specific outcome $c$. We want:
$P_{A}^{(c)}\leq 1/2+\epsilon _{A}^{(c)}$ where Alice can bias the outcome towards (c), and
$P_{B}^{(c)}\leq 1/2+\epsilon _{B}^{(c)}$ where Bob can bias the outcome towards (c)

The values of $\epsilon _{A}$ and $\epsilon _{B}$ are called biases. Coin flipping is a completely randomised primitive. There is no fixed function that determines the outputs of the players.

Coin-flipping is originally a classical functionality, which is impossible to achieve classically without any further assumption.
Computationally secure classical coin flipping protocol exists, such as the ones in [1], [2], [3]

Coin flipping is a fundamental primitive in cryptography and is used in many other multiparty protocols. Specifically, it is a fundamental subroutine in multiparty computation, online gaming, and more general randomised consensus protocols involving leader election.

A coin flipping scheme is:

• Correct: when both Alice and Bob are honest, then c is uniformly distributed: $p(c = 0) = p(c = 1) = 1/2$.
• 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 at which the protocol aborts.
• 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 \}}$.
• Balanced: when $\epsilon _{A}^{(0)}=\epsilon _{A}^{(1)}=\epsilon _{B}^{(0)}=\epsilon _{B}^{(1)}$.

In addition to these properties, there exist two types of coin-flipping protocols:

• Strong coin flipping (SCF): In SCF, two parties remotely wish to agree on a random bit, and there is no pre-determined value for this bit. i.e. Alice and Bob may wish for either 0 or 1 as their favourite outcome. This functionality is stronger (harder to achieve) than when we know beforehand what Alice’s favourite outcome is, hence the name. It has been shown in [1] that strong coin-flipping is classically impossible without any further assumption. This means that no classical coin flipping protocol is secure, i.e. no value of $\epsilon < 1/2$ can be achieved for security! This is an information-theoretic impossibility, and computationally, one can achieve a strong coin-flipping classically.
  Strong coin flipping is also impossible to achieve quantumly with zero bias ($\ epsilon=0$), but unlike in the classical world, it is possible to achieve strong coin-flipping with some non-zero bias smaller than 1/2. The fundamental information-theoretic lower bound for the bias of secure SCF in the quantum world is shown by Kitaev [4] as:
  $$\epsilon \geqslant {\frac {1}{\sqrt {2}}}-{\frac {1}{2}}\approx 0.207.$$
• Weak coin flipping (WCF): In WCF, the two parties 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 and $P_{A}^{(1)}=1$ Alice forces Bob to declare 1.
  $P_{B}^{(0)}=1$ Bob forces Alice to declare 0, and $P_{B}^{(1)}\leqslant {\frac {1}{2}}+\epsilon _{B}^{(1)}$ Bob forces Alice to declare 1. The impossibility still holds in the classical setting.
  However, with quantum mechanics, it has been shown[5] that weak quantum coin flipping, with arbitrarily small (but non-zero) bias $\epsilon$, is possible. Later, a concrete protocol was shown in 2019 [6] that achieves a bias of around 1/10.

[1] Blum, Manuel. “Coin flipping by telephone a protocol for solving impossible problems.” ACM SIGACT News 15, no. 1 (1983): 23-27.
[2] Biham, Eli, and Adi Shamir. “Differential cryptanalysis of DES-like cryptosystems.” Journal of CRYPTOLOGY 4 (1991): 3-72.
[3] Goldreich, Oded, Silvio Micali, and Avi Wigderson. “How to play any mental game, or a completeness theorem for protocols with honest majority.” In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 307-328. 2019.
[4] Chailloux, André, and Iordanis Kerenidis. “Optimal quantum strong coin flipping.” In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 527-533. IEEE, 2009.
[5] Mochon, Carlos. “Quantum weak coin flipping with arbitrarily small bias.” arXiv preprint arXiv:0711.4114 (2007).
[6] Arora, Atul Singh, Jérémie Roland, and Stephan Weis. “Quantum weak coin flipping.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 205-216. 2019.