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:1901.04876 · Physical Review Research

Impossibility of coin flipping in generalized probabilistic theories via discretizations of semi-infinite programs

Jamie Sikora, John H. Selby

Published Oct 23, 2020• 11 citations
arXivHTMLPDF

Abstract

Coin flipping is a fundamental cryptographic task where spatially separated Alice and Bob wish to generate a fair coin flip over a communication channel.It is known that ideal coin flipping is impossible in both classical and quantum theory.In this work, we give a short proof that it is also impossible in generalized probabilistic theories under the generalized no-restriction hypothesis.Our proof relies crucially on a formulation of cheating strategies as semi-infinite programs, i.e., cone programs with infinitely many constraints.This introduces a formalism which may be of independent interest to the quantum community.

DOI
10.1103/physrevresearch.2.043128

Related papers

Simple proof of the impossibility of bit commitment in generalized probabilistic theories using cone programming

Jamie Sikora, John H. Selby

Bit commitment is a fundamental cryptographic task, in which Alice commits a bit to Bob such that she cannot later change the value of the bit, while, simultaneously, the bit is hidden from Bob. It is known that ideal bit commitment is impossible within quantum theory. In this work, we show that it is also impossible in generalized probabilistic theories (under a small set of assumptions) by presenting a quantitative trade-off between Alice's and Bob's cheating probabilities. Our proof relies crucially on a formulation of cheating strategies as cone programs, a natural generalization of semidefinite programs. In fact, using the generality of this technique, we prove that this result holds for the more general task of integer commitment.

arXiv:1711.02662•Physical Review A•Apr 3, 2018•18 citations

Fair loss-tolerant quantum coin flipping

Guido Berlín, Gilles Brassard A, Félix Bussières +1 more

Coin flipping is a cryptographic primitive in which two spatially separated players, who do not trust each other, wish to establish a common random bit. If we limit ourselves to classical communication, this task requires either assumptions on the computational power of the players or it requires them to send messages to each other with sufficient simultaneity to force their complete independence. Without such assumptions, all classical protocols are so that one dishonest player has complete control over the outcome. If we use quantum communication, on the other hand, protocols have been introduced that limit the maximal bias that dishonest players can produce. However, those protocols would be very difficult to implement in practice because they are susceptible to realistic losses on the quantum channel between the players or in their quantum memory and measurement apparatus. In this paper, we introduce a quantum protocol and we prove that it is completely impervious to loss. The protocol is fair in the sense that either player has the same probability of success in cheating attempts at biasing the outcome of the coin flip. We also give explicit and optimal cheating strategies for both players.

arXiv:0904.3945•Physical Review A•Dec 10, 2009•37 citations

Quantum and classical coin-flipping protocols based on bit-commitment and their point games

Ashwin Nayak, Jamie Sikora, Levent Tunçel

We focus on a family of quantum coin-flipping protocols based on bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. We then use these simplifications to construct their point games as developed by Kitaev. We also study the classical version of these protocols and use linear optimization to formulate optimal cheating strategies. We then construct the point games for the classical protocols as well using the analysis for the quantum case. We discuss the philosophical connections between the classical and quantum protocols and their point games as viewed from optimization theory. In particular, we observe an analogy between a spectrum of physical theories (from classical to quantum) and a spectrum of convex optimization problems (from linear programming to semidefinite programming, through second-order cone programming). In this analogy, classical systems correspond to linear programming problems and the level of quantum features in the system is correlated to the level of sophistication of the semidefinite programming models on the optimization side. Concerning security analysis, we use the classical point games to prove that every classical protocol of this type allows exactly one of the parties to entirely determine the coin-flip. Using the relationships between the quantum and classical protocols, we show that only "classical" protocols can saturate Kitaev's lower bound for strong coin-flipping. Moreover, if the product of Alice and Bob's optimal cheating probabilities is 1/2, then one party can cheat with probability 1. This rules out quantum protocols of this type from attaining the optimal level of security.

arXiv:1504.04217•Apr 16, 2015•1 citation

Experimental loss-tolerant quantum coin flipping

Guido Berlín, Gilles Brassard A, Félix Bussières +3 more

