Multiparty quantum coin flipping
Authors:
- H. BuhrmanHBH. Buhrman
- Y. DodisYDY. Dodis
- H. RohrigHRH. Rohrig
- 14 April 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10930159,p. 250-259
Abstract
We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) we propose and motivate a definition for quantum broadcast. Our model of quantum broadcast channel is new. (2) 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. (3) We provide tight upper and lower bounds on the optimal bias /spl epsiv/ of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1 /spl les/ g /spl les/ k, /spl epsiv/ = 1/2 - /spl Theta/ (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 /spl les/ k/2.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Quantum Weak Coin-Flipping with Bias of 0.1922004
- Quantum Protocol for Cheat-Sensitive Weak Coin FlippingPhysical Review Letters, 2002
- A new protocol and lower bounds for quantum coin flipping2001
- Quantum bit escrow2000
- Demonstrating the viability of universal quantum computation using teleportation and single-qubit operationsNature, 1999
- Quantum circuits with mixed states1998
- Noncommuting Mixed States Cannot Be BroadcastPhysical Review Letters, 1996
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channelsPhysical Review Letters, 1993
- A Robust Noncryptographic Protocol for Collective Coin FlippingSIAM Journal on Discrete Mathematics, 1989
- A single quantum cannot be clonedNature, 1982