Tampering Attacks in Cryptography and Learning​

In this work, we revisit and extend the bitwise tampering model of Austrin et al. to the blockwise setting where each incoming block of randomness becomes tamperable with independent probability p. Our main result is an efficient blockwise p-tampering attack to bias the average of any efficient function f mapping arbitrary distribution X to [-1,+1] by \Omega(p Var[f(X)]), where Var[f(X)] is the variance of f(X), regardless of how X is partitioned into individually tamperable blocks X=(X_1,..., X_n). Further, relying on the blockwise nature of our biasing attack, we show how to bias the output of any seedless multi-source extractors if each source becomes tamperable with independent probability p. Finally, we show how to increase the classification error of deterministic learners in the so-called `poisoning' attack model under Valiant's adversarial noise where the adversary gets to tamper with each training example with independent probability p.