پژوهشگاه دانش‌های بنیادی
پژوهشکدهٔ ریاضیات

Mathematics Colloquium سمینار عمومی ریاضیات

Targeted Attacks on Coin Tossing Protocols and Applications

Mohmmad Mahmoody  
University of Virginia, USA  

Sunday, January 30, 2022,   16:00 - 17:00

VENUE   (Online)



Suppose n algorithms adaptively choose n pieces of an input (x1,...xn)=X one by one from some predefined distributions, and that Pr[f(X)=1]=p for a (known) Boolean function f. This defines a coin-tossing protocol with coin bias p. Now suppose an adversary A who observes the protocol, as it proceeds, can replace up to k of the inputs. How much can such adversary A increase Pr[f(X)=1] in the two natural settings below. 1.The tampered messages are chosen at random. 2. A can choose the tampered messages at wish. I will survey what is known about the question above, with the focus on (2) while aiming for polynomial-time attacks. I will also briefly mention the connections between the problem above and randomness-tampering attacks on encryption, data poisoning attacks on machine learning algorithms, as well as a new algorithmic approach to measure concentration in product spaces. Based on a sequence of joint works with Omid Etesami (IPM), Ji Gao (UVA), and Saeed Mahloujifar (Princeton) published at TCC'17, ALT'18, ALT'19, ICML'19, SODA'20, TCC'21.
Joining info: https://groups.google.com/g/ipm-math-colloquium


تهران، ضلع‌ جنوبی ميدان شهيد باهنر (نياوران)، پژوهشگاه دانش‌های بنيادی، پژوهشکده رياضيات
School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Niavaran Bldg., Niavaran Square, Tehran
ipmmath@ipm.ir   ♦   +98 21 22290928   ♦  math.ipm.ir