No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches

Abstract: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 $\widetilde{\Omega}(k^2)$ 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 $A\in\mathbb{R}^{k\times n}$ with $n>40k$ and target accuracy $\alpha \in (0,1]$, our black-box attack uses $O(k+\alpha^2k^2\log(2+\alpha^2k))$ queries in $\widetilde{O}(1+\alpha^2k)$ adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have $\Omega(\alpha)$ relative error. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.

Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

arXiv:2610.25008 [cs.DS]

(or arXiv:2610.25008v1 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2610.25008 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.