Polynomial-Time Targeted Attacks on Coin Tossing for Any Number of Corruptions

Abstract

Consider a coin tossing protocol in which n processors $P_1,\dots ,P_n$ agree on a random bit b in n rounds, where in round i $P_i$ sends a single message $w_i$. Imagine a full-information adversary who prefers the output 1, and in every round i it knows all the finalized messages $w_1,\dots ,w_{i-1}$ so far as well as the prepared message $w_i$. A k-replacing attack will have a chance to replace the prepared $w_i$ with its own choice $w'_i \ne w_i$ in up to k rounds. Taking majority protocol over uniformly random bits $w_i=b_i$ is robust in the following strong sense. Any k-replacing adversary can only increase the probability of outputting 1 by at most $O(k/\sqrt{n})$. In this work, we ask if the above simple protocol is tight.

For the same setting, but restricted to uniformly random bit messages, Lichtenstein, Linial, and Saks [Combinatorica’89] showed how to achieve bias $\varOmega (k/\sqrt{n})$ for any $k \in [n]$. Kalai, Komargodski, and Raz [DISC’18, Combinatorica’21] gave an alternative polynomial-time attack when $k \ge \varTheta (\sqrt{n})$. Etesami, Mahloujifar, and Mahmoody [ALT’19, SODA’20] extended the result of KKR18 to arbitrary long messages. It hence remained open to find any attacks of bias $\varOmega (k/\sqrt{n})$ in the few-corruption regime $k=o(\sqrt{n})$ when the messages are of arbitrary length, and to find such polynomial-time (and perhaps tight) attacks when messages are uniformly random bits. In this work, we resolve both of these problems.

• For arbitrary length messages, we show that k-replacing polynomial-time attacks can indeed increase the probability of outputting 1 by $\varOmega (k/\sqrt{n})$ for any k, which is optimal up to a constant factor. By plugging in our attack into the framework of Mahloujifar Mahmoody [TCC’17] we obtain similar data poisoning attacks against deterministic learners when adversary is limited to changing $k=o(\sqrt{n})$ of the n training examples.

• For uniformly random bits $b_1,\dots ,b_n$, we show that whenever $\Pr [b=1]= \Pr [\sum b_i \ge t] = \mathsf {\beta }^{(t)}_n$ for $t \in [n]$ is the probability of a Hamming ball, then online polynomial-time k-replacing attacks can increase $\Pr [b=1]$ from $\mathsf {\beta }^{(t)}_n$ to $\mathsf {\beta }^{(t-k)}_n$, which is optimal due to the majority protocol. In comparison, the (information-theoretic) attack of LLS89 increased $\Pr [b=1]$ to $\mathsf {\beta }^{(t-k)}_{n-k}$, which is optimal for adaptive adversaries who cannot see the message before changing it. Thus, we obtain a computational variant of Harper’s celebrated vertex isoperimetric inequality.