Optimal Bounds for Quantum Bit Commitment

DOI10.1109/FOCS.2011.42MaRDI QIDQ5495022zbMATH OpenFDO

Authors André Chailloux, Iordanis Kerenidis

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes 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/sqrt{2} [Kit03] (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important and open question. In this paper, we provide the optimal bound for quantum bit commitment. We first show a lower bound of approximately 0.739, improving Kitaev's lower bound. We then present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + eps in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(eps). We then use the optimal quantum weak coin flipping protocol described by Mochon[Moc07]. To stress the fact that our protocol uses quantum effects beyond the weak coin flip, we show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.

Cited in

(9)

• Quantum private information retrieval has linear communication complexity
• A search for quantum coin-flipping protocols using optimization techniques
• A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
• Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment
• Quantum coin hedging, and a counter measure
• Fidelity of quantum strategies with applications to cryptography
• Unconditionally secure quantum bit commitment based on the uncertainty principle
• Protocols for quantum weak coin flipping
• Quantum cryptography beyond quantum key distribution

This page was built for publication: Optimal Bounds for Quantum Bit Commitment

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