Paper 2019/774
Estimating Gaps in Martingales and Applications to CoinTossing: Constructions and Hardness
Hamidreza Amini Khorasgani, Hemanta Maji, and Tamalika Mukherjee
Abstract
Consider the representative task of designing a distributed cointossing 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 informationtheoretic setting, no adversary can deviate the probability of the outcome of the wellknown 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 discretetime 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 cointossing protocols in the informationtheoretic setting mentioned above. In particular, for any $X_0\in[0,1]$, we construct martingales that yield $\frac12\sqrt{\frac{X_0(1X_0)}{n}}$ insecure cointossing 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_\tauX_{\tau1} \right\vert] \geq \frac2{\sqrt{2n1}}\cdot X_0(1X_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_\tauX_{\tau1} \right\vert] \leq \frac1{\sqrt{n}}\cdot \sqrt{X_0(1X_0)}$$ Our lowerbound 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 stoppingtimes, we present representative applications to constructing distributed cointossing/dicerolling protocols, discrete control processes, failstop attacking cointossing/dicerolling protocols, and blackbox separations.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in TCC 2019
 Keywords
 information theoryfoundationsdistributed cryptography
 Contact author(s)

tmukherj @ purdue edu
hmaji @ purdue edu
haminikh @ purdue edu  History
 20191230: last of 4 revisions
 20190703: received
 See all versions
 Short URL
 https://ia.cr/2019/774
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/774, author = {Hamidreza Amini Khorasgani and Hemanta Maji and Tamalika Mukherjee}, title = {Estimating Gaps in Martingales and Applications to CoinTossing: Constructions and Hardness}, howpublished = {Cryptology ePrint Archive, Paper 2019/774}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/774}}, url = {https://eprint.iacr.org/2019/774} }