Coin flipping is a cryptographic primitive in which two distrustful parties wish to generate a random bit to choose between two alternatives. This task is impossible to realize when it relies solely on the asynchronous exchange of classical bits: one dishonest player has complete control over the final outcome. It is only when coin flipping is supplemented with quantum communication that this problem can be alleviated, although partial bias remains. Unfortunately, practical systems are subject to loss of quantum data, which allows a cheater to force a bias that is complete or arbitrarily close to complete in all previous protocols and implementations. Here we report on the first experimental demonstration of a quantum coin-flipping protocol for which loss cannot be exploited to cheat better. By eliminating the problem of loss, which is unavoidable in any realistic setting, quantum coin flipping takes a significant step towards real-world applications of quantum communication. When two spatially separated parties flip a coin, it is impossible to choose between two alternatives in an unbiased manner. This study presents a quantum coin-flipping protocol that overcomes this problem and ensures a dishonest party cannot bias the outcome completely.

arXiv:0904.3946•Nature Communications•Nov 29, 2011•54 citations

Quantum Coin Flipping: and Circuit Design Problems in Distributed Quantum Computing

Roy van Houte

Quantum coin flipping is a cryptographic primitive in which two or more parties that do not trust each other want establish a fair coin flip. These parties are not physically near each other and use quantum communication channels to interact. A quality of protocols is measured by the best possible cheating strategy, which is the solution of a complex semidefinite optimization problem. In this master thesis we show new explicit bounds in multiparty quantum coin flipping, we investigate how to explicitly formulate these problem in a standard form, we show that a fair coin flip results in the lowest possible bias and we determine more measures of the quality of a protocol. Furthermore, this master thesis presents a rigorous and detailed mathematical description of semidefinite optimization, quantum information theory and quantum coin flipping. This thesis also includes an article written together with J. Mulderij, T. Attema, I. Chiscop and F. Phillipson on distributed quantum computing. In this article, we pose new questions and formulate integer linear programs that solve to find optimal assignment of qubits to computers for a given network of quantum computers and quantum algorithm.

•Jan 1, 2020•1 citation

A Fair Loss-Tolerant Quantum Coin Flipping Protocol

Guido Berlín, Gilles Brassard A, Félix Bussières +2 more

Coin flipping is a cryptographic primitive in which two spatially separated players, who in principle do not trust each other, wish to agree on a random bit. Classical and quantum coin flipping protocols have been studied extensively for more than twenty‐five years. However, until recently, quantum coin flipping protocols were designed without taking into consideration the losses of quantum information that would be unavoidable in any realistic implementation. We introduced in 2008 a novel protocol and proved its security even when losses are taken into account: no cheating player could obtain a desired outcome with a probability greater than (6+2)/8≈93%. Here, we refine our earlier protocol by making it fair in the sense that the optimal cheating strategies allow either player to bias the outcome by the same amount. Specifically, either player can cheat to obtain a desired outcome with probability exactly 90%, but no more. An implementation is underway.

