Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Information Processing Letters

Weak coin flipping with small bias

Iordanis Kerenidis, Ashwin Nayak

Published Feb 14, 2004• 26 citations
Publisher

Abstract

This note presents a quantum protocol that demonstrates that weak coin flipping with bias ≈ 0.239, less than 1/4, is possible. A bias of 1/4 was the smallest known, and followed from the strong coin flipping protocol of Ambainis [2]. Protocols with yet smaller bias ≈ 0.207 have independently been discovered [4, 10]. We also present an alternative strong coin flipping protocol with bias 1/4 with analysis simpler than that of [2]. 1 Quantum weak coin flipping Often in applications based on this primitive, coin-flipping is used to choose one of two competing parties as the “winner”. In the classic example from [5], Alice and Bob are getting a divorce, and would like to decide who gets the car. They decide to toss a coin for that purpose, but don’t trust each other. In such a scenario, they could instead play any fair game to decide the issue. Motivated by this, we consider the following weaker version of coin-flipping. A weak coin flipping protocol with bias ǫ, is a two-party communication game in the style of [11], in which the players start with no inputs, and compute a value cA,cB ∈ {0,1} respectively or declare that the other player is cheating. The protocol is deemed successful if Alice and Bob agree on the outcome, i.e. cA = cB.

DOI
10.1016/j.ipl.

Related papers

Weak coin flipping with small bias

Iordanis Kerenidis, Ashwin Nayak

This note presents a quantum protocol that demonstrates that_weak_ coin flipping with bias approximately 0.239, less than 1/4, is possible. A bias of 1/4 was the smallest known, and followed from the strong coin flipping protocol of [Ambainis 2001]. Protocols with yet smaller bias, approximately 0.207, have independently been discovered [Ambainis 2001, Spekkens and Rudolph 2002]. We also present an alternative strong coin flipping protocol with bias 1/4 with analysis simpler than that of [Ambainis 2001].

arXiv:quant-ph/0206121•Jun 19, 2002•0 citations

Quantum weak coin flipping

Atul Singh Arora, Jérémie Roland, Stephan Weis

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. A weak coin-flipping protocol has a bias є if neither player can force the outcome towards their preferred value with probability more than 1/2+є. While it is known that all classical protocols have є=1/2, Mochon showed in 2007 that quantumly weak coin flipping can be achieved with arbitrarily small bias (near perfect) but the former best known explicit protocol has bias 1/6 (also due to Mochon, 2005). We propose a framework to construct new explicit protocols achieving biases below 1/6. In particular, we construct explicit unitaries for protocols with bias down to 1/10. To go lower, we introduce what we call the Elliptic Monotone Align (EMA) algorithm which, together with the framework, allows us to construct protocols with arbitrarily small biases.

arXiv:1811.02984•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•10 citations

Quantum Weak Coin Flipping

Atul Singh Arora, Jérémie Roland, Stephan Weis

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. A weak coin-flipping protocol has a bias $\epsilon$ if neither player can force the outcome towards their preferred value with probability more than $\frac{1}{2}+\epsilon$. While it is known that all classical protocols have $\epsilon=\frac{1}{2}$, Mochon showed in 2007 [arXiv:0711.4114] that quantumly weak coin flipping can be achieved with arbitrarily small bias (near perfect) but the best known explicit protocol has bias $1/6$ (also due to Mochon, 2005 [Phys. Rev. A 72, 022341]). We propose a framework to construct new explicit protocols achieving biases below $1/6$. In particular, we construct explicit unitaries for protocols with bias approaching $1/10$. To go below, we introduce what we call the Elliptic Monotone Align (EMA) algorithm which, together with the framework, allows us to numerically construct protocols with arbitrarily small biases.

•Jan 1, 2018•9 citations

Cheat-Penalised Quantum Weak Coin-Flipping

