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

arXiv:1402.7166 · SIAM Journal on Computing

A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias

Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, Loïck Magnin

Published Jan 1, 2016• 33 citations
arXivHTMLPDF

Abstract

Mochon's proof [Quantum Weak Coin Flipping with Arbitrarily Small Bias, preprint, arXiv:0711.4114, 2007] of the existence of quantum weak coin flipping with arbitrarily small bias is a fundamental result in quantum cryptography, but at the same time one of the least understood. Though used several times as a black box in important follow-up results [M. Ganz, Quantum Leader Election, preprint, arXiv:0910.4952, 2009; A. Chailloux and I. Kerenidis, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 527--533; N. Aharon and J. Silman, New J. Phys., 12 (2010), 033027; A. Chailloux and I. Kerenidis, in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2011; I. Kerenidis and S. Zhang, in Theory of Quantum Computation, Communication, and Cryptography, Lecture Notes in Computer Science 7582, Springer, Berlin, 2013, pp. 13--28], the result has not been peer reviewed, its novel techniques (and, in particular, Kitaev's point game formalism) have not been applied anywhere else, and an explicit protocol is missing. We believe that truly understanding the existence proof and the novel techniques it relies on would constitute a major step in quantum information theory, leading to deeper understanding of entanglement and of quantum protocols in general. In this work, we make a first step in this direction. We simplify parts of Mochon's construction considerably, making about $20$ pages of analysis in the original proof superfluous, clarifying some other parts of the proof on the way, and presenting the proof in a way which is conceptually easier to grasp. We believe the resulting proof of existence is easier to understand, more readable, and certainly verifiable. Moreover, we analyze the resources neededto achieve a bias $\varepsilon$ and show that the number of qubits is $O(\log \frac{1}{\varepsilon})$, while the number of rounds is $(\frac{1}{\varepsilon})^{O(\frac{1}{\varepsilon})}$. A true understanding of the proof, including Kitaev's point-game techniques and their applicability, as well as completing the task of constructing an explicit (and also simpler and more efficient) protocol, are left to future work.

DOI
10.1137/14096387x

Related papers

Protocols for Quantum Weak Coin Flipping

Atul Singh Arora, Jérémie Roland, Chrysoula Vlachou +1 more

Weak coin flipping is an important cryptographic primitive$\unicode{x2013}$it is the strongest known secure two-party computation primitive that classically becomes secure only under certain assumptions (e.g. computational hardness), while quantumly there exist protocols that achieve arbitrarily close to perfect security. This breakthrough result was established by Mochon in 2007 [arXiv:0711.4114]. However, his proof relied on the existence of certain unitary operators which was established by a non-constructive argument. Consequently, explicit protocols have remained elusive. In this work, we give exact constructions of related unitary operators. These, together with a new formalism, yield a family of protocols approaching perfect security thereby also simplifying Mochon's proof of existence. We illustrate the construction of explicit weak coin flipping protocols by considering concrete examples (from the aforementioned family of protocols) that are more secure than all previously known protocols. 76 pages. This is the TheoretiCS journal version

arXiv:2402.15855•TheoretiCS•Nov 26, 2025•0 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

Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment

