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

Edith Cohen; Uri Stemmer

cs.DSOct 18, 2026

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

Authors: Edith Cohen, Uri Stemmer

Organizations: Google Research · Tel Aviv University

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.

Figures & tables

Figure 1: The covariance attack in sketch space for queries with signal $w=1$ (blue) and $w=1+\alpha$ (orange). Sketches are projected on the signal column $A_{h}$ and an orthogonal direction. Illustration shows $2\sigma$ ellipses of the sketch noise. The dashed line is the threshold $1+\alpha/2$ . At the start the input noise is isotropic, and the sketch noise may separate the two signals (if there is overlap we are done). At the end, if the responder does not err earlier on an easy distribution, the sketch noise is stretched along $A_{h}$ and the two signals overlap.

Robustness benchmark: AMS/JL with robustified estimator
Result	Responder	Guaranteed outcome	Queries	Rounds	Support	Operations
Hardt–Woodruff [ 40 ]	Fixed within round	Constant error rate (on queried fixed estimator)	$\mathrm{poly}(k)$	$\widetilde{O}(k)$	$O(k)$	$\mathrm{poly}(k)$
ACS [ 1 ]	Informed	Constant error rate OR failure of dist-optimal est	$\widetilde{O}(k^{2})$	$1$	$\widetilde{O}(k^{2})$	$\widetilde{O}(k^{4})$
This work: general	Informed	Constant error rate (in round)	$O(k^{2}\log k)$	$O(k\log k)$	$\Theta(k)$	$\widetilde{O}(k^{4})$
sufficient statistic	Informed; scalar statistic	Constant error rate (in round)	$O(k^{2})$	$O(\log k)$	$\Theta(k)$	$\widetilde{O}(k^{3})$
[ 41 , 14 ]	Fixed	Accurate answers	$\widetilde{\Omega}(k^{2})$	—	—	—

Table 1: Comparison at constant accuracy and success probability. Sketch dimension

k

. Rounds are of attack adaptivity. Support is the size of a common coordinate set. Arithmetic-operation counts assume unit-cost sampling.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: The signal density and the two labeled regimes. Each ramp has width $\ell=10\alpha/c$ ; the plateau is the unlabeled gap of width $\alpha$ . The gap is widened schematically for legibility; horizontal widths are not to scale.

Randomized Sketching

Randomized sketching uses compact random projections or summaries to speed computation while approximately preserving data, geometry, or statistical structure.

See all 45 papers

Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch
Sep 16, 2026Mohammad Azhar Khan, Rameshwar Pratap, Amit SharmaRandomized Sketching
Indian Institute of Technology Hyderabad, Kandi, Sangareddy, 502284, Telangana, India.
The Fast Mixing Mechanism for Differential Privacy
May 28, 2026Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2Randomized Sketching Differential Privacy
Massachusetts Institute of Technology · The Hebrew University of Jerusalem
Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee
Aug 27, 2026Zhao Song, Lichen ZhangRandomized Sketching Linear Regression
Independent Researcher. · Massachusetts Institute of Technology.

Sep 16, 2026J/K move · Enter open · S save

Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

Mohammad Azhar Khan, Rameshwar Pratap, Amit Sharma

Indian Institute of Technology Hyderabad, Kandi, Sangareddy, 502284, Telangana, India.

Randomized Sketching

Open paper AskPDF arXiv

We consider the problem of estimating the trace of an implicit matrix

\mathbf{A} \in \mathbb{R}^{d^p\times d^p}

that can only be accessed through matrix-vector products queries. The Hutchinson trace estimator% \cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{(i)}}^T \mathbf{A} \mathbf{z}^{(i)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$ , and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$ , satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$ , and (ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$ . Generating one query vector $\mathbf{z}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(md^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in

\mathbb{R}^{d^p}

is constructed as the Kronecker product of

p

random vectors in

\mathbb{R}^d

, requiring

O(mpd)

random bits for

m

query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with

p

. In this work, we address this limitation by proposing a sketching-based estimator that requires

O\!\big(p (d + m)\log m\big)

random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with

p

Abstract

Randomized Sketching

Explore similar work

Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

The Fast Mixing Mechanism for Differential Privacy

Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee