dorsal/arxiv
View SchemaMultiparty Quantum Coin Flipping
| Authors | Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Roehrig |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0304112 |
| URL | https://arxiv.org/abs/quant-ph/0304112 |
| DOI | 10.1109/CCC.2004.1313848 |
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 epsilon of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1 <= g <= k, epsilon = 1/2 - 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 <= k/2.
{
"annotation_id": "98c9fe6c-c38a-4b0e-9228-37134f317a12",
"date_created": "2026-03-02T18:02:00.268000Z",
"date_modified": "2026-03-02T18:02:00.268000Z",
"file_hash": "5a703636fa7fa193f09effe49c82ef9dea19757d04c295e14fe30c07315075c9",
"private": false,
"record": {
"abstract": "We investigate coin-flipping protocols for multiple parties in a quantum\nbroadcast setting:\n (1) We propose and motivate a definition for quantum broadcast. Our model of\nquantum broadcast channel is new.\n (2) We discovered that quantum broadcast is essentially a combination of\npairwise quantum channels and a classical broadcast channel. This is a somewhat\nsurprising conclusion, but helps us in both our lower and upper bounds.\n (3) We provide tight upper and lower bounds on the optimal bias epsilon of a\ncoin which can be flipped by k parties of which exactly g parties are honest:\nfor any 1 \u003c= g \u003c= k, epsilon = 1/2 - Theta(g/k).\n Thus, as long as a constant fraction of the players are honest, they can\nprevent the coin from being fixed with at least a constant probability. This\nresult stands in sharp contrast with the classical setting, where no\nnon-trivial coin-flipping is possible when g \u003c= k/2.",
"arxiv_id": "quant-ph/0304112",
"authors": [
"Andris Ambainis",
"Harry Buhrman",
"Yevgeniy Dodis",
"Hein Roehrig"
],
"categories": [
"quant-ph",
"cs.CR",
"cs.DC"
],
"doi": "10.1109/CCC.2004.1313848",
"title": "Multiparty Quantum Coin Flipping",
"url": "https://arxiv.org/abs/quant-ph/0304112"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "19130da1-09bd-4937-a873-f4778e64d270",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}