Multiparty quantum coin flipping

Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig

Research output: Contribution to journalConference articlepeer-review

Abstract

We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: We propose and motivate a definition for quantum broadcast. Our model of quantum broadcast channel is new. We discovered that quantum broadcast is essentially a combination of pairwise quantum channels and a classical broadcast channel. This is a somewhat surprising conclusion, but helps us in both our lower and upper bounds. We provide tight upper and lower bounds on the optimal bias ε of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1≤g≤k,ε=1/2-⊖(g/k). Thus, as long as a constant fraction of the players are honest, they can prevent the coin from being fixed with at least a constant probability. This result stands in sharp contrast with the classical setting, where no non-trivial coin-flipping is possible when g ≤ k/2.

Original languageEnglish (US)
Pages (from-to)250-259
Number of pages10
JournalProceedings of the Annual IEEE Conference on Computational Complexity
Volume19
StatePublished - 2004
EventProceedings - 19th IEEE Annual Conference on Computational Complexity - Amherst, MA, United States
Duration: Jun 21 2004Jun 24 2004

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Multiparty quantum coin flipping'. Together they form a unique fingerprint.

Cite this