Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment

Abstract : Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than 1/ √ 2 [A. Kitaev, Presentation at the 6th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/ √ 2. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + ε in order to achieve a strong coin flipping protocol with cheating probability 1/ √ 2 + O(ε). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately γ ≈ 0.739, improving Kitaev’s lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to γ. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + ε in order to achieve a quantum bit commitment protocol with cheating probability γ + O(ε). To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.
Type de document :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2017, 46 (5), pp.1647--1677. 〈10.1137/15M1010853〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01650970
Contributeur : André Chailloux <>
Soumis le : mardi 28 novembre 2017 - 15:17:16
Dernière modification le : jeudi 13 décembre 2018 - 15:26:38

Identifiants

Collections

Citation

André Chailloux, Iordanis Kerenidis. Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2017, 46 (5), pp.1647--1677. 〈10.1137/15M1010853〉. 〈hal-01650970〉

Partager

Métriques

Consultations de la notice

133