Paper 2021/1464

Polynomial-time targeted attacks on coin tossing for any number of corruptions

Omid Etesami, Ji Gao, Saeed Mahloujifar, and Mohammad Mahmoody

Abstract

Consider an $n$-message coin-tossing 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 polynomial-time $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)$ (Komargodski-Raz [DISC'18], Mahloujifar-Mahmoody [ALT'19], and Etesami-Mahloujifar-Mahmoody [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 polynomial-time $k$-replacing targeted attacks can achieve $\mu'=\Pr[b'=1]=\beta^{(t-k)}_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^{(t-k)}_{ n-k }$ (using computationally unbounded attacks), which is optimal for adaptive adversaries who decide on corrupting parties before seeing their messages.