Quantum weak coin flipping

DOI10.1145/3313276.3316306MaRDI QIDQ5212762zbMATH OpenOpenAlexWikidataFDO

Authors Atul Singh Arora, Jérémie Roland, Stephan Weis

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

quantum informationquantum cryptographycryptographic primitivetwo-party secure

Mathematics Subject Classification ID

Applications of game theory (91A80) Cryptography (94A60) 2-person games (91A05) Quantum cryptography (quantum-theoretic aspects) (81P94) Probabilistic games; gambling (91A60)

Abstract: 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 $epsilon$ if neither player can force the outcome towards their preferred value with probability more than $frac12+epsilon$. While it is known that all classical protocols have $epsilon=frac12$, 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.

Recommendations

• Weak coin flipping in a device-independent setting
• The impossibility of efficient Quantum weak coin flipping
• Cheat-sensitive coin flipping and quantum gambling
• Tight bounds for classical and quantum coin flipping
• A new protocol and lower bounds for quantum coin flipping
• A new protocol and lower bounds for quantum coin flipping
• scientific article; zbMATH DE number 5595865
• A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
• scientific article; zbMATH DE number 5595866
• Quantum-Secure Coin-Flipping and Applications

Cited in

(15)

• Quantum dice rolling: a multi-outcome generalization of quantum coin flipping
• Weak coin flipping with small bias
• Quantum counterfeit coin problems
• Weak coin flipping in a device-independent setting
• A new protocol and lower bounds for quantum coin flipping
• Simple, near-optimal quantum protocols for die-rolling
• Dilemma that cannot be resolved by biased quantum coin flipping
• Cheat-sensitive coin flipping and quantum gambling
• Protocols for quantum weak coin flipping
• An entanglement-based protocol for strong coin tossing with bias \(1/4\)
• A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
• Semi-loss-tolerant strong coin flipping protocol using EPR pairs
• A new protocol and lower bounds for quantum coin flipping
• Tight bounds for classical and quantum coin flipping
• scientific article; zbMATH DE number 5595865 (Why is no real title available?)

This page was built for publication: Quantum weak coin flipping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212762)