“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 16758 |
|
| Abstract: | |
|
Consider a coin tossing protocol in which n processors P_1,...,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,...,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 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/). 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 (k/) for any k [n]. Kalai, Komargodski, and Raz [DISC'18, Combinatorica'21] gave an alternative polynomial-time attack when k (). Etesami, Mahloujifar, and Mahmoody [ALT'19, SODA'20] extended the result of KKR18 to arbitrary long messages. 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 (k/) 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() of the n training examples. - For uniformly random bits b_1,...,b_n, we show that whenever Pr[b=1]=Pr[ b_i t]=_n for t [n] is the probability of a Hamming ball, then online polynomial-time k-replacing attacks can increase Pr[b=1] from _n to _n , which is optimal due to the majority protocol. In comparison, the (information-theoretic) attack of LLS89 increased Pr[b=1] to _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.
Download TeX format |
|
| back to top | |
