Welcome to the resource topic for 2019/774
Title:
Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness
Authors: Hamidreza Amini Khorasgani, Hemanta Maji, 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]. This protocol should be robust to an adversary who can reset one processor to change the distribution of the final outcome. For X_0=1/2, in the information-theoretic 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. 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 information-theoretic 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. For X_0=1/2, our protocol requires only 40% 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 $$\mathbb{E}[\left\vert X_\tau-X_{\tau-1} \right\vert] \geq \frac2{\sqrt{2n-1}}\cdot X_0(1-X_0)$$ The inductive technique simultaneously constructs martingales that demonstrate the optimality of our bound, i.e., a martingale where the gap corresponding to any stopping time is small. In particular, we construct optimal martingales such that \textit{ any} stopping time \tau has $$\mathbb{E}[\left\vert X_\tau-X_{\tau-1} \right\vert] \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.
ePrint: https://eprint.iacr.org/2019/774
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .