Paper 2019/774

Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness

Hamidreza Amini Khorasgani and Hemanta Maji and Tamalika Mukherjee

Abstract

Consider the representative task of designing a distributed coin-tossing protocol for $n$ processors such that the probability of heads is $X_0\in[0,1]$, and an adversary can reset one processor to change the distribution of the final outcome. For $X_0=1/2$, in the non-cryptographic setting, no adversary can deviate the probability of the outcome of the well-known Blum's ``majority protocol'' by more than $\frac1{\sqrt{2\pi n}}$, i.e., it is $\frac1{\sqrt{2\pi n}}$ insecure. For computationally bounded adversaries and any $X_0\in[0,1]$, the protocol of Moran, Naor, and Segev (2009) is only $O\left(\frac1n\right)$ insecure. In this paper, we study discrete-time martingales $(X_0,X_1,\dotsc,X_n)$ such that $X_i\in[0,1]$, for all $i\in\{0,\dotsc,n\}$, and $X_n\in \{0,1\}$. These martingales are commonplace in modeling stochastic processes like coin-tossing protocols in the non-cryptographic setting mentioned above. In particular, for any $X_0\in[0,1]$, we construct martingales that yield $\frac12\sqrt{\frac{X_0(1-X_0)}{n}}$ insecure coin-tossing protocols with $n$-bit communication; irrespective of the number of bits required to represent the output distribution. Note that for sufficiently small $X_0$, we achieve higher security than Moran et al.'s protocol even against computationally unbounded adversaries. For $X_0=1/2$, our protocol requires only 40 percent of the processors to achieve the same security as the majority protocol. The technical heart of our paper is a new inductive technique that uses geometric transformations to precisely account for the large gaps in these martingales. For any $X_0\in[0,1]$, we show that there exists a stopping time $\tau$ such that $$E\left[{|{X_\tau-X_{\tau-1}}|}\right]\geq \frac2{\sqrt{2n-1}}\cdot X_0(1-X_0)$$ The inductive technique simultaneously constructs martingales that demonstrate the optimality of our bound, \ie, a martingale where the gap corresponding to any stopping time is small. In particular, we construct optimal martingales such that any stopping time $\tau$ has $$E\left[{|{X_\tau-X_{\tau-1}}|}\right]\leq \frac1{\sqrt{n}}\cdot \sqrt{X_0(1-X_0)}$$ Our lower-bound holds for all $X_0\in[0,1]$; while the previous bound of Cleve and Impagliazzo (1993) exists only for positive constant $X_0$. Conceptually, our approach only employs elementary techniques to analyze these martingales and entirely circumvents the complex probabilistic tools inherent to the approaches of Cleve and Impagliazzo (1993) and Beimel, Haitner, Makriyannis, and Omri (2018). By appropriately restricting the set of possible stopping-times, we present representative applications to constructing distributed coin-tossing/dice-rolling protocols, discrete control processes, fail-stop attacking coin-tossing/dice-rolling protocols, and black-box separations.