## 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 language | English (US) |
---|---|

Pages (from-to) | 250-259 |

Number of pages | 10 |

Journal | Proceedings of the Annual IEEE Conference on Computational Complexity |

Volume | 19 |

State | Published - 2004 |

Event | Proceedings - 19th IEEE Annual Conference on Computational Complexity - Amherst, MA, United States Duration: Jun 21 2004 → Jun 24 2004 |

## ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Computational Mathematics