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:2402.15233 · Quantum

On the composable security of weak coin flipping

Jiawei Wu, Yanglin Hu, Akshay Bansal, Marco Tomamichel

Published Jun 24, 2025• 1 citation
arXivHTMLPDF

Abstract

Weak coin flipping is a cryptographic primitive in which two mutually distrustful parties generate a shared random bit to agree on a winner via remote communication. While a stand-alone secure weak coin flipping protocol can be constructed from noiseless quantum communication channels, its composability remains unexplored. In this work, we demonstrate that no weak coin flipping protocol can be abstracted as a simple black-box resource with composable security. Despite this, we also establish the overall stand-alone security of quantum weak coin flipping protocols under composition in sequential order.

DOI
10.22331/q-2025-06-24-1780

Related papers

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

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

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

Dilemma that Cannot Be Resolved by Biased Quantum Coin Flipping

Satoshi Ishizaka

We show that a biased quantum coin flip (QCF) cannot provide the performance of a black-boxed biased coin flip, if it satisfies some fidelity conditions. Although such a QCF satisfies the security conditions of a biased coin flip, it does not realize the ideal functionality and, therefore, does not satisfy the demands for universally composable security. Moreover, through a comparison within a small restricted bias range, we show that an arbitrary QCF is distinguishable from a black-boxed coin flip unless it is unbiased on both sides of parties against insensitive cheating. We also point out the difficulty in developing cheat-sensitive quantum bit commitment in terms of the uncomposability of a QCF.

arXiv:quant-ph/0703099•Physical Review Letters•Feb 19, 2008•7 citations

Optimal Quantum Strong Coin Flipping

André Chailloux, Iordanis Kerenidis

Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambain is achieved a cheating probability of at most 3/4. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2}. Closing this gap has been one of the important open questions in quantum cryptography. In this paper, we resolve this question by presenting 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+epsilon in order to achieve a strong coin flipping protocol with cheating probability 1/sqrt{2}+O(epsilon). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon.

arXiv:0904.1511•Annual Symposium on Foundations of Computer Science•Oct 1, 2009•67 citations
Weak coin flipping is a cryptographic primitive in which two mutually distrustful parties generate a shared random bit to agree on a winner via remote communication. While a stand-alone secure weak coin flipping protocol can be constructed from noiseless quantum communication channels, its composability remains unexplored. In this work, we demonstrate that no weak coin flipping protocol can be abstracted as a simple black-box resource with composable security. Despite this, we also establish the overall stand-alone security of quantum weak coin flipping protocols under composition in sequential order.
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.
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.
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
We show that a biased quantum coin flip (QCF) cannot provide the performance of a black-boxed biased coin flip, if it satisfies some fidelity conditions. Although such a QCF satisfies the security conditions of a biased coin flip, it does not realize the ideal functionality and, therefore, does not satisfy the demands for universally composable security. Moreover, through a comparison within a small restricted bias range, we show that an arbitrary QCF is distinguishable from a black-boxed coin flip unless it is unbiased on both sides of parties against insensitive cheating. We also point out the difficulty in developing cheat-sensitive quantum bit commitment in terms of the uncomposability of a QCF.
Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambain is achieved a cheating probability of at most 3/4. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2}. Closing this gap has been one of the important open questions in quantum cryptography. In this paper, we resolve this question by presenting 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+epsilon in order to achieve a strong coin flipping protocol with cheating probability 1/sqrt{2}+O(epsilon). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon.