| Paper ID | D6-S6-T4.1 |
| Paper Title |
Efficient Distributed Coin-tossing Protocols |
| Authors |
Hamidreza Amini Khorasgani, Hemanta K. Maji, Himanshi Mehta, Mingyuan Wang, Purdue University, United States |
| Session |
D6-S6-T4: Byzantine Adversaries |
| Chaired Session: |
Monday, 19 July, 23:40 - 00:00 |
| Engagement Session: |
Tuesday, 20 July, 00:00 - 00:20 |
| 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. 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 an adversary can cause. This work considers an adversary who monitors the protocol's communication and intervenes at most once by restarting the processor who just broadcast her message. For a given tolerance $\eps$, our objective is to use the minimum number of processors, ensuring that this adversary can only change the output distribution by at most $\eps$. Historically, the ``threshold coin-tossing protocols'' have been optimal or asymptotically optimal against various adversary models. However, for our model, Khorasgani, Maji, and Mukherjee (2019) prove the existence of coin-tossing protocols that achieve the same tolerance as the threshold protocols using a smaller number of processors. Unfortunately, their protocol is not computationally efficient. Towards this objective, for any $X\in(0,1)$ and $n\in\NN$, this paper presents computationally efficient coin-tossing protocols approximating the new protocols of Khorasgani, Maji, and Mukherjee (2019). This protocol's running time is linear in the inverse of the accuracy parameter of this approximation, which can be set arbitrarily small.
|
