| Abstract |
Ben-Or and Linial (1985) introduced the full information model for coin-tossing protocols involving $n$ processors with unbounded computational power using a common broadcast channel for all their communications. For most adversarial settings, the characterization of the exact or asymptotically optimal protocols remains open. Furthermore, even for the settings where near-optimal asymptotic constructions are known, the exact constants or poly-logarithmic multiplicative factors involved are not entirely well-understood. This work studies $n$-processor coin-tossing protocols where every processor broadcasts an arbitrary-length message once. An adaptive Byzantine adversary, based on the messages broadcast so far, can corrupt $k=1$ processor. A bias-$X$ coin-tossing protocol outputs 1 with probability $X$; otherwise, it outputs 0 with probability $(1-X)$. A coin-tossing protocol's insecurity is the maximum change in the output distribution (in the statistical distance) that a Byzantine adversary can cause. Our objective is to identify bias-$X$ coin-tossing protocols achieving near-optimal minimum insecurity for every $X\in[0,1]$. Lichtenstein, Linial, and Saks (1989) studied bias-$X$ coin-tossing protocols in this adversarial model where each party broadcasts an independent and uniformly random bit. They proved that the elegant ``threshold coin-tossing protocols'' are optimal for all $n$ and $k$. Furthermore, Goldwasser, Kalai, and Park (2015), Kalai, Komargodski, and Raz (2018), and Haitner and Karidi-Heller (2020) prove that $k=\bigO{\sqrt n\cdot \polylog{n}}$ corruptions suffice to fix the output of any bias-$X$ coin-tossing protocol. These results encompass parties who send arbitrary-length messages, and each processor has multiple turns to reveal its entire message. We use an inductive approach to constructing coin-tossing protocols using a potential function as a proxy for measuring any bias-$X$ coin-tossing protocol's susceptibility to attacks in our adversarial model. Our technique is inherently constructive and yields protocols that minimize the potential function. It is incidentally the case that the threshold protocols minimize the potential function, even for arbitrary-length messages. We demonstrate that these coin-tossing protocols' insecurity is a 2-approximation of the optimal protocol in our adversarial model. For any other $X\in[0,1]$ that threshold protocols cannot realize, we prove that an appropriate (convex) combination of the threshold protocols is a 4-approximation of the optimal protocol. Finally, these results entail new (vertex) isoperimetric inequalities for density-$X$ subsets of product spaces of arbitrary-size alphabets.
|
