A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias
arXiv:1402.7166
Abstract
Mochon's proof [Moc07] of 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 [Gan09, CK09, AS10, CK11, KZ13] 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 needed to achieve a bias and show that the number of qubits is , while the number of rounds is . 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.
arXiv comment48 pages, 5 figures. Comments are welcome
References in corpus (15)
- Unconditionally secure quantum bit commitment is impossible
- Is Quantum Bit Commitment Really Possible?
- Reexamination of Quantum Bit Commitment: the Possible and the Impossible
- Cheat Sensitive Quantum Bit Commitment
- A quantum protocol for cheat-sensitive weak coin flipping
- On bit-commitment based quantum coin flipping
- Possibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment
- Multiparty Quantum Coin Flipping
- A large family of quantum weak coin-flipping protocols
- Quantum Leader Election
- Optimal bounds for quantum bit commitment
- Optimal quantum strong coin flipping
- Quantum weak coin-flipping with bias of 0.192
- A New Protocol and Lower Bounds for Quantum Coin Flipping
- Quantum dice rolling