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

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.
Type de document :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2016, pp.48. 〈10.1137/14096387X〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094114
Contributeur : André Chailloux <>
Soumis le : lundi 22 décembre 2014 - 11:52:30
Dernière modification le : mardi 17 avril 2018 - 11:34:41
Document(s) archivé(s) le : samedi 15 avril 2017 - 07:53:15

Fichier

1402.7166.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, Lock Magnin. A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2016, pp.48. 〈10.1137/14096387X〉. 〈hal-01094114〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

132