Paper 2017/950

Blockwise $p$-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners

Saeed Mahloujifar and Mohammad Mahmoody

Abstract

Austrin, Chung, Mahmoody, Pass and Seth (Crypto'14) studied the notion of bitwise $p$-tampering attacks over randomized algorithms in which an efficient `virus' gets to control each bit of the randomness with independent probability $p$ in an online way. The work of Austrin et al. showed how to break certain `privacy primitives' (e.g., encryption, commitments, etc.) through bitwise $p$-tampering, by giving a bitwise $p$-tampering biasing attack for increasing the average $E[f(U_n)]$ of any efficient function $f:\{0,1{\}}^n\to [-1,+1]$ by $\mathrm{\Omega }(p\cdot Var[f(U_n)])$ where $Var[f(U_n)]$ is the variance of $f(U_n)$. In this work, we revisit and extend the bitwise tampering model of Austrin et al. to blockwise setting, where blocks of randomness becomes tamperable with independent probability $$. Our main result is an efficient blockwise $$-tampering attack to bias the average $$ of any efficient function $$ mapping arbitrary $$ to $$ by $$ regardless of how $$ is partitioned into individually tamperable blocks $$. Relying on previous works, our main biasing attack immediately implies efficient attacks against the privacy primitives as well as seedless multi-source extractors, in a model where the attacker gets to tamper with each block (or source) of the randomness with independent probability $$. Further, we show how to increase the classification error of deterministic learners in the so called `targeted poisoning' attack model under Valiant's adversarial noise. In this model, an attacker has a `target' test data $$ in mind and wishes to increase the error of classifying $$ while she gets to tamper with each training example with independent probability $$ an in an online way.