科研之友
微信
新浪微博
Facebook
分享链接
摘要
In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364-369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any m-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by Omega(1/m). For more than two decades the best known coin-flipping protocols against dishonest majority had bias Theta(l/root m) where l is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1-18], who constructed an m-round, two-party coin-flipping protocol with optimal bias Theta(1/m). In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503-513] extended this result to the multiparty case in which less than 2/3 of the parties can be corrupted. Still, for the case of 2/3(or more) corrupted parties, the best known protocol had bias Theta(l/root m). In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an m-round, three-party coin-flipping protocol, with bias O(log(3)m)/m). Our approach (which we also apply to the two-party case) does not follow the "threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned Theta(l/root m)-bias protocol.
- 出版日期2017
