The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation

Thank you for your time and detailed, helpful comments! We will address all these issues and carefully proofread the final version.

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?”

Response:
Prior works that use single-batch (non-adaptive) attacks include:

• Cherapanamjeri and Nelson, NeurIPS 2020 (on JL with standard estimator)
• Cohen et al., ICML 2022 and AAAI 2023 (on CountSketch and AMS sketch)
• Ahmadian & Cohen, ICML 2024 (on MinHash cardinality sketches)

We have added an explicit mention of these works when discussing this attack structure.

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?”

Response:
Yes — 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.

It 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.

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?”

Response:
We 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)$.

We thank the reviewer for their time and helpful comments! Our final version will address all the points listed under “weaknesses.”

Q1: “Is the $\Omega(k^2)$ noise support size a theoretical necessity, or could it be reduced empirically without compromising effectiveness?”

Response:
Our 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.

We 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.

Q2: “Consider removing the redundant restatement of Theorem 3.2 on Line 273 in Section 4.4, as it adds little new content.”

Response:
Thank you for pointing this out — we will remove the redundant restatement in the final version.

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.”

Response:
When 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.

As 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.

We thank the reviewer for their time and helpful comments!

W1 (improve the writing). We will address all comments, thank you!

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.”

Response: 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.

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”

Response: 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.

We thank the reviewer for their time and helpful comments!

W1 “Empirical verification only done for JL sketching matrices with Standard/Robust Estimator, should at least include some other sketch constructions”

We plan to add experiments with AMS sketching matrices and the standard (median based) and robustified estimators. We expect to see similar behavior to JL.

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”

The 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.

That 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.