Revision History for: Coin Flipping
- 2026-06-07 at 18:57 by Mina Doosti
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 [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.
Protocols
The protocols that implement this functionality are:
Classical Analogues
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]Real-world Use Cases
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.
Properties
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.
Further Information
No content has been added to this section, yet!
References
* The original version of this page on the old QPZoo was created by Mathieu Bozzio.
[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. - 2025-06-24 at 21:23 by JuliaM
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 [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.
Protocols
The protocols that implement this functionality are:
Classical Analogues
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]Real-world Use Cases
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.
Properties
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.
Further Information
No content has been added to this section, yet!
References
[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. - 2025-05-15 at 12:34 by JuliaM
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 [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.
Protocols
No protocols implement this functionality yet.
Classical Analogues
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]Real-world Use Cases
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.
Properties
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.
Further Information
No content has been added to this section, yet!
References
[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. - 2025-05-15 at 11:34 by Mina Doosti