# Fast White-Box Adversarial Streaming Without a Random Oracle

arXiv: https://arxiv.org/abs/2406.06808 · HTML: https://mlsanity.com/paper/2406.06808/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 72 references that are in the map.
- First posted on arXiv 10 Jun 2024.

## Builds on (most cited first, 27 of 27)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [AutoAugment: Learning Augmentation Policies from Data](https://mlsanity.com/paper/1805.09501/) (2018)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors](https://mlsanity.com/paper/1807.07978/) (2018)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [The Adversarial Robustness of Sampling](https://mlsanity.com/paper/1906.11327/) (2019)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Separating Adaptive Streaming from Oblivious Streaming](https://mlsanity.com/paper/2101.10836/) (2021)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adversarially Robust Streaming via Dense--Sparse Trade-offs](https://mlsanity.com/paper/2109.03785/) (2021)
- [Rounding Dynamic Matchings Against an Adaptive Adversary](https://mlsanity.com/paper/1911.05545/) (2019)
- [Streaming data preprocessing via online tensor recovery for large environmental sensor networks](https://mlsanity.com/paper/2109.00596/) (2021)
- [Adversarially Robust Coloring for Graph Streams](https://mlsanity.com/paper/2109.11130/) (2021)
- [The White-Box Adversarial Data Stream Model](https://mlsanity.com/paper/2204.09136/) (2022)
- [For-all Sparse Recovery in Near-Optimal Time](https://mlsanity.com/paper/1402.1726/) (2014)
- [More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time](https://mlsanity.com/paper/2103.07857/) (2021)
- [Beating the Folklore Algorithm for Dynamic Matching](https://mlsanity.com/paper/2106.10321/) (2021)
- [Keep That Card in Mind: Card Guessing with Limited Memory](https://mlsanity.com/paper/2107.03885/) (2021)
- [Improved Algorithms for White-Box Adversarial Streams](https://mlsanity.com/paper/2307.03529/) (2023)

## Abstract (arXiv)

Recently, the question of adversarially robust streaming, where the stream is allowed to depend on the randomness of the streaming algorithm, has gained a lot of attention. In this work, we consider a strong white-box adversarial model (Ajtai et al. PODS 2022), in which the adversary has access to all past random coins and the parameters used by the streaming algorithm. We focus on the sparse recovery problem and extend our result to other tasks such as distinct element estimation and low-rank approximation of matrices and tensors. The main drawback of previous work is that it requires a random oracle, which is especially problematic in the streaming model since the amount of randomness is counted in the space complexity of a streaming algorithm. Also, the previous work suffers from large update time. We construct a near-optimal solution for the sparse recovery problem in white-box adversarial streams, based on the subexponentially secure Learning with Errors assumption. Importantly, our solution does not require a random oracle and has a polylogarithmic per item processing time. We also give results in a related white-box adversarially robust distributed model. Our constructions are based on homomorphic encryption schemes satisfying very mild structural properties that are currently satisfied by most known schemes.