We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of $n$ processors at most $t$ of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost $n/3$ processor failures and terminates in $t+4$ rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of $n$ processors at most $t$ of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost $n/3$ processor failures and terminates in $t+4$ rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.

IEICE Transactions on Information and SystemsJan 1, 20011 citation

Non-Interactive Protocols for Global Coin Tossing and Shared Pseudo-Random Secrets Generation

Manuel Cerecedo, Tsutomu Matsumoto, Hideki Imai

Technical report of IEICE. ISECAug 30, 19930 citations

Experimental loss-tolerant quantum coin flipping

Guido Berlín, Gilles Brassard A, Félix Bussières +3 more

Coin flipping is a cryptographic primitive in which two distrustful parties wish to generate a random bit to choose between two alternatives. This task is impossible to realize when it relies solely on the asynchronous exchange of classical bits: one dishonest player has complete control over the final outcome. It is only when coin flipping is supplemented with quantum communication that this problem can be alleviated, although partial bias remains. Unfortunately, practical systems are subject to loss of quantum data, which allows a cheater to force a bias that is complete or arbitrarily close to complete in all previous protocols and implementations. Here we report on the first experimental demonstration of a quantum coin-flipping protocol for which loss cannot be exploited to cheat better. By eliminating the problem of loss, which is unavoidable in any realistic setting, quantum coin flipping takes a significant step towards real-world applications of quantum communication. When two spatially separated parties flip a coin, it is impossible to choose between two alternatives in an unbiased manner. This study presents a quantum coin-flipping protocol that overcomes this problem and ensures a dishonest party cannot bias the outcome completely.Coin flipping is a cryptographic primitive in which two distrustful parties wish to generate a random bit to choose between two alternatives. This task is impossible to realize when it relies solely on the asynchronous exchange of classical bits: one dishonest player has complete control over the final outcome. It is only when coin flipping is supplemented with quantum communication that this problem can be alleviated, although partial bias remains. Unfortunately, practical systems are subject to loss of quantum data, which allows a cheater to force a bias that is complete or arbitrarily close to complete in all previous protocols and implementations. Here we report on the first experimental demonstration of a quantum coin-flipping protocol for which loss cannot be exploited to cheat better. By eliminating the problem of loss, which is unavoidable in any realistic setting, quantum coin flipping takes a significant step towards real-world applications of quantum communication. When two spatially separated parties flip a coin, it is impossible to choose between two alternatives in an unbiased manner. This study presents a quantum coin-flipping protocol that overcomes this problem and ensures a dishonest party cannot bias the outcome completely.

arXiv:0904.3946Nature CommunicationsNov 29, 201154 citations

We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of

n

processors at most

t

of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost

n/3

processor failures and terminates in

t+4

rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.