Limits on the security of coin flips when half the processors are faulty

TLDR

Asynchronous protocols for agreeing on an unbiased random bit are effective only when fewer than half of the processors are faulty; with half faulty, the output can be heavily biased. The authors show that these protocols are optimal, proving that no protocol can tolerate faults in at least half of the processors. The proof assumes faulty processors can privately communicate among themselves but cannot read private messages exchanged between correct processors. The result holds under very general communication models, requiring only weak probabilistic agreement among correct processors, and shows that faulty processors need minimal power.

Abstract

Protocols which allow an asynchronous network of processors to agree on a r andom (unbiased) bit are proposed in [1] and [4]. It is claimed tha t (assuming a t rapdoor funct ion exists), if less than half of the processors are faulty then the correct processors will still agree on a bit whose bias is negligibly small (when the running t ime of the processors is poly(n) the bias is smaller than O(~r) for all k). If half the processors are faulty then these protocols are no longer effective: the bits ou tpu t by the correct processors may be heavily biased. We prove tha t the above protocols are opt imal in the sense tha t no protocol exists which tolerates faults in at least half of the processors. The result is very general because few restr ict ions are made on the types of communicat ion allowed between correct processors (such as pr ivate channels and global channels) and the correct processors only need to agree on a bit in a weak probabil ist ic sense. Also, the faulty processors do not require very much power. They can privately communicate wi th each other but they cannot read messages which are exchanged pr ivately between two correct processors. An interest ing instance of the problem arises when the number of processors is fixed at two and one of t hem