Research map / Adversarial robustness and security / Black-box and transfer attacks
The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a universal, single-batch black-box attack on linear sketches for l2 norm estimation that uses O~(k^2) queries and yields an adversarial vector defeating the optimal estimator for the query distribution, matching known quadratic upper bounds.
Problem
Black-box adversarial robustness of linear sketches (JL, AMS) for l2 norm estimation: how many adaptive/non-adaptive queries are needed to find an input where the sketch-based norm estimate fails.
Approach
A universal attack that queries sparse signal plus dense Gaussian noise vectors on a random coordinate, collects norm-gap responses, and forms the normalized signed sum of noise vectors; the deviation of the optimal signal estimator grows as sqrt(r) while the norm stays O(sqrt r), giving a quadratic query bound independent of the sketching matrix.
Key results
- Theorem: with r = O(gamma^2 alpha^-2 k^2 log^2 k) queries and noise support m = Omega(k^2), either response error rate exceeds a constant or the output is gamma-adversarial for the optimal estimator.
- Empirically the attack inflates estimator bias on JL and AMS sketches (k in {100,250,1000}), with bias growing roughly like the square root of the number of queries.
- Attack remains effective with noise support as small as O(k) in experiments, below the n = Omega(k^2) the analysis requires.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the universal nonadaptive attack with \tilde{O}(k^2) queries | Any linear sketch and query responder for ℓ2 norm estimation · General linear sketches, ℓ2 norm estimation | queries to construct an adversarial input or cause responder failure: r = C \gamma^2 \alpha^{-2} k^2 \log^2 k | Helped |
| Add Gaussian noise to the squared-norm estimate before taking the square root | Standard norm estimators for Gaussian JL and AMS sketches · Gaussian JL and AMS sketches | robustness to attack (adversarial bias growth) | Helped |
| Add Gaussian noise to the squared-norm estimate before taking the square root | Standard norm estimators for Gaussian JL and AMS sketches · Fresh non-adaptive inputs | accuracy: 1/\sqrt{k} -> \sqrt{\frac{1}{k} + \sigma^{2}} | Hurt |
| Use the standard or lower-σ robust estimator instead of a higher-σ robust estimator | Robustified JL and AMS estimators · Gaussian JL and AMS sketches | adversarial bias growth | Hurt |
| Increase sketch dimension k | Robustified sketch estimators · Gaussian JL and AMS sketches | robustness to attack | Helped |
| Increase support size n | Universal attack on JL and AMS sketches · Gaussian JL and AMS sketches | attack effectiveness | Mixed |
Surprising findings
- The attack remains effective against the median-of-means estimator for AMS, a non-linear estimator, although the proof covers only linear optimal estimators.
- Experiments show success with noise support on the order of k, much smaller than the theoretical n = Omega(k^2) requirement.
Limitations
- Guarantee holds only against the optimal estimator for the query distribution, not every query responder.
- Theoretical analysis requires noise support n = Omega(k^2), larger than the empirically observed requirement.
- Empirical study limited to JL and AMS matrices with simulated responders.
Experimental setup
Metrics: ratio of estimated norm to true norm of adversarial vector error rate of norm-gap responses
Baselines: standard sketch-norm estimator median-of-means estimator for AMS robustified noisy estimators
Builds on: Johnson-Lindenstrauss transform AMS sketch adaptive data analysis robust estimators
Closest papers by meaning
- Sign Bits Are All You Need for Black-Box Attacks (ICLR 2020 · similarity 0.87)
- $\sigma$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples (ICLR 2025 · similarity 0.87)
- BRUSLEATTACK: A QUERY-EFFICIENT SCORE- BASED BLACK-BOX SPARSE ADVERSARIAL ATTACK (ICLR 2024 · similarity 0.87)
- Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs (ICML 2024 · similarity 0.87)
- Thwarting Adversarial Examples: An $L_0$-Robust Sparse Fourier Transform (NeurIPS 2018 · similarity 0.86)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.