arXiv preprint ·
No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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Ω(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 $α\in (0,1]$, our black-box attack uses $O(k+α^2k^2\log(2+α^2k))$ queries in $\widetilde{O}(1+α^2k)$ 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Hadamard Transforms for Dimension Reduction
Approximating Independent Sets Using Additive Combinatorics
Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision
Strategy recovery for Mean-Payoff Games is as hard as solving them from scratch
Integer Programing: An Algorithm with Exponent Linear in the Dimension
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.