The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ₂ Norm Estimation

2025/07/22 by Sara Ahmadian, Edith Cohen, Ahmadian, Sara +3
Computer Science · #Adversarial Robustness in Machine Learning #Cryptographic Implementations and Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Security and Verification in Computing

paper · pdf · doi:10.48550/arxiv.2507.16345

openalex publication_date 2025/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the black-box adversarial setting, where a fixed, hidden sketching matrix A ∈ R^{k × n} maps high-dimensional vectors v ∈ Rⁿ to lower-dimensional sketches A v ∈ R^k, and an adversary can query the system to obtain approximate ℓ₂-norm estimates that are computed from the sketch. We present a universal, nonadaptive attack that, using O(k²) queries, either causes a failure in norm estimation or constructs an adversarial input on which the optimal estimator for the query distribution (used by the attack) fails. The attack is completely agnostic to the sketching matrix and to the estimator: it applies to any linear sketch and any query responder, including those that are randomized, adaptive, or tailored to the query distribution. Our lower bound construction tightly matches the known upper bounds of Ω(k²), achieved by specialized estimators for Johnson Lindenstrauss transforms and AMS sketches. Beyond sketching, our results uncover structural parallels to adversarial attacks in image classification, highlighting fundamental vulnerabilities of compressed representations.

Citations

• Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
• One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
• A Strong Separation for Adversarially Robust ℓ₀ Estimation for Linear Sketches
• Subsampling Suffices for Adaptive Data Analysis
• Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
• On the Robustness of CountSketch to Adaptive Inputs
• Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
• Adversarially Robust Streaming via Dense--Sparse Trade-offs
• A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
• Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
• On Adaptive Distance Estimation
• Adversarially Robust Streaming Algorithms via Differential Privacy
• Rounding Dynamic Matchings Against an Adaptive Adversary
• Minimum Cut in O(mlog² n) Time
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Practical Black-Box Attacks against Machine Learning
• Algorithmic Stability for Adaptive Data Analysis
• Explaining and Harnessing Adversarial Examples
• Preserving Statistical Validity in Adaptive Data Analysis
• Preventing False Discovery in Interactive Data Analysis is Hard
• Intriguing properties of neural networks
• How Robust are Linear Sketches to Adaptive Inputs?
• Decoding by Linear Programming

Related

• Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
• A Strong Separation for Adversarially Robust ℓ₀ Estimation for Linear Sketches
• How Robust are Linear Sketches to Adaptive Inputs?
• L_p-norm Distortion-Efficient Adversarial Attack
• Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability