The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
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Ω(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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionImage ClassificationSimilar Papers 제목 키워드 기반
MALICE: Manipulation Attacks on Learned Image ComprEssion
Deep learning techniques have shown promising results in image compression, with competitive bitrate and image reconstruction quality from compressed latent. However, while image compression has progressed towards a high…
Image CompressionImage ReconstructionWhen Compression Becomes an Attack Surface: Black-Box Attacks on Prompt-Compressed LLM Agents
Prompt compression is increasingly deployed in LLM agents to reduce latency and cost, but it also determines what the backend LLM ultimately sees. We show that, when trusted and untrusted inputs are compressed under a sh…
QuadAttack: A Quadratic Programming Approach to Ordered Top-K Attacks
The adversarial vulnerability of Deep Neural Networks (DNNs) has been well-known and widely concerned, often under the context of learning top-$1$ attacks (e.g., fooling a DNN to classify a cat image as dog). This paper …
Binary Quadratic Quantization: Beyond First-Order Quantization for Real-Valued Matrix Compression
This paper proposes a novel matrix quantization method, Binary Quadratic Quantization (BQQ). In contrast to conventional first-order quantization approaches, such as uniform quantization and binary coding quantization, t…
Neural Network CompressionGlobal Performance Guarantees for Neural Network Models of AC Power Flow
Machine learning, which can generate extremely fast and highly accurate black-box surrogate models, is increasingly being applied to a variety of AC power flow problems. Rigorously verifying the accuracy of the resulting…