mlsanityData to 7 Oct 2026

Fast White-Box Adversarial Streaming Without a Random Oracle

arXiv 2406.06808 ↗First posted 10 Jun 2024cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

27 of 72 references.

References · 27

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2016Adversarial Machine Learning at Scalecited by 934
  5. 2017Ensemble Adversarial Training: Attacks and Defensescited by 833
  6. 2018AutoAugment: Learning Augmentation Policies from Datacited by 728
  7. 2016Delving into Transferable Adversarial Examples and Black-box Attackscited by 530
  8. 2018Adversarially Robust Generalization Requires More Datacited by 318
  9. 2018Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priorscited by 145
  10. 2021Adversarial Laws of Large Numbers and Optimal Regret in Online Classificationcited by 39
  11. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  12. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
15 more
  1. 2019The Adversarial Robustness of Samplingcited by 18
  2. 2020Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimatorscited by 16
  3. 2021Adversarial Robustness of Streaming Algorithms through Importance Samplingcited by 13
  4. 2021Separating Adaptive Streaming from Oblivious Streamingcited by 9
  5. 2021A Framework for Adversarial Streaming via Differential Privacy and Difference Estimatorscited by 9
  6. 2021Adversarially Robust Streaming via Dense--Sparse Trade-offscited by 7
  7. 2019Rounding Dynamic Matchings Against an Adaptive Adversarycited by 6
  8. 2021Streaming data preprocessing via online tensor recovery for large environmental sensor networkscited by 3
  9. 2021Adversarially Robust Coloring for Graph Streamscited by 3
  10. 2022The White-Box Adversarial Data Stream Modelcited by 3
  11. 2014For-all Sparse Recovery in Near-Optimal Timecited by 1
  12. 2021More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Timecited by 1
  13. 2021Beating the Folklore Algorithm for Dynamic Matchingcited by 1
  14. 2021Keep That Card in Mind: Card Guessing with Limited Memorycited by 1
  15. 2023Improved Algorithms for White-Box Adversarial Streamscited by 1

Built on by

Not cited yet.