**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 \colon \{0,1\}^n \to [-1,+1]$ by $\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 $p$. Our main result is an efficient blockwise $p$-tampering attack to bias the average $E[f(X)]$ of any efficient function $f$ mapping arbitrary $X$ to $[-1,+1]$ by $\Omega(p \cdot Var[f(X)])$ regardless of how $X$ is partitioned into individually tamperable blocks $X=(X_1,\dots,X_n)$. 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 $p$. 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 $d$ in mind and wishes to increase the error of classifying $d$ while she gets to tamper with each training example with independent probability $p$ an in an online way.

**Category / Keywords: **Tampering, Extractors, Adversarial Learning, Randomness.

**Original Publication**** (in the same form): **IACR-TCC-2017

**Date: **received 25 Sep 2017, last revised 23 Apr 2018

**Contact author: **mahmoody at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20180423:190550 (All versions of this report)

**Short URL: **ia.cr/2017/950

[ Cryptology ePrint archive ]