Paper 2020/519
Optimallysecure Cointossing against a Byzantine Adversary
Hamidreza Amini Khorasgani, Hemanta K. Maji, and Mingyuan Wang
Abstract
In their seminal work, BenOr and Linial (1985) introduced the full information model for collective cointossing protocols involving $n$ processors with unbounded computational power using a common broadcast channel for all their communications. The design and analysis of cointossing 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 cointossing 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 polylogarithmic multiplicative factors involved are not entirely wellunderstood. In this work, we study $n$processor cointossing protocols where every processor broadcasts an arbitrarylength 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$ cointossing protocol outputs 1 with probability $X$; 0 with probability $(1X)$. For a cointossing 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$ cointossing protocols with minimum insecurity, for every $X\in[0,1]$. Lichtenstein, Linial, and Saks (1989) studied bias$X$ cointossing 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 wellbehaved 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 cointossing protocol must be monotone. Surprisingly, for this class of cointossing 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 cointossing 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 KaridiHeller (2020) prove that $k=\mathcal{O}\left(\sqrt n\cdot \polylog{n}\right)$ corruptions suffice to fix the output of any biasX cointossing protocol. These results consider parties who send arbitrarylength 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 cointossing protocol in practice, for a fixed target tolerance of insecurity, one needs a precise characterization of the minimum insecurity achieved by these cointossing protocols. We rely on an inductive approach to constructing cointossing protocols to study a proxy potential function measuring the susceptibility of any bias$X$ cointossing 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 2approximate 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 4approximation of the optimal protocol.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 MultipartyCointossingAdaptive AdversariesOptimal ProtocolsIsoperimetric Inequalities
 Contact author(s)

haminikh @ purdue edu
hmaji @ purdue edu
wang1929 @ purdue edu  History
 20210202: last of 2 revisions
 20200505: received
 See all versions
 Short URL
 https://ia.cr/2020/519
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/519, author = {Hamidreza Amini Khorasgani and Hemanta K. Maji and Mingyuan Wang}, title = {Optimallysecure Cointossing against a Byzantine Adversary}, howpublished = {Cryptology ePrint Archive, Paper 2020/519}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/519}}, url = {https://eprint.iacr.org/2020/519} }