提出一种新型压缩攻击，可高效破坏任意低维映射的范数估计。
The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
- 基于黑盒查询构造通用非自适应攻击，仅需约k²次查询
- 在任意线性映射和估计器下均有效，且达到理论最优复杂度
- 揭示压缩表示与图像分类中对抗攻击的深层共性，适合安全研究者
通过线性映射进行降维是强大且广泛使用的技术，但已知对对抗输入敏感。本文研究黑盒对抗设置：固定隐藏的映射矩阵 $A \in \mathbb{R}^{k \times n}$ 将高维向量 $v \in \mathbb{R}^n$ 映射为低维草图 $A v \in \mathbb{R}^k$，攻击者可通过查询获取基于草图的近似 $\β_2$-范数估计。我们提出一种通用、非自适应攻击，仅需 $\tilde{O}(k^2)$ 次查询，即可导致范数估计失败或构造出使最优估计器失效的对抗样本。该攻击完全不依赖于映射矩阵和估计器，适用于任意线性草图及任意查询响应机制（包括随机化、自适应或针对查询分布优化的）。其下界构造与已知 $\tilde{\Omega}(k^2)$ 上界紧致匹配，覆盖了针对 Johnson-Lindenstrauss 变换和 AMS 草图的专用估计器。本结果不仅拓展至草图领域，更揭示压缩表示与图像分类中对抗攻击之间的结构相似性，揭示了压缩表示的根本脆弱性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。