Paper 2020/519

Optimally-secure Coin-tossing against a Byzantine Adversary

Hamidreza Amini Khorasgani, Hemanta K. Maji, and Mingyuan Wang

Abstract

In their seminal work, Ben-Or and Linial (1985) introduced the full information model for collective coin-tossing protocols involving $n$ processors with unbounded computational power using a common broadcast channel for all their communications. The design and analysis of coin-tossing protocols in the full information model have close connections to diverse fields like extremal graph theory, randomness extraction, cryptographic protocol design, game theory, distributed protocols, and learning theory. Several works have focused on studying the asymptotically best attacks and optimal coin-tossing protocols in various adversarial settings. While one knows the characterization of the exact or asymptotically optimal protocols in some adversarial settings, for most adversarial settings, the optimal protocol characterization remains open. For the cases where the asymptotically optimal constructions are known, the exact constants or poly-logarithmic multiplicative factors involved are not entirely well-understood. In this work, we study $n$-processor coin-tossing protocols where every processor broadcasts an arbitrary-length message once. Note that, in this setting, which processor speaks and its message distribution may depend on the messages broadcast so far. 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$; 0 with probability $(1-X)$. For a coin-tossing protocol, its insecurity is the maximum change in the output distribution (in the statistical distance) that an adversarial strategy can cause. Our objective is to identify optimal bias-$X$ coin-tossing protocols with minimum insecurity, for every $X\in[0,1]$. Lichtenstein, Linial, and Saks (1989) studied bias-$X$ coin-tossing protocols in this adversarial model under the highly restrictive constraint that each party broadcasts an independent and uniformly random bit. The underlying message space is a well-behaved product space, and $X\in[0,1]$ can only be integer multiples of $1/2^n$, which is a discrete problem. The case where every processor broadcasts only an independent random bit admits simplifications, for example, the collective coin-tossing protocol must be monotone. Surprisingly, for this class of coin-tossing protocols, the objective of reducing an adversary’s ability to increase the expected output is equivalent to reducing an adversary’s ability to decrease the expected output. Building on these observations, Lichtenstein, Linial, and Saks proved that the threshold coin-tossing protocols are optimal for all $n$ and $k$. In a sequence of works, Goldwasser, Kalai, and Park (2015), Kalai, Komargodski, and Raz (2018), and (independent of our work) Haitner and Karidi-Heller (2020) prove that $k=\mathcal{O}\left(\sqrt n\cdot \polylog{n}\right)$ corruptions suffice to fix the output of any bias-X coin-tossing protocol. These results consider parties who send arbitrary-length messages, and each processor has multiple turns to reveal its entire message. However, optimal protocols robust to a large number of corruptions do not have any apriori relation to the optimal protocol robust to $k=1$ corruption. Furthermore, to make an informed choice of employing a coin-tossing protocol in practice, for a fixed target tolerance of insecurity, one needs a precise characterization of the minimum insecurity achieved by these coin-tossing protocols. We rely on an inductive approach to constructing coin-tossing protocols to study a proxy potential function measuring the susceptibility of any bias-$X$ coin-tossing protocol to attacks in our adversarial model. Our technique is inherently constructive and yields protocols that minimize the potential function. It happens to be the case that threshold protocols minimize the potential function. We demonstrate that the insecurity of these threshold protocols is 2-approximate 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.