Fast White-Box Adversarial Streaming Without a Random Oracle

• URL: http://arxiv.org/abs/2406.06808v1
• Date: Mon, 10 Jun 2024 21:23:19 GMT
• Title: Fast White-Box Adversarial Streaming Without a Random Oracle
• Authors: Ying Feng, Aayush Jain, David P. Woodruff,
• Abstract summary: We consider a strong white-box adversarial model, 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. 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.
• Score: 48.45771871410984
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  We show how to analyze the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions. We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm. Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.
  arXiv  Detail & Related papers  (2024-07-19T08:29:12Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• Adversarially Robust Distributed Count Tracking via Partial Differential Privacy [17.43748116766233]
  We study the distributed tracking model, also known as distributed functional monitoring. This model involves $k$ sites each receiving a stream of items and communicating with the central server. For count tracking, it is known that there is a $sqrtk$ gap in communication between deterministic and randomized algorithms.
  arXiv  Detail & Related papers  (2023-11-01T07:42:13Z)
• Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model [14.204551125591022]
  An adversarial streaming algorithm must maintain utility even when the input stream is chosen adaptively and adversarially. We present two models that allow us to interpolate between the oblivious and the adversarial models. This allows us to design robust algorithms with significantly improved space complexity.
  arXiv  Detail & Related papers  (2023-01-22T21:13:13Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles. We use a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases.
  arXiv  Detail & Related papers  (2022-03-17T19:26:00Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering corrupted by random noise and adversarial modifications.
  arXiv  Detail & Related papers  (2021-08-10T14:46:17Z)
• A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators [26.151761714896118]
  We study streaming algorithms that provide provable guarantees even when the input stream is chosen by an adaptive adversary. We propose a novel framework for adversarial streaming that hybrids two recently suggested frameworks.
  arXiv  Detail & Related papers  (2021-07-30T10:20:38Z)
• Adversarial Robustness of Streaming Algorithms through Importance Sampling [29.957317489789745]
  We introduce adversarially robust streaming algorithms for central machine learning and algorithmic tasks. Our results are based on a simple, but powerful, observation that many importance sampling-based algorithms give rise to adversarial robustness. We empirically confirm the robustness of our algorithms on various adversarial attacks and demonstrate that by contrast, some common existing algorithms are not robust.
  arXiv  Detail & Related papers  (2021-06-28T19:24:11Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.