A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias

DOI10.1137/14096387XzbMATH Open1342.81096arXiv1402.7166MaRDI QIDQ2805518FDOQ2805518

Authors: Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, Loïck Magnin 

Publication date: 12 May 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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 $epsilon$ and show that the number of qubits is $O(log1/epsilon)$, while the number of rounds is $(1/epsilon{)}^{O(1/epsilon)}$. 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.

Full work available at URL: https://arxiv.org/abs/1402.7166

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
• 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

zbMATH Keywords

quantum cryptographysecurityquantum protocolsquantum weak coin flipping

Mathematics Subject Classification ID

Cryptography (94A60) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cites Work

• Title not available (Why is that?)
• Quantum cryptography: public key distribution and coin tossing
• Weak coin flipping with small bias
• Quantum bit escrow
• Optimal Quantum Strong Coin Flipping
• Optimal Bounds for Quantum Bit Commitment
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Foundations of Cryptography
• A new protocol and lower bounds for quantum coin flipping
• Coin flipping by telephone a protocol for solving impossible problems
• Quantum dice rolling: a multi-outcome generalization of quantum coin flipping
• A quantum protocol for sampling correlated equilibria unconditionally and without a mediator
• Quantum leader election

Cited In (8)

• Quantum coin hedging, and a counter measure
• A search for quantum coin-flipping protocols using optimization techniques
• Quantum weak coin flipping
• Weak coin flipping with small bias
• Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment
• Quantum cryptography beyond quantum key distribution
• Quantum leader election
• Title not available (Why is that?)

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)