# The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\\ell\_2$ Norm Estimation

Source: [The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\\ell\_2$ Norm Estimation](<https://www.sota2.com/research/paper/68fa7b761e209131cea88a47>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T05:41:29.127Z

Authors: Sara Ahmadian, Edith Cohen, Uri Stemmer

Published: 2025-07-22T08:25:05.000Z

## 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 \\in R^{k \\times n}$ maps high-dimensional vectors $v \\in R^n$ to lower-dimensional sketches $A v \\in R^k$, and an adversary can query the system to obtain approximate $\\ell\_2$-norm estimates that are computed from the sketch. We present a universal, nonadaptive attack that, using $\\tilde{O}(k^2)$ 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 $\\tilde{\\Omega}(k^2)$, 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2507.16345>)

[PDF](<https://arxiv.org/pdf/2507.16345.pdf>)
