Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01094114
Contributor : André Chailloux <>
Submitted on : Monday, December 22, 2014 - 11:52:30 AM
Last modification on : Saturday, March 28, 2020 - 2:17:28 AM
Long-term archiving on: : Saturday, April 15, 2017 - 7:53:15 AM

File

1402.7166.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

447

Files downloads

600