“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16758
School of Mathematics
  Title:   Polynomial-time targeted attacks on coin-tossing for any number of corruptions
  Author(s):  Omid Etesami (Joint with J. Gao, S. Mahloujifar, and M. Mahmoody)
  Status:   In Proceedings
  Proceeding: The Theory of Cryptography Conference (TCC) 2021
  Year:  2021
  Supported by:  IPM
  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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right