The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
Authors: Sara Ahmadian
Edith Cohen
Uri Stemmer
Venue: NeurIPS 2025 poster ()
Keywords: $\ell_2$ sketches
dimensionality reduction
robustness
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Attack of size quadratic in sketch size (meets upper bound)

Abstract: 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 \emph{black-box adversarial setting}, where a fixed, hidden sketching matrix $A \in \mathbb{R}^{k \times n}$ maps high-dimensional vectors $\boldsymbol{v} \in \mathbb{R}^n$ to lower-dimensional sketches $A\boldsymbol{v} \in \mathbb{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 \emph{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 \emph{any} linear sketch and \emph{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{\Omega}(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.

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for l2 Norm Estimation
Sara Ahmadian
Edith Cohen
Google Research
Google Research and Tel Aviv University edi edithhcohenvang.. com
sahmadi waw.oddle@@@ggggc.oooomo
Uri Stemmer
Tel Aviv University and Google Research
n@uri.co.il
Abstract
Dimensionality reduction via linear sketching is powerful and widely used tech- nique, but it known to be vulnerable to adversarial inputs. We study the black-box adversurial setting, where a fixed, hidden sketching matrix A E R maps high- dimensional vectors v E R" to lower-dimen dwwer-dimensionl sketches Av E RR and an adversary query the system to obtain approximate 22-norm estimates that are computed from the sketch.
We present universal, nonadaptive atlack that, using Ö(k2) queries, either causes a failure in norm estimation or constructs an adversarial input on which the opti- mal estimator for the query distribution (used by the attack) fails. The attack is completely agnostic to the sketching matrix and to the estimator-in 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 (((2.), achieved by specialized estimators for
transforms and AMS sketches. Beyond sketching, our results uncover structural parallels adversarial attacks in image classification, highlighting fundamental vulnerabilities compressed representations.
Introduction
Dimensionality reduction a fundamental technique data analysis, algorithm design, and machine learning. A common paradigm is to apply sketching map, compressive transformation C' R -
R which maps a high-dimensional input vector to a lower-dimensional representation. The map typically sampled from a known distribution (e.g., The Johnson Johnson-LLndenn Lindenstrauss (JL) transform [29] ) or learned during training, and is designed support estimation of specific properties of the input v, such norms, inner products, or distances, using only the sketch C(v)..
Once constructed, the sketching map typically remains fixed across all inputs. This true when compression layers are part of a trained model, and it is necessary in algorithmic contexts that require composabilitytte ability sketch distributed datasets independently and combine the reshhts-without revisiting the original data. A fixed sketching map also supports downstream tasks that operate directly in sketch space.
However, this compression introduces an intrinsic vulnerability: small input perturbations can produce large changes in the sketch, even when the true property (such the norm) is nearly unchanged. For linear sketching maps A E R&xn, this vulnerability arises from structural facts such as the existence
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of nontrivial null-space vectors and directions along which small-norm perturbations yield large distortions.
Such adversarial inputs can be constructed easily in the white-box setting, where the sketching map C' is known. In this work, we focus the black-hox attack model, which captures realistic situations where the adversary does not see the sketching map directly but can access it interactively via a responder using queries of the following form:
(i) The adversary chooses a query vector v E IR...
(ii) The system receives v and computes a sketch C(v).
(iii) The responder selects map & of sketches to distributions, receives the sketch C(v) from system and returns a (possibly randomized) value ~ (C(()) to the adversary.
The goal of the adversary, in general terms, is to compromise the sketching map by causing a failure: If responses are correct, construct an adversarial input. We measure the efficiency of such attacks by the number of queries they require, as function of the sketch size k.
We distinguish between two settings. In the nonadaptive case, all queries (including the final candidate) are chosen without regard to responses from earlier queries. The adversary performs a blind search, and success depends on the density of adversarial directions in the input space. In contrast, in the adaptive setting, each query can depend on prior responses, allowing the adversary to extract information about the sketching map and potentially converge to an adversarial input more efficiently.
The black-box model in the adaptive setting is well studied across multiple areas, including statistical queries [19, 28, 31, 25, 17, 6]. sketching and streaming algorithms [33, 26, 9, 27, 40, 5, 8, 13, 15, 1, 22, 16], dynamic graph algorithms [36, 2, 20, 24, 39, 7], and machine learning [37, 21, 4, 34, 32, 35).
In this study, we aim to better understand this vulnerability for the task of 2o-m estimation and to gain more general insights through this lens. Specifically, we consider linear transformations specified by a sketching matrix
R which maps v E IR" to a sketch Av E IR
Two classic methods for this task are the Johnson-Lindenstenn Lindenstrauss (JL) transform [29] and the AMS sketch [3], They define distributions over sketching matrices that approximately preserve Euclidean norms (and therefore support sketch- based approximation of distances). The provided guarantees are probabilistic: for any input vector, with high probability over the random choice of the sketching matrix A E & the scaled norm of the sketch || closely approximates |||2 (within relative error 6 with probability 1 when k = -2 Oogg(111( (og(1/))).
However, as said, in practice, the sketching matrix is typically fixed over all input vectors, and importantly, no fixed matrix can preserve approximate norms for all inputs: every sketching matrix inevitably has inputs on which it fails. In the nonadaptive setting, the guarantees of JL and AMS apply via a union bound: with high probability (at least - 5) over the sampling of matrices, the fixed sampled sketching matrix supports up to de O(ke) approximate norm queries, in the sense that with probability 1 8, they are all accurate to within relative error e. Therefore, finding a bad input requires a number of queries that is exponential in k.
The adaptive setting was studied in multiple works. In terms of positive results, it is known that JL and AMS sketches can effectively trade off baseline mon-adappivve accuracy and robustness within a fixed sketch size budget of k. By using carefully designed "robust" estimators [27, 10]. the sketch can support for a fixed e, number of adaptive queries that guadratic in k. The idea, based on [18, 6). is to protect information on the sketching matrix by adding noise to the returned "best possible" estimate (or by subsampling a part of the sketch for each response).
As for negative results, Hardt and Woodruff [26] constructed an attack of size polynomial in k that for any sketching matrix constructs a distribution over inputs under which any estimator would fail. The idea in the attack is to identify vectors that lie close to the null space of A and hence are transparent to the sketch. Cherapanamjeri and Nelson [12], Ben-Eliezer et al. [9] presented an attack of size linear in & on the JL and AMS sketches with the standard estimator (which returns a scaled norm of the sketch). The product of these attack is a vector on which the standard estimator fails. Cohen et al. [15] constructed an attack of quadratic size on the AMS sketch that is universal (applies against any query responder), that constructs a vector on which the standard estimator fails. These negative results vary by (i) the scope of the sketching matrices compromised (general or JL/AMS), (ii) the

---

power of the query responder (strategic and adaptive or the standard estimator), and (iii) the product of the attack (a distribution that fails any query responder or a single vector with an out-of-distribution sketch that fails the "optimal" estimator).
An intriguing gap remains, however, between the established quadratic guarantee for the number of adaptive queries with correct responses and the super-quadratic sizes of the known attacks for general sketching matrices.
1.1 Overview of contributions
Our primary contribution in this work, is a construction of an attack of quadratic size in lc that applies against any sketching matrix R4xn and with any query responder for Eg norm estimation. The attack produces a vector with an dittrf-distribution sketch:
Theorem 1.1 (Attack Properties). There exist universal constant C' > 0, and families of distribu- tions Fn over R", such that the following holds.
For every sketching matrix A R with n = Q2k?',, any query responder, and deviation y 2 1 and accuracy E (0, 1) parameters, with probability at least 0.9 over the choice of distribution DD F, after r o>2a2 log" 2 ii.d. queries D, one of the following outcomes occurs:
(i) At least 8(a)) > 0* fraction of the responses have relative enror greater than a. or
(ii) We construct a query vector on which the optimal estimator (with respect to A and 'D) returns a value that deviates from the true norm by least a multiplicatiiv factor of 7j-
Our attack deploys simple and natural query distribution that combines weighted sparse signal with additive dense noise:
v wee + u,
where en. is the standard basis vector corresponding index [n]. and u is Gaussian noise supported on a set M C. [n] \ {h} of size m > k.2
Importantly, sparse queries alone insufficient for attack: under the mild assumption that the sketching matrix A has its columns in general position, the & norm of any k-sparse vector can be exactly recovered from its sketch (e.g., [11]). This implies that if the attack is restricted to sparse inputs, the response leaks no information about the sketching matrix and full robustness is preserved.
To sample from our query distribution, we first choose the signal coordinate h ~ [n] uniformly at random, and then independently sample a noise support M C [n]] \ (h} of size m = !2kk2)
The goal of the query responder is to estimate the l2 norm of v from its sketch Av, with relative error at most a. Our attack remains effective even against the simpler norm gap task: return - if ||
||l||| < 1 and return if wl]2 2 + a, with either output permitted when || E (1, + a).
Note that the norm gap task reveals strietly less information than norm estimation: with relative error ((a) trivially yields a correct solution to the norm gap task with parameter ((a), but vice versa.
estimate
Our attack described in Algorithm Query vectors (v(1)) (eE(r) are constructed by sampling signal value (t) ~ W, where W is probability distribution over R, and Gaussian noise (t) to form (1) = (0 en + (1) The adversary collects the responses (1)) for the sketch Av(O, We establish that if the responses are correct for the norm gap (except for small fraction of queries) then the normalized signed sum of the noise vectors Σ, ((t) is adversarial.
Universality and Limitations Our attack is universal in that it applies with any query responder. The analysis allows the responder to be strategic and adaptive, with full knowledge of the query distribution D and the internal state of the attacker. Notably, the attack is single batch - it uses adaptivity the minimal possible way: all queries are generated independently and only the final adversarial vector is constructed adaptively from the responses.
A constant that depends on a 'Single batch attacks were constructed in prior works for JL, Count-Sketch, AMS, and Cardinality sketches [12-14, 14, 1].
3

---

A limitation of our result is that the attack guarantees failure only for the optimal estimator tailored and A, rather than for every possible query responder. The stronger coaal--onsuueting distribution over inputs that defeats all responders with high probability- open.
Despite this, we believe result is both theoretically meaningful and practically relevant. Theoreti- cally, we obtain right quadratic bound in the batch-query model, whereas known attacks with the stronger guarantee require significantly more queries (a higher degree polynomial in k). Moreover, any attack achieving the stronger guarantee would require least (2(k) adaptive batches, and thus cannot be realized within our single-batch setting. In this sense, the adversarial vector we construct is the strongest outcome achievable in our setting.
Our attack product is practically relevant because the optimization process in a model training tends converge an (at least locally) optimal estimator for the training distribution. Therefore, compromising the model means compromising this specific implemented estimator, coded in the model parameter values, rather than any possible query responder.
Roadmap Our attack algorithm is described in Section with the analysis presented in Section 4. An empirical study of our attack on JL and AMS sketching matrices is included in Section 5. We conclude in Section with discussion of open directions and implications to image classifiers.
2
Preliminaries
We denote vectors in boldface u, scalars v in non boldface, and inner product of two vectors by (v, u.) >; 0,U4g For vector R", we refer to E [n] as key and to u; the value of the ith key. For M C [n]] let uM be the projection of v on entries (Mz)ae To streamline the presentation, interchangeably
the same notation to refer both random variable and a distribution.
N(,, o²) is the normal distribution with mean 0 and variance o² with density function
(===))²
Pp.02 (x)
(1)
042
o0 is the E-dimensional Gaussian distribution with covariance matrix It iLid. ((,, o()) Its probability density function is
1u1
fo( 2
20
linear sketching map defined by a sketching matrix A *x* where < n. The input is represented vector IR" and the sketch of v is the product Av R
Attack description
Definition 3.1 ((y, aapG Problem). Given width parameter >> 0 and y R, a gap problem is, for input x E R to return -1 when x I y and to return when x 2 y + a. The output may be arbitrary in (-1, |l|2 (y.y a).
Observe that an additive approximation of ax/2 or a multiplicative approximation of a/ (2(y + a)) for yields correct solution to the (e, a--aap problem for æ. Hence an attack that is effective with the weaker norm gap responses is more powerful.
Our attack is described in Algorithm The signal density and parameter settings described in Definition 3.3.
In each of r attack steps,
1. The adversary samples an independent query vector e := we + cz by sampling Gaussian noise with support M (O, x² 1/m), sampling signal weight ~ W.
2. The responder chooses an estimator map v R + P((-1, (((1,1)) 13), obtains the sketch Av from the system, and returns ((Av) to the adversary.

---

Algorithm
1:
Universal Attack on Sketching Matrix A; lg norm gap
responder
Input: A E R*x" accuracy parameler a, number of queries r, signal index h E [n], support M C [n] size m |M noise scale factor
for E [r] do // Main loop
0
i $ M i M
// sample noise vector
M(O,
1/m)
(1) W
1/ Sample signal weight from W. (Definition 3.3)
(1) w()) en + (2)
// Query vector // sketchee responses 1/ Responder receives aketch, returns 8(t) E {-11,1)
Responder chooses estimator (1)) R 4 P(-1,1)
(0)) (Av(()
2ieed a (02(0
return x (adv)
[[ (1
I/ Adversarial noise
3. The adversary then adds sz the accumulated output.
The product of the attack ((adv) the normalized accumulated output.
Theorem 3.2 (Attack efficacy). Let A E R&xn be sketching matrix. Consider applying Algo- rithm with a randomly selected h E [n] and support M C [m] \. {h} of size m = (2(k2) and r = a(72a2x² 222 log" k) queries. Then with constant probability one of the following holds. Either the error rate of responses s(1) for the (1, o-)-aap problem on the input norm [| ll (see Defini- tion 3.1) exceeded some constant ō(() > 0 or the vector z ((adv) is "-adversarial noise vector (see Definition 4.3) for A, signal h and noise support M.
We define vector as a-aavvrrariall if, under the query distribution specified by h and M, the optimal estimator returns value that deviates from the true norm by a multiplicative factor of at least y,
3.1 Density and parameter setting
Definition 3.3 (Signal density and parameters). a<l<l+a < b and has density function:
The distribution W' we use for w is parametrized by
0,
W < a or w > b
C W
a w 1
2
1- a
C b +
v(w)
C,
1< w l+a,
C b -
1 w
We set the parameters as follows according the gap and the error rate 8 allowed for the responder. We use > 0 that satisfies 5/ log(1/8) = ((a²) and that is a small constant (that does not depend on and is selected according other constants).
1 - 10a/c
1 + a + 10a/c
Observe from settings that each of the intervals (a. 1] and [1 a, has at least constant fraction of the probability mass.
4 Analysis of the attack
This section presents the key components and outlines the proof of Theorem 3.2, with full details deferred to the appendix.
5

---

We introduce notation for the query and noise distributions. For indices M C [n], let Na be the distribution over E IR" in which Wju] and the coordinates indexed by M are sampled from the m = |M -dimensionna Gaussian distribution uM ~ (O, 1 m)). Note that Nu, M is the distribution of noise vectors selected in Algorithm 1.
For [m)] M [m] \ {h}, and noise scale leet
Fh, == we + cN
(3)
be the distribution of vectors formed by adding a scaled noise vector sampled from Nn. m to a signal wey, where ea. E RR is the standard basis vector at index h. F,,,,,lw] is the distribution of query vectors selected in Algorithm I for signal value w.
Our analysis is in terms of signal estimation. In order to facilitate it, establish that correct norm gap output yields a correct signal gap output with similar parameters:
Lemma 4.1 (Norm gap signal gap). With the choice of parameters for our attack and m Q(kk + r) log((k: + r)) with probability close to 1, a correct (1 e 1.1.,a))nor gap output implies correct (1,ax)-signat gap output all queries.
The proof is included in Appendix A. The norm gap in the statement of Theorem 3,2 is with parameters (1,a). To reduce clutter, we treat it in the sequel as signal gap of (1,
4.1 Signal estimation and the optimal estimator
For fixed sketching matrix A, h E [ni], and noise support M, we express the optimal estimator on the signal w from a sketch Av when v ~ [e., For this purpose we may assume that the distributions (and A, h. and M) are given the responder. Note that if it holds that Aoh O, then the sketch carries no information on the signal w. When this is not the case, we can express the optimal unbiased estimator. The proof included Appendix
Lemma 4.2 (Estimator for the Signal). Fix h E (n), noise support set M C [m) (h), and a noise scale factor e. Consider the distributions Fh.,,alu) parametrized by w.
If the column Ash is nonzero, then there exists an unbiased, complete, and sufficient statistic Th.M R + for the signal w based on the sketch Av.
Furthermore, the deviation of this estimator from its mean, defined as
An.as (c.Au) == Th, (Av) W. depends only on the sketch of the noise u Nn.Ms. and distributed as a Gaussian random variable (00 oo (h, M).
The estimator Th (Av) also minimizes the mean squared error (MSE) [30].
We define an adversarial noise vector to be one that causes a large deviation in this optimal estimator:
Definition 4.3 (7 adversarial noise). A unit vector u with support M is 7-adversarial for A, h, M if | (u)) > >
Adversity of 7 means that the value is /////rrr)) standard deviations off. We will see that the attack size needed for certain adversity depends on or.
4.2 Lower bounding the error
Since M (Av) minimizes the MSE for estimating the signal w from the sketch, it implies a lower bound on the error that applies for any query responder the query distribution of Algorithm 1: Corollary 4.4. The mean squared error (MSE) on any estimator, even one that is tailored to h, M, and c, queries of the form [N, when ~ W is 2(2 (h, MY?).
We next establish that for any sketching matrix A E k random choice of signal index h E [n] and noise support (of size M that is slightly superlinear in k), it is likely that either column is all zeros (and hence any estimator must fail with constant probability) or oz M) = (k)). The proof is in Appendix C.

---

Lemma 4.5 (Lower Bound on Error). Let A E [xx((++)) be a matrix with m 2 20k log" k. Then, for at least 0.9 fraction of columns h E [m + 11, it holds that either Ash is all zeros or of (h, M [m 1J (b.)) Ω Flogk)
Recall that when the input vectors are k-sparse, exact recovery of the norm is possible, and hence there is no estimation error. Therefore, there is potential vulnerability only when the sparsity of the query vectors exceeds and thus our slightly super linear sparsity is necessary.
As a corollary of Lemma 4.5, we obtain a lower bound on the relative error guarantees of any estimator:
Corollary 4.6. Consider a fixed sketching matrix Let E R be a sketching matrix with n. = Ok log k). Consider the distribution of queries that samples h and M (of size m = Ok log k)) randomly from [n] and then sample query from M,, [w] where ~ W (and the density of W is least a constant range of size > 100/VBt Then with least constant probability, the MSE of any sketch-base based signal (and hence norm) estimator is Q1 (k log k).
Remark 4.7 (Error for JL matrices). Sampled matrices from the JL distributions meet this upper bound: For fixed noise support M of size m > k log k. with high probability over the sampling of A, for all h e [n)]. of M) (l1/k) (the property needed for the sampled that the projected rows A.M are close to orthogonal).
4.3 The gain lemma
We quantify the expected progress (towards an ad adversarial vector) in each step of the attack in terms of (h, M). What we show is that when the estimator has low error rate, then queries for which the noise component u has a higher deviation A,.M (Au) are more likely to have g(() = 1. Specifically, even though E[ (Au)) = 0 (as the deviation has distribution (0, )f))), the response s(t) is correlated with it and we will show that E[AA, (s(() Au]] xx 07, M).
Definition 4.8 (Error rate of sketch-based signal gap estimator). An estimator vb R - P(-111
map from sketch to a probability distribution on {-1, For a sketching map A E R h, M, e and signal distribution W, the error rate of sb for the a-iiinall gap problem (Definition 3.1) is the probability over the query distribution of an incorrect (1, a)- signal gap response:
err( (+)
[Pr(y (Av) 1) 1( 1) + Pr(y (Av)= -1] 1( 2 1 +
If Aoh 0 then any estimator would have at least a constant error rate. Additionally, from standard tail bounds. for error rate that is O()), must hold that a c0 cl((/oog(//)) and therefore or < a (l/c//oo((//)).
We therefore consider the case where Ast + and therefore unbiased Th, exists and of M) is well defined, and assume that or < Appendix D for the proof): Lemma 4.9 (Gain Lemma). If err(v)] < 8 and attack parameters are as in Definition 3.3, and σr < aa// lee/cc/loge (og((/))) then
We quantify the per-step expected gain (see
(l((AO)(T,NNAA)) - w)) = 22-00-lcoo(00
4.4 Proof of Attack efficacy Theorem
Proof of Theorem 3.2. The proof idea is to bound the deviation and the norm of the sum Ene(r) s(0) (t) and show that the deviation increases faster than the norm.
We first bound norm. We show that if the noise support sufficiently wide with m 22, then for any choice of ((9), the norm of Elery ((1) can not be much higher than that of the sum Eier) 200 of independent Gaussians:
Σ (0) (0)
-((F)
(4)
EE|T
7

---

This follows an immediate corollary of Lemma E.1.
We now consider the deviation of the sum. From Lemma 4.9 obtain that for each Ep(s A (Az(0))] = 0i of (h, M)).
From concentration of An. (that are independent (N0, of.)) we obtain that with high probability
Σ s 19 () = = (h,
(5)
From Lemma 4.5, for any sketching matrix A E R when sample h, and M [na] of size [2(k log k),, then with constant probability have (h, M) 9 Tog
Combining with (5) we obtain that
Σ (0 (Az( =
ra k log k
(6)
Combining (4) and (6) we obtain that with constant probability
<vra" k klog k
A (Az( = S2
For the deviation to exceed solving for vFa klog
7, we obtain r = k).
This concludes the proof.
Empirical study
We implemented Algorithm and evaluated its effectiveness on two families of sketching matrices: Gaussian Johnson- Lindenstrausss (JL) transforms [29] with A E Rxxn with i.i.d. entries Aij 1/0,1/k) and AMS sketches [3] with A {=1]<x= consisting of i.id. Rademacher entries (Ai =1 with equal probability). Our evaluation used different configurations of sketch dimension l and ambient dimension (effectively, the noise support). For each configuration applied the attack against the corresponding standard norm estimator and its robustified variant, and measured how rapidly the adversarial bias grows.
Standard Estimators. For Gaussian JL matrices, the standard norm estimator is simply the sketch norm, which coincides with the minimum-variame unbiased estimator for ||u||2 under Gaussian projections:
=
For AMS sketches, we implemented the median-of coiiiaan-o--mansss (MoM) estimator. Specifically, we partition the k rows of A into m [v]]} groups of equal size b = [k/g], compute the mean of y within each group, and take the median of the g group means:
| median
1 Vi IEG.
Σ
2
Σ
Σ
b
LEG2
VEG
Our final estimate is ||0||
V
10
Simplified attack We implemented simplified attack that sufficed for the special of JL/AMS matrices (distribution that invariant under column permutations) and query responders that are not adaptive and not tailored to the input distribution). Our query vectors [I.[ = 1] (see Eq. (3)), that is, use a fixed signal value w = and fixed h = n and M
sampled i.i.d. from
[n 1]. Observe that for query vectors, the norm || is concentrated around Vw² + = V2.

---

Robust Estimators. The robust variants are parameterized by noise scale and add Gaussian noise the squared-none -oom standard estimate before taking the square root:
(D) V ||el1 +00,
In our attack implementation the responder outputs & = 1 when 8, 2 1 + and 8 = otherwise."
On freshly sampled (non-adaptive) inputs, the estimator has standard deviation 1/v in the JL case, whereas for the robustified estimator the standard deviation increases to / + a². Therefore, the non-adaptive accuracy decreases with the robustmess noise
Experiments For each (k, n)) configuration sketch size and support size n, we performed rep = 20 trials. For each trial we sample a fresh sketching matrix A Æ We sample query vectors as described and apply estimators with different values of the robustness noise a E {0, 0.1, 0.2, 0.4) to the same query vectors (observe that a is the standard estimator). We study the effectiveness of our attack by tracking the ratio 8 (z(dd))) //1 //adv)]|2 ||2, where & the (respective) standard estimator that is applied the sketch and z g(adv) is the adversarial vector.
Results Fig. and Fig. report, for different configurations with &t E {100, 250, 1000), the ratio 8. (= / /||= (adv) l| (the y-axis) as function of the number of attack queries (the r-axis).
We observe that the attack is effective even in configurations with small support size of n/k E 5]. The standard and lower-o robust estimators are initially more accurate but also accumulate bias faster and incur much higher error the attack progresses. A larger sketch size k results in higher robustness (slower increase in the bias) for the same noise a. The plots show quadratic pattern where the bias induced by the attack increases like square root of the number of queries. Results for additional configurations for the same are reported in Fig. 3. We observe that the effectiveness of the attack tends increase with a larger support size
Discussion. Our empirical results demonstrate that the attack is substantially more effective in practice than our current analysis predicts. In particular, we observe strong empirical success even when the noise support size is very small-on the order of O whereas our analysis requires ((k2). The attack is also effective with relatively few queries, again beyond what is guaranteed by our theoretical bounds.
Moreover, our analysis only establishes that the attack product compromises the optimal estimator for the sketching matrix, which is linear statistic of the sketch. For JL sketches, the standard estimator is very close (up to row orthogonality) to this optimal estimator, so our theory is largely predictive. In estimator, which non-linear, yet the
contrast, for AMS sketches we employ median-of-mentt attack empirically compromises it with comparable efficiency. This suggests that the vulnerability extends beyond linear estimators and may be more fundamental than our current proofs capture.
333 5-3
Klach cilll bw200 LWDKO
Kluch L. 1210 wevce
jock
Matfoer of cann
Figure 1: Attack on JL with (ks n) E {(100, 500), (250. 1000), (1000, 5000)]- Standard and robust estimators. Mean ratio of estimate to actual norm with 95% confidence intervals over 20 repetitions.
'Our simplified attack would fail against a fully strategic responder that is tuned the input distribution and always returns the deterministic value Vi² + = /2. Such responder leaks no information about the sketching matrix and is correct with high probability all queries.

---

Sanur yod
Davitiss
Figure 2: Attack on AMS with (k, n) E {(100, (250, 1000), (1000, 2000)). Standard and robust estimators. Mean ratio of estimate to actual norm with 95% confidence intervals over 20 repetitions.
Acack Ju L-256 2-20
Acl andd
Not
Ouarte
Figure Attack on JL with (k, E {(250, 500), (250, 2000), (1000, 10000)}. Mean ratio of estimate to actual norm with 95% confidence intervals over 20 repetitions.
Conclusion
Our results further suggest that vulnerability to black-box attacks is inherent consequence of dimensionality reduction. Nonetheless, it can be partly mitigated by sacrificing some non non-adaptive accuracy in exchange for increased robustness, underscoring fundamental trade-off. We close with several directions for further investigation.
Theory questions. We proved tight, quadratic-size universal attack that succeeds against any query responder, but our analysis only guarantees compromise of the optimal (linear) estimator for the sketch and attack distribution. Empirically we observed that our attack compromised also the non-linear median-od of-me estimator for AMS. This suggests exploring broader applicability of attack. Another natural question is whether our technique Gribelyuk et al. [23]. A more ambitious goal is to construct a quadratic-size attack that generates a single distribution capable of compromising every query responder. Such an attack would necessarily require 52())) adaptive batches and could plausibly build on enhanced version of our construction that incorporates the discovered adversarial directions into the input distribution [16]. Another open question concerns the required size of the noise support, which directly corresponds the attacker's storage cost. Our current proof requires n = 22222) because it relies on general bound (Lemma E. 1) for arbitrary signed sums of Gaussian vectors. Empirically, however, we observe that our attack remains effective with support small as 2k, and we conjecture that Ö(k) support should suffice.
be extended to other norms, in
Connections to Image Classifiers. Our findings on the vulnerability of linear sketches may shed light the phenomenon of adversarial examples in image classification, which has been extensively studied in prior work [37, 21, 4, 34, 32. 35]. Many of these attacks exhibit a striking structural similarity our setting: they construct adversarial examples by aggregating small, randomly oriented perturbations that consistently push the system's 's output in a particular direction. When normalized and accumulated, these perturbations yield large, adversarial deviation that fools the model. This additive, alignment-based mechanism appears to be remarkably effective across domains.
Although image classifiers such as CNNs are highly nonlinear, they contain significant linear com- ponents, particularly in early layers. This observation raises a natural question: could adversarial susceptibility in image models arise, least in part, from the same Iireanity-driven accumulation of aligned noise? If so, it may be possible to improve robustness by introducing carefully designed randomness-sur as injecting noise that unknown the attacker into internal representations or into the input.
10

---

Acknowledgments
Edith Cohen was partially supported by Israel Science Foundation (grant 1156/23). Uri Stemmer was Partially supported by the Israel Science Foundation (grant 1419/24) and the Blavatnik Family foundation.
References
[1] Sara Ahmadian and Edith Cohen. Unmasking vulnerabilities: Cardinality sketches under adaptive inputs. In JCML, 2024. URL https: org/ 10. 48550/arXiv.... htt//aravvvv... 2405. 17780.
[2] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via lin- ear measurements. In Proceedings of the 2012 Annual ACM-SIAM Symposium on Dis-
crete Algorithms (SODA), pages 459-467, 2012. doi: 19111337719781111979700 https://epube: siam. arg/doi/ab//10. 113771.998611119733994444
URL
[3] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58:137-147, 1999.
[4] Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adver- sarial examples. In International conference on machine learning, pages 284-293, PMLR, 2018.
[5] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. CoRR, abs/2107.14527,, 2021.
[6] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput., 50(3), 2021. doi: (0.1137/1M1100344 URL https /
/ttpss///oo..org/1110 org/10. 1137 16M1103646.
[7] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. CoRR, abs/21 .03980, 2021.
[8] Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense- sparse trade-offs. CoRR, abs/2109.03785. 2021.
[9] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. SIGMOD Rec., 50(1); 2021.
[10] Guy Blanc. Subsampling suffices for adaptive data analysis. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 999-1012, ACM, 2023. doi: 10.1145/
3564246.3585226, URL https: /t////dooo/ doi. org 10 1155.11141/14..35555551 358162222226635226..
[11] Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 5 42(12)54003-2215, 2005.
[12] Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020.
[13] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 41 12-4140. PMLR, 2022.
[14] Edith Cohen, Jelani Nelson, Tamas Sarlos, and Uri Stemmer. Tricking the hashing trick: tight lower bound on the robustness of countsketch to adaptive inputs. Proceedings of the AAAI Conference on Artificial Intelligence, 7735-723, Jun. 2023. doi: 10. 10.1669//aai.v3/7 25882. URL https:/ //tjs//j..... aaai, org index phtp whpppppppp////eeeeeeeew/p WAAI/article/vieee 25882.
11

---

[15] Edith Cohen, Jelani Nelson, Tamas Sarlos, and Uri Stemmer. Tricking the hashing trick: A tight lower bound on the robustness of countsketch to adaptive inputs. Proceedings of the AAAI Conference on Artificial Intelligence, 57(6):7235-7243, Jun. 2023. doi: 10. 10.16/99aaii httss::p:: //otttss://os...
25882.
orge wwwpddee.pppppaeeee phtpppppp//aaaaaaea http//AAA//rricel/eiieeeee 25882..
[16] Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, and Uri Stemmer. One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches, arXiv preprint MXXi:2241.003777 2024.
[17] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In STOC, pages 117-126. ACM, 2015.
[18] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi. Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty- Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page 117-126, New York, NY. USA, 2015. Association for Computing Machinery. ISBN 978 9781450335366 doi: 1145/27 2746580.
10.1145/274633. 2746500.. URL https://doi.
[19] David A. Freedman. A note on screening regression equations. The American Statistician, 37(2): 152-155, 1983. doi: 10. 000100000000311055111811 10482722. URL https: /www tandf online. com/doi/abs/10 10000000//000 1080/00031305, 1983. 10482729.
[20] Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in o(m log² n) time. In ICALP. volume 168 of L/PIcs, pages 57:1-57:15, Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020.
[21] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6522 2014.
[22] Elena Gribelyuk, Honghao Lin, David Woodruff, Huacheng Yu, and Samson Zhou. A strong separation for adversarially robust to estimation for linear sketches. In Proceedings of the 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024. URL
https: //ap:i////a/iva///aa www/oogg//....o 2adf/2400 /2009.409 16153.
[23] Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. Lifting linear sketches: Optimal bounds and adversarial robustness. In Proceedings of the 57th ACM Symposium Theory of Computing (STOC '25), pages 406,406, 2025. doi: 10. 10.1145/3717823.
3718 3718227.
[24] Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, page 2542-2561, USA, 2020. Society for Industrial and Applied Mathematics.
[25] M. Hardt and J. Ullman. Preventing false discovery in interactive data analysis is hard. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 454-463. IEEE Computer Society, 2014, doi: 10. 109/FOCS.2014.55
https://:
Leeecomppttrssociety org/ 1109/FOCS. 2000DC..001..55. 20.4.55.
[26] Moritz Hardt and David P. Woodruff. How robust are linear sketches to adaptive inputs? In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 121-130, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. doi: 10. 00.1145/288608.24444 2488608. 2488624.
URL. https:://///o/ http:///dooooo//..11111 1145/
[27] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversari- ally robust streaming algorithms via differential privacy. In Annual Conference Advances in Neural Information Processing Systems (NewrIPS), 2020.
[28] John P. A. Ioannidis. Why most published research findings are false. PLoS Med, (2):8, 2005.
[29] William B. Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. Contemporary Mathematics, 26:189-206 1984.
12

---

[30] E.L. Lehmann and G. Casella. Theory of Point Estimation. Springer, 2nd edition, 1998.
[31] Paul M. Lukacs, Kenneth P. Burnham, and David R. Anderson. Model selection bias and Freedman's 's paradox. Annals of the Institute of Statistical Mathematics, 62(1):1 17, 2009.
[32] Aleksander Madry, Alcksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018. URL https: //arxiv. org/ h//g//////// abs/1706.... 06083. 3xiv:1706.06083
[33] nya Mironov, Moni Naor, and Gil Segev. Sketching in adversarial environments. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, page 651 151-660, New York, NY. USA, 2008, Association for Computing Machinery, ISBN 978160558044 doi:
10. 10.1145/1374336633444771. URL https:://ool 10./10. 1145/1374376 1374471.
[34] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Anan- thram Swami. Practical black-box attacks against machine learning. Proceedings of the 2017 ACM Asia conference computer and communications security, pages 506-519, 2017.
[35] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, ed- itors, Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019. URL https: httttpp:///procceddngss neurips iaapprrfilees httpe//flleeeapp/2//1900000 pappr//019//111/11 55222256770022252266111111133343 Pwper.
[36] Yossi Shiloach and Shimon Even. An on-line edge-deletion problem. J. ACM, 28(1):1-4,jar 1981. ISSN 0004-5411. doi: 10. 10.1145/3222343222333 URL https://doi. org/ 10. 1145/ 012234.322233
[37] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6199, 2013.
[38] Roman Vershynin. High- DigneeDimnsional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, UK, 2018. ISBN 9781 108415194. doi: 10.1017/978 108231596.
[39] David Waje. Rounding Dynamic Matchings against Adaptive Adversary. Association for Computing Machinery, New York, NY, USA, 2020. URL httpt:///doi: orggiiorg//1 1145/ 3357713. 3384258.
[40] David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In Proceedings of the 62nd IEEE Annual Symposium Foundations of Computer Science (FOCS), 2021.
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims reflect the contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We explain that what we are doing is what we can hope do single-batch
attack.
14

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, authors should discuss possible limitations of their approach to address problems of privacy and faireess
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Most of the proofs are in the supplementary but ideas and sketches are contained in the main body.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We included very light weight experiments as demonstration. This is a theory paper. We disclose everything needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
There is no data and the code is very minimal and easy to redo.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. //wips.ccppublll/ https//cpppbclcguueeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
We do not do any model training. We only implemented a version of our Algorithm 1.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We report results of few repetitions in our demonstration.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Experiments are simple and light weight
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //pprris///urips...// ctpss.cc//oo ccc/publiccEthicsuuie dnee???
Answer: [Yes]
Justification:
We believe we did.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This is theory paper exposing some vulnerabilities in dimensionality reduc- tion. There is no direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not applicable
Guidelines:
18

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We only used standard python libraries.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new datasets or code. This is a theory paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
19

---

Justification:
Not applicable
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
We did not use LLM beyond editing, formatting, and such.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: http://neuii.pp.eee cc/ http://errpp...c//o//eeeeeeeeeee for what should or should not be described.
20

---

A Norm estimation to signal estimation
This section contains a restatement and proof of Lemma 4.1:
Lemma 4.1 (Norm gap signal gap). With the choice of parameters for for attack and m Qi(k + r) log((k + r)) with probability close to correct (1 è², 1.l.x)--ormm gap outpu implies correct -iignall gap output all queries.
Proof. The query vectors v = wew + cu sampled in Algorithm are from distributions [[(]) for w E [a, b). The squared norm is || = w² + + | around its expectation 1:
We show that || tightly concentrated
Claim A.1 (Concentration of | 2
Pr
| 11/2 é S 2e 2e- (2)
Proof. The sum of the squares of i.i.d (O, d²) has distribution a² x²x and expected value mo? Applying tail bounds on Xm (Gaussian concentration of measure) we obtain that for c E (0,
|
mo²
Pr
2 E
S 2e (2)2))
mo?
Substituting o² 1/m we obtain the claim.
It follows that if we choose our queries, the squared norm of the noise is within |/ E (1 1/(10v/).. Therefore, correct (1, aa- output on the norm yields a correct (1, a² + 2app on the squared norm ||v 12. This gives an (1 - e² (1 + 1/(10/k)), a² + 2a c² (110/k) output on the squared signal 2
Q((k + r) log((k + r)/5)) then with probability 1 - 6, all
We now note that we can assume 1/V/ because otherwise, any responder would be incorrect with constant probability. Using our parameter setting of l close to I and fixed e < we obtain the claim in the statement of the lemma.
B Estimator for the Signal
This section contains a restatement and proof of Lemma 4.2.
Lemma 4.2 (Estimator for the Signal). Fix (n), noise support set M C [m] \ (h), and a noise scale factor c. Consider the distributions M., parametrized by w.
If the column Ash is nonzero, then there exists unbiased, complete, and sufficient statistic Th.M R + R for the signal w based on the sketch Av.
Furthermore, the deviation of this estimator from its mean, defined as
Ah.M (cAu) == Th, (Av) W.
depends only on the sketch of the noise u NN, and is distributed as a Gaussian random variable (10,c oz (h, M).
Proof. If the column A.h. is zero, then the sketch contains no information on the signal w and unbiased estimation is not possible. Otherwise, our goal is to express the unbiased sufficient statistic Th. (Av) for the unknown scalar w.
Because row operations preserve the information a sketch, there exists an invertible matrix G E & such that for A' = GA,,
the transformed column h has value 1 in the first row and 0 elsewhere: 4i, 1 and AG, 0 for 1; and
every row AlM for i > of the submatrix restricted to the noise coordinates, is either orthogonal to the first row Afas or is the zero vector 0.
21

---

Since G is invertible, A' is equivalent to the original sketching matrix A in that we can obtain the sketch A'v from Av and vice versa.
We specify a sufficient statistics T in terms of A'u (so that (Av) = T(GA))) Consider the distribution of the sketch y = A'o GAv for wen + cu where Na,ar. We have w + jEjEM M Alzuz, hence it has distribution
cN(w, of), where of = || 12 1
m
From orthogonality of the rows A's restricted M, the random variables y; are indepen- dent of A' and hence convey information on w. The information on the signal to in the sketch, and the unbiased sufficient statistic is therefore 1/1 = (GAv)), which has distribution (7) and is an unbiased estimator of w.
To establish the claim for the additive error, note that
M (cAu)= = ah (Av)) - w = (GAv)) - w = (cGAAu)1
C Proof of Lower Bound on Error Lemma
This section contains a restatement and proof of Lemma 4.5.
Lemma 4.5 (Lower Bound on Error). Ler [=(((++1) a matrix with m 2 20k log Then, for at least 0.9 fraction of columns h [m + 1], it holds that either Aoh is all zeros of (h, M [m + 1I (h}) = Ω logg
We will use the following technical claims Definition C.1 (Fragile Columns). Let A E R*x"" For each column / E [m]. define
K₁ {i [k] Aa # 0}.
byh = { E [m] A 2 Al,
the set Kn of active and the dominated number bin of each active row. Let i Kn.
(h)
(h)
(h)
C2
Kaa
be the nondecreasing rearrangement of (bar ::E Kn We say that a column h is fragile, if:
im
V1 visis Kyl: &
2
10k log, k
Note that zero columns are fragile by definition.
Claim C.2 (Most Columns are Fragile). m > 2h log, is then at least 0.9m of the columns are fragile.
Proof. We look at [loge k] ranges of ba values where Ri = [1...., 10k inga
m
and Rd =
- 24-2,2% 2,2) Tok log, for >
We say column is strong for range if it has 2 or more bis values in Rg That is, ( bin E R, 20-1, Clearly if column h is not fragile then it must be strong for some range but the converse may not hold.
We bound the number of distinct columns that are strong for at least one range t. This bounds the total number of non-fragile columns.
Consider range t = 1. Each of the k rows contributes the columns of its 10k log, k largest entries. So the total number of columns that can be strong for range 1 most To
m
Now consider > 1. Each row has at most 2
10k log, k distinct columns with b.g. E R2 But for column to be strong for it has to participate in 2 such rows. So total, the range contributes most T0 logg x) strong columns.
m
22

---

Summing over all ranges, we obtain bound of m/ 10 on the total number of columns that are strong for least one range. This also bounds the number of non con-fragile columns. This concludes the proof.
IT
Claim C.3 (Nearly to fully orthogonal rows). independent and satisfy
((k) E R_ for k 2 1 be linearly Let v11),
(0 01)
(i ():)
| |2> > i(2 Ink
(d.,,...,kk) n.).
Then there are orthogonal (1)), u such that (1) (2), and
1 ( || ||e ( ||3 > i(1 In k)
(i 2, ...... k)
u (1) is an affine combination of v (1) (i-1)
(i 2,.... k)
Proof. We construct vectors u (2)
u (k) in order using the following operations:
(v((), (0)
(
j=l
5 ())
(1)
(o xااس
1
We establish the claim by induction on i. The claim clearly holds for = 1.
Assume it holds for i. Then (0) Ejm The ( where Ej=1 Tzz Therefore for all h
(0(h) (0) = Σ
2e (1)(0(0))0)) = Σ My =
==1
Therefore
(++1) = v(++))
Σ
| 12 i0
5=1
Using orthogonality of (u++)) joss obtain:
a 1 ||
1
10
i (1 Ink) 2 1 1.
(using upper bound on the Harmonic sum).
The scaling of ū ( ensures that (()) is an affine combination of (()) and (u()) Since by induction each (1) for j < is affine combination of (v(*)) combining we obtain that so is (t)
The scale factor is s; 1 - Ej= (1+lak)) (0, 1]. Therefore,
| x
|| 12 1.
Proof of Lemma 4.5. We first give characterization of o (h, [m + 1] {h}) that we will use, and follows from similar argument to the proof of Lemma 4.2. Let G E R be invertible so that the column GA has only values (0. 1) and the rows of the submatrix GA, mm+1]((A) with column
h removed are orthogonal. Then
Σ
m |GAA, 11
(8)
o (h, im 11 (b])
&GA.
23

---

We assume, without loss of generality, that the rows of A are either orthogonal or O. From Claim C.2, it follows that most columns of fragile.
We now fix a nonzero fragile column h. We scale the rows so that A are in f0, 1). Note that the fragility of columns is invariant to rescaling of rows. From fragility, and with the rescaling, the squared norms of the rows in increasing order are at least
km
10k log
We now consider the submatrix B | Imn E R of A with column h removed and all
rows which column was not active are removed. Let the rows of be v and observe that from orthogonality of the rows of A and from the fragility of h, the vectors satisfy the conditions in the statement of Claim C.3. Therefore by applying the claim we obtain a matrix B' (with row vectors u² that are orthogonal, are affine transformations of the rows of B, and that
10k log k im
k loggg k O
Σ B
m
It follows that if applied the same transformations with the column h, the column would be invariant. The matrix A' with column A with substituting the matrix could be obtained using the same transformation. This matrix satisfies the conditions of the characterization and by applying (8) we obtain (h, {m + (h} = 2 (oggg) and this concludes the proof.
D Proof of the Gain Lemma
This section contains a restatement and proof of Lemma 4.9.
Because M M is a sufficient statistic for the distribution of the sketch Av, conditioned on Th.M (Av) (G(h.M) Av)1 т, does not depend on Let f- R be the density function of this distribution.
We can thus express the expected value of vb conditioned on the value of the statistic Th.M(y) = (as it does not depend the signal value w):
(T)): - f (1y)f+
M(())
dy dy
(9)
We express the error rate of va (see Definition 4.8) terms of and o²::
/''
L Vww
+ +1
err(v)=
Po, 20 (z) dr (w) du
(10)
JR
b
V(w x)
Po,0 23 (1) dx dw dw,
2
1+
where v(w) be the density function of the distribution W on the signal (see Definition 3.3) and 60,003 is the distribution of the deviation (see Lemma 4.2).
Lemma 4.9 (Gain Lemma). If err < 8 and attack parameters are as in Definition 3.3, and σT a/ (a//////////a (cy (lg()/)) then
(A - w)] = (laaa'ccorhh (c,
Proof. We bound from below the expected value, over our query distribution, of
((A (Av) w) cd((Av)An. (Au).

---

We express the expected value of ab over our query distribution, conditioned on the deviation A (cAu) = x:
Po (x) S-" Viw + x) (2) v(w) du
E [bb) (n,rr(AAu) = x]
V(w + x)) v(w) dw
b+z
(ww) v(w x) dw.
(11)
atr
We express the expected value of An over our query distribution.
El
E =
x E (((( (nAur(AAu) = x]]
(f Jatz
b+z
330,0"03 (x)
V(w) x) dw dx
using (11)
b-x
24Puct0f(1) (x)
((w))((w x) dw
ja-z (w) v(w + x)) dw dx (12)
Jatz
(using that yp is symmetric function).
We separately bound the parts of the integral in (12) due to x E [a, oo] and x E [0.
We first consider E [a, oo]. Since y is density function and | < 1, the absolute value of the difference expression is bounded by 2. Hence,
cc
(12) due to x E (ax, 20|1 2 x40,e'033 (z)
exp( (a/(-(a//))))))
2m
We now bound the contribution to (12) due to x E [0, a). We use the following:
Claim D.I. For xr E [0, a] and assuming err(v) S 0.05 and our setting of a, b,
b+C ((w) v(w 2) dw
sー /- ((w)v(u + +2) ((w))(w22)d dw 2lca 1x).
(13)
atx
a-x
Proof. We break the range integration into parts according to the density function v (see Defini- tion 3.3) and bound each part.
25

---

b+o
b-z ((w) v(w 2)dw du Io (w) v(w x)) du
(14)
((w) v(w + x) dw
(15)
a-
((w) (v(w x) =nw + x)) dw
(16)
V(ne (v(w x)- v(w + x²) du
(17)
1-x
1+a-x
V(w) (u(w x) vww x)) du
(18)
1+x
lttts
+
((w)(((u) - x) - v(w + x)) dw
(19)
+ta-x
Vlw) (v(w x) -v(w + x)) du
(20)
1ta=x
btr
+
v(w)v(ww x) dw
(21)
We now bound each part. We use that C ((e/a) and (1 (1- (1- - (1+ a) = O(a/c).
((15) S C 4x²
O
a xx²)
1-a
1-=
C
C 1-x
(16)
(ww)
(-2r
dw -2x
((w) dw 2 0.1ca
Jaz
1-a a
atz
(17)),(199) s 20x² 0(ca-112"
(18) = 0
C
b-z
(20) 2x
v(() du -1
b (1 ++a
11444
4r
(21) s b - (1+
=0(e² a 22
Our bounds for (16) and (20) use that for with error at most 0.05 and x E [0, at). holds (with our choices for b) that f (w)dw 00.1 - a), firat (w)dd > 0.1 (1 + a)). O
(12) due [0, /." xrPuctt3 (z) (c) =Q(eaa -112)-107))
(22)
Combining (22) and (13) we establish the claim in the statement of the Lemma: (12) = 2(a -1 ca c077)
E
Signed sum of Gaussian vectors
Lemma E.1 (Upper bound for the signed sum of Gaussian vectors). Let X,,...,,, X, Lid Nn, (0.1)
in R m Define
Σ s sxx.||3
M = max =E(1))-
1=1
26

---

Then for every >> 0
PH[M M & (V++ vm
2 1 - 22 -1/22
In particular,
S 2r + vrm
with probability 1 T1/2
Proof. Collect the random vectors into the Gaussian matrix X sign vector E {+1} have
[1 X₂) IR IRmxr. For any
Σ s;X; X8,
hence
[ l|2 S mmax (X) |8|12 = max (X) VT,
where mmax (X) is the largest singular value of X. Since this holds for all s, we get
M S max (X) VT.
(23)
For an m x r matrix with i.d. NiO,, 1) entries, applying the standard concentration bound (see, c.g., Theorem 4.4.5 in Vershynin [38]) we obtain
Pr(o (X) 2 V Vm +1 - 2e 12
(t>00 0).
Combining this bound with (23) yields the first stated probability bound. For the simplified bound, we plug-in = vf in the above.
27


Reviews:
[{"review_id": "Rv98eIXwgn", "reviewer": "Reviewer_wnnW", "summary": "- This paper studies the problem of constructing adversarial inputs to linear sketches for the task of L2 norm estimation\n- The presented attack is a universal, non-adaptive attack using $\\tilde{O}(k^2)$ queries, where $k$ is the dimension of lower-dimensional projection\n- Compared to prior work, this paper works for any sketching matrix (whereas prior work focused on JL/AMS constructions), and also is universal (whereas previous work may only work for some estimators)", "questions": "See weaknesses", "limitations": "See weaknesses", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n- Good presentation\n- Clear contribution over prior work, reducing the number of queries for general sketching matrices to quadratic (whereas prior work work used more specific information about the sketching matrix)\n\n\nWeaknesses\n- Empirical verification only done for JL sketching matrices with Standard/Robust Estimator, should at least include some other sketch constructions\n- Attack requires that the estimator is optimal with respect to $\\mathcal{D}$ and $A$. How this can be generalized to non-optimal responders is not clear", "was_revised": true, "final_justification": "I have read the other rebuttals/responses. The authors have clarified concerns from all reviewers and clarified the future works sections, and there seems to be a consensus that the contributions of this paper are significant.", "rebuttal": "We thank the reviewer for their time and helpful comments!\n\n### W1 **“Empirical verification only done for JL sketching matrices with Standard/Robust Estimator, should at least include some other sketch constructions”**\n\nWe plan to add experiments with AMS sketching matrices and the standard (median based) and robustified estimators. We expect to see similar behavior to JL.\n\n### W2 **“Attack requires that the estimator is optimal with respect to $D$ and $A$. How this can be generalized to non-optimal responders is not clear”**\n\nThe attack works against *any* responder, even a strategic one with full knowledge of the attack strategy. However, the product of the attack is statistically guaranteed to only fail the optimal estimator with respect to $D$ and $A$.  A nice property of our attack is that it works in a very limited model of single batch (=  non adaptive) and produces a single adversarial input.  To be effective against strategic estimators that are tailored to the attack strategy and adapt to the actual queries, we must use fully adaptive attacks with $O(k)$ rounds of adaptivity. It is an open question whether there exists such a quadratic size attack.\n\nThat said, we suspect that our current attack is effective against a wider class of non-strategic (fixed) estimators. To establish this with this form of attacks (that remarkably are similar to attacks on image classifiers) we need (for the final compromised estimator) to be able to relate its responses on queries in a weak way to the response on their linear combination. Linear estimators do that, but the hope is to specify a more general condition. These are questions for followup works."}, {"review_id": "PlpD7uJPlQ", "reviewer": "Reviewer_5Z34", "summary": "The paper presents an attack against linear sketches that aim to preserve the $\\ell_2$ norm, showing that after a quadratic number of queries, norm estimation can be compromised.\n\nFormally, the paper considers an attacker, a responder, and a fixed but unknown matrix $A \\in \\mathbb{R}^{k \\times n}$, which is hidden from both parties. In each round, the attacker generates a query vector $v \\in \\mathbb{R}^n$ and submits it to a black-box system. The responder receives the sketch $A v$ and must decide whether $\\|v\\|_2 \\le 1$ or $\\|v\\|_2 \\ge 1 + \\alpha$, for some fixed $\\alpha > 0$.\n\nThe main result shows that there exists a family of distributions over $\\mathbb{R}^n$ such that, if:\n1. The attacker randomly selects a distribution from this family and samples vectors $v$ accordingly, and\n2. The responder is aware of the distribution being used,\n\nthen after $\\tilde{O}(\\gamma^2 \\alpha^{-2} k^2)$ rounds, with constant probability, one of the following occurs:\n- The responder makes a constant fraction of errors in their binary decisions, or\n- The attacker can construct a vector $u$ such that the optimal estimator (with respect to $A$ and the chosen distribution) returns a value outside the interval $(1 \\pm \\gamma)\\|u\\|_2$.", "questions": "1. The setting introduced on Page 2 involves only two parties: the adversary and the responder. However, the attack–defense framework appears to implicitly involve a third party—namely, a “system” that computes $A v$ for each query vector. This system acts as a black box accessible to both the adversary and the responder.\n\n    This third entity is not formally introduced in the initial setup but becomes explicit on Page 5, where the paper describes each step of the attack (e.g., Line 166). Clarifying the role of the system earlier in the paper would help readers better understand the interaction model and the assumptions about information flow.\n\n\n2. The experimental section includes standard estimators for the Johnson–Lindenstrauss (JL) transform. \nHow does the proposed attack compares to prior methods designed to target these estimators, as discussed in the introduction.", "limitations": "See weakness and questions.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. Dimensionality reduction is widely used in data analysis and machine learning. Understanding when and how it fails contributes to our broader understanding of the stability and limitations of existing models.\n\n2. The proposed attack is agnostic to the underlying matrix $A$, and the number of queries required matches existing bounds for answering adaptively chosen queries accurately.\n\n3. The writing of the paper could be significantly improved. \n    * Several notations are introduced before being properly defined, which hinders readability. \n        For example:\n        - Line 41: the symbol $\\psi$ is used without a prior definition.\n        - Line 100: the meaning of $\\delta(\\alpha)$ is unclear.\n        - Line 120: the $W$ appears without explanation.\n\n   * Additionally, the technical overview in lines 119–123 of the introduction refers to the algorithm's pseudocode, which is not presented until two sections later. \n   This makes it difficult for the reader to follow the intuition behind the approach at an early stage.\n\n   * The figures in the experimental section are difficult to read due to the text being too small. \n   Axis labels, legends, and annotations should be enlarged to ensure readability.", "was_revised": true, "final_justification": "I trust these clarifications will be reflected in the final version to enhance readability. I will keep my score unchanged.", "rebuttal": "We thank the reviewer for their time and helpful comments\\!\n\n### W1 (improve the writing). We will address all comments, thank you\\! \n\n### Q1  **“The setting introduced on Page 2 involves only two parties: the adversary and the responder. However, the attack–defense framework appears to implicitly involve a third party—namely, a “system” that computes $Av$  for each query vector. This system acts as a black box accessible to both the adversary and the responder.”**\n\nResponse:   We added “system” to the description of the interaction in page 2\\. We initially attempted to streamline the description, but changed that as the reviewer found it confusing.\n\n### Q2   **“The experimental section includes standard estimators for the Johnson–Lindenstrauss (JL) transform. How does the proposed attack compares to prior methods designed to target these estimators, as discussed in the introduction”**\n\nResponse: We used simplified attacks, as explained, in the empirical section since we only attacked the standard and non-strategic robust estimators (we did not sample signal value).  Our simplified attack on the standard estimator is similar to the attack used in \\[Cherapanamjeri and Nelson NeurIPS2020\\]. One difference is that the CN20 attack was in terms of distance estimation: The generated queries  did not have a signal component; The responder compares the estimate of the distance to $e\\_1$ to the estimate of the distance to $-e\\_1$; and the result of the comparison determines the sign multiplier for forming an adversarial vector. The construction of the adversarial input in CN20 is also similar (and also similar to attacks from other domains including image classifiers): A signed sum of query vectors."}, {"review_id": "NFlqFxf33o", "reviewer": "Reviewer_c6SG", "summary": "This paper investigates the robustness of linear sketching methods for ℓ₂ norm estimation under black-box adversarial settings. The authors propose a universal, nonadaptive attack that applies to any sketching matrix and query responder, including randomized and adaptive ones. The attack constructs a carefully designed distribution over sparse signals with additive Gaussian noise, and—using only $O(k^2  log^2⁡k )$ queries—either induces a nontrivial error rate in the responses or constructs a vector that misleads the optimal estimator tailored to the attacker's query distribution. Theoretical analysis demonstrates that this query complexity is tight, and preliminary experiments confirm the trade-off between robustness and estimation accuracy.", "questions": "1. Is the $Ω(k^2)$ noise support size a theoretical necessity, or could it be reduced empirically without compromising effectiveness?\n\n2. Consider removing the redundant restatement of Theorem 3.2 on Line 273 in Section 4.4, as it adds little new content.\n\n3. While the authors claim that their result is “practically relevant,” the paper does not elaborate on the specific real-world scenarios or applications where such an attack might be impactful. A more concrete discussion of the practical implications of adversarial norm estimation in sketch-based systems would help contextualize the contribution.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Clear problem formulation: Definitions such as the (1, α)-gap problem (Definition 3.1) and adversarial noise vector (Definition 4.3) provide clean abstraction layers for analysis.\n\n2. The paper offers a clean theoretical framework, with precise definitions and proofs.\n\n3. The proposed attack is compatible with any sketching matrix and query responder, including randomized and adaptive estimators (Lines 125–126), demonstrating strong generality under minimal assumptions.\n\nWeaknesses:\n\n1. Some parts of the paper contain unnecessary redundancy; for example, Line 273 in Section 4.4 restates Theorem 3.2 in a way that duplicates prior content without adding new insight.\n\n2. Proof presentation could be improved: Key results like Theorem 3.2 are explained informally with phrases like “the idea is to show...” (Line 279), lacking formal structure and transitions.\n\n3. The attack's failure guarantee applies only to the optimal estimator aligned with the attack distribution and sketch matrix, and does not extend to arbitrary estimators, limiting its generality in practice.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and helpful comments! Our final version will address all the points listed under “weaknesses.”  \n\n---\n\n### Q1: *“Is the $\\Omega(k^2)$ noise support size a theoretical necessity, or could it be reduced empirically without compromising effectiveness?”*\n\n**Response:**  \nOur empirical attacks were effective with a much smaller support size: for $k = 100$ we used $n = 1000$, and for $k = 1000$ we used $n = 20000$. It is likely that even smaller supports would suffice, and we plan to extend our experiments to verify this.  \n\nWe also conjecture that the theoretical bound on support size can be improved. The only part of our analysis that requires a quadratic bound (as opposed to linear in $k$) is one lemma concerning the signed sum of Gaussian vectors under a “worst-case” choice of signs. This condition may be unnecessarily strong for query responses, and tightening it remains an open problem.  \n\n---\n\n### Q2: *“Consider removing the redundant restatement of Theorem 3.2 on Line 273 in Section 4.4, as it adds little new content.”*\n\n**Response:**  \nThank you for pointing this out — we will remove the redundant restatement in the final version.  \n\n---\n\n### Q3: *“While the authors claim that their result is ‘practically relevant,’ the paper does not elaborate on the specific real-world scenarios or applications where such an attack might be impactful. A more concrete discussion of the practical implications of adversarial norm estimation in sketch-based systems would help contextualize the contribution.”*\n\n**Response:**  \nWhen we describe our results as “practically relevant,” we are referring to the broader family of “sketch-based systems.” In their simplest form, sketches are used end-to-end — e.g., on network logs or streaming data — where an estimator is explicitly applied to approximate exact quantities. However, sketches also appear as **components** within more complex systems. For example, dimensionality reduction frequently appears as “bottleneck layers” in deep neural networks, where components learn to detect specific features and may implicitly estimate norms or proximities to other components or baselines.  \n\nAs we discuss in the paper, what we find striking is that the attack format — combining noise vectors with signs correlated to predictions to produce an adversarial direction — appears effective across domains, including highly non-linear image classifiers. Understanding this phenomenon in a unified way, identifying its intrinsic causes, and exploring potential mitigations is valuable. Norm estimation on linear sketches provides a clean setting for such exploration."}, {"review_id": "IeMlYXFxaX", "reviewer": "Reviewer_ctJN", "summary": "This paper designs a **non-adaptive**  attack against linear sketches for the $\\ell_2$ Norm Estimation problem. It starts with a batch of $\\tilde{O}(k^2)$ non-adaptive queries. Upon receiving all query responses, an attack query is generated based on those responses, which is guaranteed to compromise the $\\textit{optimal estimator}$. The $\\tilde{O}(k^2)$ batch size nearly matches the $\\Omega(k^2)$ upper bound achieved by JL transforms and AMS sketches, thus is nearly optimal. \n\nConcretely, each query vector is sampled as $v_i = w_i e + u_i$, where $e_h$ is a random, fixed basis vector, $w_i$ is an independent weight drawn from a carefully designed distribution, and $u_i$ is an independent Gaussian noise supported on a random subset of $[n]$ of size $\\tilde{O}(k^2)$. then the attack vector is a weighted sum of the noise vectors, where the weights are the query responses. The authors  prove the effectiveness of such an attack by showing that (1) the optimal estimator for the signal weight is a complete, sufficient statistic whose deviation is Gaussian, and (2) as long as the estimator does not err by too much, each query contributes an expected ''gain'' in aligning the weighted sum with an adversarial direction. This leads to the eventual failure of the estimator.", "questions": "1. There are many recent works on attacks against sketching / streaming. Has a non-adaptive “batch” attack model similar to the one in this paper been considered previously?\n\n2. The paper suggests, as a future direction, reducing the Gaussian noise support from $O(k^2)$ to $O(k)$. Beyond satisfying aesthetic bounds, does a smaller support lead to any concrete efficiency or robustness benefits for the attack?\n\n3. In adversarial streaming, Gribelyuk et al. (2025) extends L2 norm estimation lower bound to taks such as Lp norm, operator norm, and eigenvalues estimations. While this paper investigates a different attack model, does the result similarly generalizes to tasks beyond L2 norm estimation?", "limitations": "Yes, the limitations are clearly discussed. The authors also point two potential future directions, which are\n- designing attacks that compromise $\\textit{every}$ query responder (beyond the optimal estimator considered in this paper), and\n- reducing the support size of the Gaussian additive noise from $O(k^2)$ to $O(k)$.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strength**:\n1. The non-adaptive ''batch'' attack model considered in this paper feels both intuitive and neat. And this paper studies the lower bound for the L2 norm estimation problem in this setting, which is arguably one of the most important problem. Although the bound holds only against ''optimal estimators'', one can imagine many use cases when the query responder is indeed an optimal estimator, thus I find the contribution of this paper clear.\n\n2. While the construction of the attack queries is easy to understand, the analysis feels non-trivial and novel. I think the high-level idea of the ''gaining lemma''  may potentially apply to other problems under similar attack models. \n\n\n**Weakness**:\n\nI think the presentation of the paper can be improved.\n\n1. Some terms are used before explaining. For example,\n- ''Optimal estimator'' is only explained as ''tailored to A and D'' until page 6. It would be clearer to either move the explanation on Line 215, 216 to a much earlier place, or add a few more words on what specific ''optimal estimator'' is being considered, since this is central to understanding the contribution and applicability of the result. \n- ''Signal gap'' appears in Lemma 4.1 without definition. Because ''signal'' already refers to $e_h$ earlier (and ''signal weight'' to $w$), the phrase “signal gap” is not self-explanatory and should be defined at first use.\n\n2. The purpose of each lemma in Section 4 is not very intuitive. i.e., It's a bit hard to understand what's the role of them in the entire proof. I think it would be helpful to add a short overview of the proof strategy and how the lemmas interlock.\n\n3. For the appendix, I only browsed through Appendix C and find\n- multiple typos, e.g. \"is order\" on Line 544, \"$2^{t-2}$\" on Line 527, and unclosed brackets on Line 564, 572. \n- Claim C.3. needs $\\langle v^{(i)}, v^{(j)} \\rangle = 1$ in the condition. Tracing down the proof of Lemma 4.5, Claim C.3 is applied on rows of a submatrix $B$ of $A$ containing orthogonal rows. I'm not sure how these rows satisfy the condition. \n\n\n  While I believe the proofs in the appendix are correct (at least on the high level), I suggest the authors to carefully proofread.", "was_revised": true, "final_justification": "I didn't have major questions previously. My questions were mostly for curiosity, and the authors' answers are satisfying. So I will maintain my score.", "rebuttal": "Thank you for your time and detailed, helpful comments! We will address all these issues and carefully proofread the final version.\n\n---\n\n### Q1: *“There are many recent works on attacks against sketching / streaming. Has a non-adaptive ‘batch’ attack model similar to the one in this paper been considered previously?”*\n\n**Response:**  \nPrior works that use single-batch (non-adaptive) attacks include:  \n\n- Cherapanamjeri and Nelson, NeurIPS 2020 (on JL with standard estimator)  \n- Cohen et al., ICML 2022 and AAAI 2023 (on CountSketch and AMS sketch)  \n- Ahmadian & Cohen, ICML 2024 (on MinHash cardinality sketches)  \n\nWe have added an explicit mention of these works when discussing this attack structure.  \n\n---\n\n### Q2: *“The paper suggests, as a future direction, reducing the Gaussian noise support from $k^2$ to $k$. Beyond satisfying aesthetic bounds, does a smaller support lead to any concrete efficiency or robustness benefits for the attack?”*\n\n**Response:**  \nYes — since the attack constructs vectors over the support and stores a sum of these vectors, a smaller support directly reduces storage requirements for the attack.  \n\nIt is also worth noting that our empirical attacks were already effective with much smaller supports: for $k = 100$ we used $n = 1000$, and for $k = 1000$ we used $n = 20000$. We suspect that even smaller supports would suffice and plan to extend our experiments to verify this.  \n\n---\n\n### Q3: *“In adversarial streaming, Gribelyuk et al. (2025) extends L2 norm estimation lower bounds to tasks such as Lp norm, operator norm, and eigenvalue estimation. While this paper investigates a different attack model, does the result similarly generalize to tasks beyond L2 norm estimation?”*\n\n**Response:**  \nWe did not consider other norms in this work, but this is an interesting direction for future research. We will add it as an open question in the conclusion section. We conjecture that the approach could extend to other settings — in particular, to $\\ell_p$ norms with $p \\in (1,2)$."}]

Author rebuttal:

Meta-review: This paper studies the robustness of linear sketches for ℓ₂ norm estimation under black-box adversarial attacks. The authors present a universal, non-adaptive, quadratic-size attack that succeeds against *any* linear sketching matrix and query responder, including randomized or adaptive ones. The result matches known upper bounds achieved for specific sketches (e.g., JL, AMS) with specialized estimators. The paper develops a clean theoretical framework, introducing abstractions such as the gap problem and the “gain lemma,” and provides preliminary experiments.  

**Strengths:**  
- Establishes a tight quadratic lower bound for adversarial attacks in a general sketching setting, extending beyond prior results.
- Generality: the attack applies to any linear sketch and responder, independent of distributional assumptions.  
- The theoretical development is constructive, with well-isolated abstractions that clarify the attack mechanism.  
- Empirical results, though limited, illustrate the attack in practice and confirm the expected failure modes.  

**Weaknesses:**  
- Empirical validation is somewhat limited (mainly to JL sketches with standard/robust estimators); experiments with other sketches (e.g., AMS) would strengthen the work.  
- Exposition could be improved: some definitions (e.g., “system,” “optimal estimator,” “signal gap”) appear late or without sufficient clarity; figures are hard to read; the appendix contains redundancy and typos.  
- The main failure guarantee applies to the optimal estimator under the attack distribution; extending guarantees to arbitrary or strategic estimators remains an open problem.  

**Outcomes of rebuttal:**  
The author–reviewer exchanges were constructive/productive. Authors committed to clarifying the exposition, introducing all notions or players (including the “system”), and improving figures and proof readability. They also promised to expand experiments to AMS sketches and explore smaller noise support sizes. Reviewers generally found the theoretical contribution solid and significant, and maintained or slightly increased their scores after rebuttal. One reviewer signaled lack of expertise, but others provided substantial evaluations.  

**Summary:**  
This paper makes a clear theoretical contribution to the adversarial robustness of low-dimensional representations, proving tight quadratic lower bounds for adversarial attacks on sketch-based norm estimation. While the exposition and empirical scope can be improved, the contribution is significant. I recommend acceptance as a poster, and encourage the authors to incorporate the clarifications and additional experiments discussed during the rebuttal.
Decision: Accept (poster)