André Chailloux, Iordanis Kerenidis

Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the $30$th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than $1/\sqrt{2}$ [A. Kitaev, Presentation at the $6$th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to $1/\sqrt{2}$. More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2+\varepsilon$ in order to achieve a strong coin flipping protocol with cheating probability $1/\sqrt{2}+O(\varepsilon)$. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately $\gamma \approx 0.739$, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to $\gamma$. More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2 + \varepsilon$ in order to achieve a quantum bit commitment protocol with cheating probability $\gamma + O(\varepsilon)$. To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.

SIAM Journal on Computing•Jan 1, 2017•2 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

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

Quantum Leader Election

Maor Ganz

Leader election between n parties is known to be impossible classically. This work gives a simple algorithm that does it, based on the weak coin flipping protocol with arbitrarily small bias derived by Mochon in 2007, and recently published and simplified in Aharonov et al in 2016. A protocol with linear number of coin flipping rounds is quite simple to achieve; We further provide an improvement to logarithmic number of coin flipping rounds. This is a much improved journal version of a preprint posted in 2009: many typos are corrected, proofs are more rigorous and accurate, and the analysis of complexity is significantly tightened which gives a stronger result in terms of efficiency; The first protocol with linear number of rounds, was achieved independently also by Aharon and Silman in 2010.

arXiv:0910.4952•Oct 26, 2009•8 citations
Mochon's proof [Quantum Weak Coin Flipping with Arbitrarily Small Bias, preprint, arXiv:0711.4114, 2007] of the existence of quantum weak coin flipping with arbitrarily small bias is a fundamental result in quantum cryptography, but at the same time one of the least understood. Though used several times as a black box in important follow-up results [M. Ganz, Quantum Leader Election, preprint, arXiv:0910.4952, 2009; A. Chailloux and I. Kerenidis, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 527--533; N. Aharon and J. Silman, New J. Phys., 12 (2010), 033027; A. Chailloux and I. Kerenidis, in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2011; I. Kerenidis and S. Zhang, in Theory of Quantum Computation, Communication, and Cryptography, Lecture Notes in Computer Science 7582, Springer, Berlin, 2013, pp. 13--28], the result has not been peer reviewed, its novel techniques (and, in particular, Kitaev's point game formalism) have not been applied anywhere else, and an explicit protocol is missing. We believe that truly understanding the existence proof and the novel techniques it relies on would constitute a major step in quantum information theory, leading to deeper understanding of entanglement and of quantum protocols in general. In this work, we make a first step in this direction. We simplify parts of Mochon's construction considerably, making about 202020 pages of analysis in the original proof superfluous, clarifying some other parts of the proof on the way, and presenting the proof in a way which is conceptually easier to grasp. We believe the resulting proof of existence is easier to understand, more readable, and certainly verifiable. Moreover, we analyze the resources neededto achieve a bias ε\varepsilonε and show that the number of qubits is O(log⁡1ε)O(\log \frac{1}{\varepsilon})O(logε1​), while the number of rounds is (1ε)O(1ε)(\frac{1}{\varepsilon})^{O(\frac{1}{\varepsilon})}(ε1​)O(ε1​). A true understanding of the proof, including Kitaev's point-game techniques and their applicability, as well as completing the task of constructing an explicit (and also simpler and more efficient) protocol, are left to future work.
Weak coin flipping is an important cryptographic primitive$\unicode{x2013}$it is the strongest known secure two-party computation primitive that classically becomes secure only under certain assumptions (e.g. computational hardness), while quantumly there exist protocols that achieve arbitrarily close to perfect security. This breakthrough result was established by Mochon in 2007 [arXiv:0711.4114]. However, his proof relied on the existence of certain unitary operators which was established by a non-constructive argument. Consequently, explicit protocols have remained elusive. In this work, we give exact constructions of related unitary operators. These, together with a new formalism, yield a family of protocols approaching perfect security thereby also simplifying Mochon's proof of existence. We illustrate the construction of explicit weak coin flipping protocols by considering concrete examples (from the aforementioned family of protocols) that are more secure than all previously known protocols. 76 pages. This is the TheoretiCS journal version
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.
Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the 303030th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than 1/21/\sqrt{2}1/2​ [A. Kitaev, Presentation at the 666th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/21/\sqrt{2}1/2​. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+ε1/2+\varepsilon1/2+ε in order to achieve a strong coin flipping protocol with cheating probability 1/2+O(ε)1/\sqrt{2}+O(\varepsilon)1/2​+O(ε). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately γ≈0.739\gamma \approx 0.739γ≈0.739, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to γ\gammaγ. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+ε1/2 + \varepsilon1/2+ε in order to achieve a quantum bit commitment protocol with cheating probability γ+O(ε)\gamma + O(\varepsilon)γ+O(ε). To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.
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.
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.
Leader election between n parties is known to be impossible classically. This work gives a simple algorithm that does it, based on the weak coin flipping protocol with arbitrarily small bias derived by Mochon in 2007, and recently published and simplified in Aharonov et al in 2016. A protocol with linear number of coin flipping rounds is quite simple to achieve; We further provide an improvement to logarithmic number of coin flipping rounds. This is a much improved journal version of a preprint posted in 2009: many typos are corrected, proofs are more rigorous and accurate, and the analysis of complexity is significantly tightened which gives a stronger result in terms of efficiency; The first protocol with linear number of rounds, was achieved independently also by Aharon and Silman in 2010.