AIP conference proceedings•Jan 1, 2009•1 citation
Coin flipping is a fundamental cryptographic task where spatially separated Alice and Bob wish to generate a fair coin flip over a communication channel.It is known that ideal coin flipping is impossible in both classical and quantum theory.In this work, we give a short proof that it is also impossible in generalized probabilistic theories under the generalized no-restriction hypothesis.Our proof relies crucially on a formulation of cheating strategies as semi-infinite programs, i.e., cone programs with infinitely many constraints.This introduces a formalism which may be of independent interest to the quantum community.
Bit commitment is a fundamental cryptographic task, in which Alice commits a bit to Bob such that she cannot later change the value of the bit, while, simultaneously, the bit is hidden from Bob. It is known that ideal bit commitment is impossible within quantum theory. In this work, we show that it is also impossible in generalized probabilistic theories (under a small set of assumptions) by presenting a quantitative trade-off between Alice's and Bob's cheating probabilities. Our proof relies crucially on a formulation of cheating strategies as cone programs, a natural generalization of semidefinite programs. In fact, using the generality of this technique, we prove that this result holds for the more general task of integer commitment.
Coin flipping is a cryptographic primitive in which two spatially separated players, who do not trust each other, wish to establish a common random bit. If we limit ourselves to classical communication, this task requires either assumptions on the computational power of the players or it requires them to send messages to each other with sufficient simultaneity to force their complete independence. Without such assumptions, all classical protocols are so that one dishonest player has complete control over the outcome. If we use quantum communication, on the other hand, protocols have been introduced that limit the maximal bias that dishonest players can produce. However, those protocols would be very difficult to implement in practice because they are susceptible to realistic losses on the quantum channel between the players or in their quantum memory and measurement apparatus. In this paper, we introduce a quantum protocol and we prove that it is completely impervious to loss. The protocol is fair in the sense that either player has the same probability of success in cheating attempts at biasing the outcome of the coin flip. We also give explicit and optimal cheating strategies for both players.
We focus on a family of quantum coin-flipping protocols based on bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. We then use these simplifications to construct their point games as developed by Kitaev. We also study the classical version of these protocols and use linear optimization to formulate optimal cheating strategies. We then construct the point games for the classical protocols as well using the analysis for the quantum case. We discuss the philosophical connections between the classical and quantum protocols and their point games as viewed from optimization theory. In particular, we observe an analogy between a spectrum of physical theories (from classical to quantum) and a spectrum of convex optimization problems (from linear programming to semidefinite programming, through second-order cone programming). In this analogy, classical systems correspond to linear programming problems and the level of quantum features in the system is correlated to the level of sophistication of the semidefinite programming models on the optimization side. Concerning security analysis, we use the classical point games to prove that every classical protocol of this type allows exactly one of the parties to entirely determine the coin-flip. Using the relationships between the quantum and classical protocols, we show that only "classical" protocols can saturate Kitaev's lower bound for strong coin-flipping. Moreover, if the product of Alice and Bob's optimal cheating probabilities is 1/2, then one party can cheat with probability 1. This rules out quantum protocols of this type from attaining the optimal level of security.
Coin flipping is a cryptographic primitive in which two distrustful parties wish to generate a random bit to choose between two alternatives. This task is impossible to realize when it relies solely on the asynchronous exchange of classical bits: one dishonest player has complete control over the final outcome. It is only when coin flipping is supplemented with quantum communication that this problem can be alleviated, although partial bias remains. Unfortunately, practical systems are subject to loss of quantum data, which allows a cheater to force a bias that is complete or arbitrarily close to complete in all previous protocols and implementations. Here we report on the first experimental demonstration of a quantum coin-flipping protocol for which loss cannot be exploited to cheat better. By eliminating the problem of loss, which is unavoidable in any realistic setting, quantum coin flipping takes a significant step towards real-world applications of quantum communication. When two spatially separated parties flip a coin, it is impossible to choose between two alternatives in an unbiased manner. This study presents a quantum coin-flipping protocol that overcomes this problem and ensures a dishonest party cannot bias the outcome completely.
Quantum coin flipping is a cryptographic primitive in which two or more parties that do not trust each other want establish a fair coin flip. These parties are not physically near each other and use quantum communication channels to interact. A quality of protocols is measured by the best possible cheating strategy, which is the solution of a complex semidefinite optimization problem. In this master thesis we show new explicit bounds in multiparty quantum coin flipping, we investigate how to explicitly formulate these problem in a standard form, we show that a fair coin flip results in the lowest possible bias and we determine more measures of the quality of a protocol. Furthermore, this master thesis presents a rigorous and detailed mathematical description of semidefinite optimization, quantum information theory and quantum coin flipping. This thesis also includes an article written together with J. Mulderij, T. Attema, I. Chiscop and F. Phillipson on distributed quantum computing. In this article, we pose new questions and formulate integer linear programs that solve to find optimal assignment of qubits to computers for a given network of quantum computers and quantum algorithm.
Coin flipping is a cryptographic primitive in which two spatially separated players, who in principle do not trust each other, wish to agree on a random bit. Classical and quantum coin flipping protocols have been studied extensively for more than twenty‐five years. However, until recently, quantum coin flipping protocols were designed without taking into consideration the losses of quantum information that would be unavoidable in any realistic implementation. We introduced in 2008 a novel protocol and proved its security even when losses are taken into account: no cheating player could obtain a desired outcome with a probability greater than (6+2)/8≈93%. Here, we refine our earlier protocol by making it fair in the sense that the optimal cheating strategies allow either player to bias the outcome by the same amount. Specifically, either player can cheat to obtain a desired outcome with probability exactly 90%, but no more. An implementation is underway.