The problem of quantum dice rolling (DR)—a generalization of the problem of quantum coin flipping (CF) to more than two outcomes and parties—is studied in both its weak and strong variants. We prove by construction that quantum mechanics allows for (i) weak N -sided DR admitting arbitrarily small bias for any N and (ii) two-party strong N -sided DR saturating Kitaev's bound for any N . To derive (ii) we also prove by construction that quantum mechanics allows for (iii) strong imbalanced CF saturating Kitaev's bound for any degree of imbalance. Furthermore, as a corollary of (ii) we introduce a family of optimal 2 m -party strong n m -sided DR protocols for any pair m and n .
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.
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
ε and show that the number of qubits is
O(logε1), while the number of rounds is
(ε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.
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.
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
21+ϵ. While it is known that all classical protocols have
ϵ=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/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.
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.