Paper 2021/1464
Polynomialtime targeted attacks on coin tossing for any number of corruptions
Omid Etesami, Ji Gao, Saeed Mahloujifar, and Mohammad Mahmoody
Abstract
Consider an $n$message cointossing protocol between $n$ parties $P_1,\dots,P_n$, in which $P_i$ broadcasts a single message $w_i$ in round $i$ (possibly based on the previously shared messages) and at the end they agree on bit $b$. A $k$replacing adversary $A_k$ can change up to $k$ of the messages as follows. In every round $i$, the adversary who knows all the messages broadcast so far, as well as a message $w_i$ that is prepared by $P_i$ to be just sent, can can to replace the prepared message $w_i$ with its own choice. A targeted adversary prefers the outcome $b'=1$, and its bias is defined as $\mu'\mu$, where $\mu'=\Pr[b'=1]$ (resp. $\Pr[b=1]=\mu$) refers to the probability of outputting $1$ when the attack happens (resp. does not happen). In this work, we study $k$replacing targeted attacks, their computational efficiency, and optimality, for all $k \in [n]$. Large messages: When the messages are allowed to be arbitrarily long, we show that polynomialtime $k$replacing targeted attacks can achieve bias $\Omega(\mu k/\sqrt n)$ for any $k$ (and any protocol), which is optimal up to a constant factor for any $\mu = \Theta(1)$. Previously, it was known how to achieve such bias only for $k = \Omega(\sqrt n)$ (KomargodskiRaz [DISC'18], MahloujifarMahmoody [ALT'19], and EtesamiMahloujifarMahmoody [SODA'20]). This proves a computational variant of the isoperimetric inequality for product spaces under $k=o(\sqrt n)$ Hamming distance. As a corollary, we also obtain improved $poly(n)$time targeted poisoning attacks on deterministic learners, in which the adversary can increase the probability of any efficiently testable bad event over the produced model from $\mu=1/poly(n)$ to $\mu + \Omega(\mu k /\sqrt n)$ by changing $k$ out of $n$ training examples. Binary messages: When the messages $w_1,\dots,w_n$ are uniformly random bits, we show that if $\mu=\Pr[b=1]= \Pr[\sum w_i \geq t] = \beta^{(t)}_n$ for $t \in [n]$ is the probability of falling into a Hamming ball, then polynomialtime $k$replacing targeted attacks can achieve $\mu'=\Pr[b'=1]=\beta^{(tk)}_n $, which is optimal due to the simple majority protocol. Thus, as corollary we obtain an alternative proof of the Harper's celebrated vertex isoperimetric inequality in which the optimal adversary (that maps random points to a set of measure $\mu$ by changing at most $k$ bits) is limited to be online and run in polynomial time. Previously, Lichtenstein, Linial, and Saks [Combinatorica'89] showed how to achieve $\mu'=\Pr[b'=1] = \beta^{(tk)}_{ nk }$ (using computationally unbounded attacks), which is optimal for adaptive adversaries who decide on corrupting parties before seeing their messages.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in TCC 2021
 Keywords
 Coin tossing attacksdata poisoningisoperimetric inequality
 Contact author(s)

jg6yd @ virginia edu
mohammad @ virginia edu
sfar @ princeton edu
etesami @ gmail com  History
 20211106: received
 Short URL
 https://ia.cr/2021/1464
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1464, author = {Omid Etesami and Ji Gao and Saeed Mahloujifar and Mohammad Mahmoody}, title = {Polynomialtime targeted attacks on coin tossing for any number of corruptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1464}, year = {2021}, url = {https://eprint.iacr.org/2021/1464} }