An Unbiased Global Coin Flipping Protocol on Synchronous Distributed Systems
Kunikazu Yoda, Yasuo Okabe, Masanori Kanazawa · Kyoto University Research Information Repository (Kyoto University) · 2001
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.