Atul Singh Arora, Carl A. Miller, Mauro E. S. Morales +1 more

Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose $Λ$ points (compared to $0$ in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with $Λ=0.01$, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond $1/2 + 10^{-8}$, which uses $24$ qubits and $10^{16}$ rounds of communication (provably $10^{7}$ times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to $1/2 + 10^{-10}$) and reducing the rounds of communication (down to $25,180$), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.

arXiv:2510.03218•Oct 3, 2025•0 citations

Quantum weak coin flipping with a single photon

Mathieu Bozzio, Ulysse Chabaud, Iordanis Kerenidis +1 more

Weak coin flipping is among the fundamental cryptographic primitives which ensure the security of modern communication networks. It allows two mistrustful parties to remotely agree on a random bit when they favor opposite outcomes. Unlike other two-party computations, one can achieve information-theoretic security using quantum mechanics only: both parties are prevented from biasing the flip with probability higher than $1/2+\ensuremath{\epsilon}$, where $\ensuremath{\epsilon}$ is arbitrarily low. Classically, the dishonest party can always cheat with probability 1 unless computational assumptions are used. Despite its importance, no physical implementation has been proposed for quantum weak coin flipping. Here, we present a practical protocol that requires a single photon and linear optics only. We show that it is fair and balanced even when threshold single-photon detectors are used, and reaches a bias as low as $\ensuremath{\epsilon}=1/\sqrt{2}\ensuremath{-}1/2\ensuremath{\approx}0.207$. We further show that the protocol may display a quantum advantage over a few-hundred meters with state-of-the-art technology.

arXiv:2002.09005•Physical Review A•Aug 19, 2020•19 citations

Analytic quantum weak coin flipping protocols with arbitrarily small bias

Atul Singh Arora, Jérémie Roland, Chrysoula Vlachou

Weak coin flipping (WCF) is a fundamental cryptographic primitive for two-party secure computation, where two distrustful parties need to remotely establish a shared random bit whilst having opposite preferred outcomes. It is the strongest known primitive with arbitrarily close to perfect security quantumly while classically, its security is completely compromised (unless one makes further assumptions, such as computational hardness). A WCF protocol is said to have bias $\epsilon$ if neither party can force their preferred outcome with probability greater than $1/2+\epsilon$. Classical WCF protocols are shown to have bias $1/2$, i.e., a cheating party can always force their preferred outcome. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias $\epsilon (k)=1/(4k+2)$ for arbitrarily large $k$ and proposed a protocol with bias $1/6$. Last year, Arora, Roland and Weis presented a protocol with bias $1/10$ and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC'19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon's proof. As an example, we illustrate the construction of a WCF protocol with bias $1/14$.

arXiv:1911.13283•Nov 29, 2019•1 citation
This note presents a quantum protocol that demonstrates that weak coin flipping with bias ≈ 0.239, less than 1/4, is possible. A bias of 1/4 was the smallest known, and followed from the strong coin flipping protocol of Ambainis [2]. Protocols with yet smaller bias ≈ 0.207 have independently been discovered [4, 10]. We also present an alternative strong coin flipping protocol with bias 1/4 with analysis simpler than that of [2]. 1 Quantum weak coin flipping Often in applications based on this primitive, coin-flipping is used to choose one of two competing parties as the “winner”. In the classic example from [5], Alice and Bob are getting a divorce, and would like to decide who gets the car. They decide to toss a coin for that purpose, but don’t trust each other. In such a scenario, they could instead play any fair game to decide the issue. Motivated by this, we consider the following weaker version of coin-flipping. A weak coin flipping protocol with bias ǫ, is a two-party communication game in the style of [11], in which the players start with no inputs, and compute a value cA,cB ∈ {0,1} respectively or declare that the other player is cheating. The protocol is deemed successful if Alice and Bob agree on the outcome, i.e. cA = cB.
This note presents a quantum protocol that demonstrates that_weak_ coin flipping with bias approximately 0.239, less than 1/4, is possible. A bias of 1/4 was the smallest known, and followed from the strong coin flipping protocol of [Ambainis 2001]. Protocols with yet smaller bias, approximately 0.207, have independently been discovered [Ambainis 2001, Spekkens and Rudolph 2002]. We also present an alternative strong coin flipping protocol with bias 1/4 with analysis simpler than that of [Ambainis 2001].
We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. A weak coin-flipping protocol has a bias є if neither player can force the outcome towards their preferred value with probability more than 1/2+є. While it is known that all classical protocols have є=1/2, Mochon showed in 2007 that quantumly weak coin flipping can be achieved with arbitrarily small bias (near perfect) but the former best known explicit protocol has bias 1/6 (also due to Mochon, 2005). We propose a framework to construct new explicit protocols achieving biases below 1/6. In particular, we construct explicit unitaries for protocols with bias down to 1/10. To go lower, we introduce what we call the Elliptic Monotone Align (EMA) algorithm which, together with the framework, allows us to construct protocols with arbitrarily small biases.
We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. A weak coin-flipping protocol has a bias ϵ\epsilonϵ if neither player can force the outcome towards their preferred value with probability more than 12+ϵ\frac{1}{2}+\epsilon21​+ϵ. While it is known that all classical protocols have ϵ=12\epsilon=\frac{1}{2}ϵ=21​, Mochon showed in 2007 [arXiv:0711.4114] that quantumly weak coin flipping can be achieved with arbitrarily small bias (near perfect) but the best known explicit protocol has bias 1/61/61/6 (also due to Mochon, 2005 [Phys. Rev. A 72, 022341]). We propose a framework to construct new explicit protocols achieving biases below 1/61/61/6. In particular, we construct explicit unitaries for protocols with bias approaching 1/101/101/10. To go below, we introduce what we call the Elliptic Monotone Align (EMA) algorithm which, together with the framework, allows us to numerically construct protocols with arbitrarily small biases.
Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose ΛΛΛ points (compared to 000 in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with Λ=0.01Λ=0.01Λ=0.01, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond 1/2+10−81/2 + 10^{-8}1/2+10−8, which uses 242424 qubits and 101610^{16}1016 rounds of communication (provably 10710^{7}107 times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to 1/2+10−101/2 + 10^{-10}1/2+10−10) and reducing the rounds of communication (down to 25,18025,18025,180), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.
Weak coin flipping is among the fundamental cryptographic primitives which ensure the security of modern communication networks. It allows two mistrustful parties to remotely agree on a random bit when they favor opposite outcomes. Unlike other two-party computations, one can achieve information-theoretic security using quantum mechanics only: both parties are prevented from biasing the flip with probability higher than $1/2+\ensuremath{\epsilon}$, where $\ensuremath{\epsilon}$ is arbitrarily low. Classically, the dishonest party can always cheat with probability 1 unless computational assumptions are used. Despite its importance, no physical implementation has been proposed for quantum weak coin flipping. Here, we present a practical protocol that requires a single photon and linear optics only. We show that it is fair and balanced even when threshold single-photon detectors are used, and reaches a bias as low as $\ensuremath{\epsilon}=1/\sqrt{2}\ensuremath{-}1/2\ensuremath{\approx}0.207$. We further show that the protocol may display a quantum advantage over a few-hundred meters with state-of-the-art technology.
Weak coin flipping (WCF) is a fundamental cryptographic primitive for two-party secure computation, where two distrustful parties need to remotely establish a shared random bit whilst having opposite preferred outcomes. It is the strongest known primitive with arbitrarily close to perfect security quantumly while classically, its security is completely compromised (unless one makes further assumptions, such as computational hardness). A WCF protocol is said to have bias ϵ\epsilonϵ if neither party can force their preferred outcome with probability greater than 1/2+ϵ1/2+\epsilon1/2+ϵ. Classical WCF protocols are shown to have bias 1/21/21/2, i.e., a cheating party can always force their preferred outcome. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias ϵ(k)=1/(4k+2)\epsilon (k)=1/(4k+2)ϵ(k)=1/(4k+2) for arbitrarily large kkk and proposed a protocol with bias 1/61/61/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/101/101/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC'19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon's proof. As an example, we illustrate the construction of a WCF protocol with bias 1/141/141/14.