A Lower Bound for Adaptively-Secure Collective Coin Flipping Protocols
- PDF / 512,534 Bytes
- 25 Pages / 442.205 x 665.008 pts Page_size
- 9 Downloads / 197 Views
Bolyai Society – Springer-Verlag
Combinatorica 25pp. DOI: 10.1007/s00493-020-4147-4
A LOWER BOUND FOR ADAPTIVELY-SECURE COLLECTIVE COIN FLIPPING PROTOCOLS YAEL TAUMAN KALAI, ILAN KOMARGODSKI*, RAN RAZ† Received January 31, 2019 Revised March 26, 2020 In 1985, Ben-Or and Linial (Advances in Computing Research 1989) introduced the collective coin flipping problem, where n parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party in the course of the protocol as a function of the messages seen so far. They showed that the majority protocol, in which each player sends a random bit and the output is the majority value, tolerates √ O( n) adaptive corruptions. They conjectured that this is optimal for such adversaries. We prove that the majority protocol is optimal (up to a poly-logarithmic factor) among all protocols in which each party sends a single, possibly long, message. Previously, such a lower bound was known for protocols in which parties are allowed to send only a single bit (Lichtenstein, Linial, and Saks, Combinatorica 1989), or for symmetric protocols (Goldwasser, Kalai, and Park, ICALP 2015).
1. Introduction In the collective coin flipping problem, introduced by Ben-Or and Linial [9], a set of n computationally unbounded parties, each equipped with a private source of randomness, are required to generate a common random bit. The communication model is the “full information” model [9], where all parties communicate via a single broadcast channel. The goal of the parties is to agree on a common random bit even in the case that some t = t(n) of Mathematics Subject Classification (2010): 68Q01, 68Q17, 68Q25 Part of this work done at MSR New England and Cornell Tech. † Research supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation grants No. CCF-1714779 and CCF-1412958. ∗
2
YAEL TAUMAN KALAI, ILAN KOMARGODSKI, RAN RAZ
the parties are faulty and controlled by an adversary whose goal is to bias the output of the protocol in some direction. We say that a protocol Π is resilient (or secure) to t corruptions if for any adversary A that makes at most t corruptions it holds that n o min Pr [Output of A(Π) = 0] , Pr [Output of A(Π) = 1] ≥ Ω(1), where “Output of A(Π)” is a random variable that corresponds to the output of the protocol Π when executed in the presence of the adversary A.1 The adversary is Byzantine, namely, once it corrupts a party, it completely controls it and can send arbitrary messages on its behalf. Usually, two types of Byzantine adversaries are considered, static or adaptive ones. A static adversary is an adversary that chooses which parties to corrupt ahead of time, before the protocol begins. An adaptive adversary, on the other hand, is allowed to choose which parties to corrupt adaptively in the course of the protocol as a function of the messages seen so far. In the case of static adversaries, colle
Data Loading...
