“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 fullinformation adversary who prefers the output 1, and in every round i it knows all the finalized messages w_1,...,w_i1 so far as well as the prepared message w_i. A kreplacing 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 kreplacing 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 polynomialtime 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 kreplacing polynomialtime 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 polynomialtime kreplacing attacks can increase Pr[b=1] from _n to _n , which is optimal due to the majority protocol. In comparison, the (informationtheoretic) attack of LLS89 increased Pr[b=1] to _nk, 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 