Optimal Quantum Strong Coin Flipping

DOI10.1109/FOCS.2009.71MaRDI QIDQ5171218zbMATH OpenFDO

Authors André Chailloux, Iordanis Kerenidis

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Cryptography (94A60) Quantum cryptography (quantum-theoretic aspects) (81P94)

Abstract: Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit [Blu81]. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4 [Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than $1/sqrt2$ [Kit03]. 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/sqrt2$. 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/sqrt2+O(epsilon)$. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon [Moc07].

Cited in

(14)

• Quantum coin hedging, and a counter measure
• A search for quantum coin-flipping protocols using optimization techniques
• Unconditionally secure relativistic multi-party biased coin flipping and die rolling
• Secure certification of mixed quantum states with application to two-party randomness generation
• Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment
• Preface
• Fidelity of quantum strategies with applications to cryptography
• Preface
• Semi-loss-tolerant strong quantum coin-flipping protocol using quantum non-demolition measurement
• Protocols for quantum weak coin flipping
• A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
• Quantum cryptography beyond quantum key distribution
• Quantum leader election
• Quantum cryptography: key distribution and beyond

This page was built for publication: Optimal Quantum Strong Coin Flipping

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