A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
From MaRDI portal
Publication:2805518
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.
Recommendations
- The impossibility of efficient Quantum weak coin flipping
- A new protocol and lower bounds for quantum coin flipping
- A new protocol and lower bounds for quantum coin flipping
- Weak coin flipping in a device-independent setting
- An entanglement-based protocol for strong coin tossing with bias \(1/4\)
- Tight bounds for classical and quantum coin flipping
- scientific article; zbMATH DE number 5595865
- Quantum weak coin flipping
- A simple proof of the Kochen-Specker theorem on the problem of hidden variables
- Two simple proofs of the Kochen-Specker theorem
Cites work
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A new protocol and lower bounds for quantum coin flipping
- A quantum protocol for sampling correlated equilibria unconditionally and without a mediator
- Coin flipping by telephone a protocol for solving impossible problems
- Foundations of Cryptography
- Optimal Bounds for Quantum Bit Commitment
- Optimal Quantum Strong Coin Flipping
- Quantum bit escrow
- Quantum cryptography: public key distribution and coin tossing
- Quantum dice rolling: a multi-outcome generalization of quantum coin flipping
- Quantum leader election
- Weak coin flipping with small bias
Cited in
(8)- Weak coin flipping with small bias
- scientific article; zbMATH DE number 5595865 (Why is no real title available?)
- Quantum cryptography beyond quantum key distribution
- Quantum weak coin flipping
- Quantum leader election
- Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment
- A search for quantum coin-flipping protocols using optimization techniques
- Quantum coin hedging, and a counter measure
This page was built for publication: A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805518)
