For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Unbiased Global Coin Flipping Protocol on Synchronous Distributed Systems
Kunikazu YODA Yasuo OKABE Masanori KANAZAWA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/01/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
distributed protocol, global coin flipping, synchronous distributed system, adversary,
Full Text: PDF(390KB)>>
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 manipulated by a malicious adversary, and 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 the adversary 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, which we use as the base of our protocol. 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 slight expense of running time, which is only added just two rounds.