arXiv · Oct 18, 2026
No Escape from the Quadratic Barrier: Adaptive Attacks on Linear ℓ₂ Sketches
By Edith Cohen, Uri Stemmer
Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially many nonadaptive queries in sketch dimension k. For adaptive black-box queries, known privacy-based defenses guarantee Ω(k²) and it remained open whether stronger guarantees were possible. Prior attacks used more queries, restricted the responder, or provided weaker failure guarantees. We show that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query. For every fixed hidden AinR^(k× n) with n>40k and target accuracy α ∈ (0,1], our black-box attack uses O(k+α²k²log(2+α²k)) queries in O(1+α²k) adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have Ω(α) relative error. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.