loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
Multiparty Quantum Coin Flipping
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig, "Multiparty Quantum Coin Flipping," Computational Complexity, Annual IEEE Conference on, pp. 250-259, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313848,
author = {Andris Ambainis and Harry Buhrman and Yevgeniy Dodis and Hein Röhrig},
title = {Multiparty Quantum Coin Flipping},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {250-259},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313848},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Multiparty Quantum Coin Flipping
SN - 1093-0159
SP250
EP259
A1 - Andris Ambainis,
A1 - Harry Buhrman,
A1 - Yevgeniy Dodis,
A1 - Hein Röhrig,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Andris Ambainis, IAS and U. of Latvia
Harry Buhrman, CWI and U. of Amsterdam
Yevgeniy Dodis, New York University
Hein Röhrig, U. of Calgary

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 \varepsilon of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1 \le g \le k,\varepsilon = \frac{1}{2} - \Theta (\frac{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 \le \frac{k}{2}.

    Citation:
    Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig, "Multiparty Quantum Coin Flipping," ccc, pp.250-259, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.