# Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of
CountSketch to Adaptive Inputs

Edith Cohen Google Research and Tel Aviv University<EMAIL_ADDRESS>Jelani Nelson UC Berkeley and Google Research<EMAIL_ADDRESS>Tamás
Sarlós Google Research<EMAIL_ADDRESS>Uri Stemmer Tel Aviv University and
Google Research<EMAIL_ADDRESS>Partially supported by the Israel Science
Foundation (grant 1871/19) and by Len Blavatnik and the Blavatnik Family
foundation.

###### Abstract

CountSketch and Feature Hashing (the "hashing trick") are popular randomized
dimensionality reduction methods that support recovery of $\ell_{2}$-heavy
hitters (keys $i$ where $v_{i}^{2}>\epsilon\|\boldsymbol{v}\|_{2}^{2}$) and
approximate inner products. When the inputs are not adaptive (do not depend on
prior outputs), classic estimators applied to a sketch of size
$O(\ell/\epsilon)$ are accurate for a number of queries that is exponential in
$\ell$. When inputs are adaptive, however, an adversarial input can be
constructed after $O(\ell)$ queries with the classic estimator and the best
known robust estimator only supports $\tilde{O}(\ell^{2})$ queries. In this
work we show that this quadratic dependence is in a sense inherent: We design
an attack that after $O(\ell^{2})$ queries produces an adversarial input
vector whose sketch is highly biased. Our attack uses "natural" non-adaptive
inputs (only the final adversarial input is chosen adaptively) and universally
applies with any correct estimator, including one that is unknown to the
attacker. In that, we expose inherent vulnerability of this fundamental
method.

##  1 Introduction

CountSketch [11] and its variant feature hashing [31, 41] are immensely
popular dimensionality reduction methods that map input vectors in
$\mathbb{R}^{n}$ to their sketches in $\mathbb{R}^{d}$ (where $d\ll n$). The
methods have many applications in machine learning and data analysis and often
are used as components in large models or pipelines [41, 35, 33, 12, 13, 1,
37, 2, 15].

The mapping is specified by internal randomness $\rho\sim\mathcal{D}$ that
determines a set of $d=\ell\cdot b$ linear measurements vectors
$(\boldsymbol{\mu}^{(j,k)})_{j\in[\ell],k\in[b]}$ in $\mathbb{R}^{n}$. The
sketch $\text{{Sketch}}_{\rho}(\boldsymbol{v})$ of a vector
$\boldsymbol{v}\in\mathbb{R}^{n}$ is the matrix of $d$ linear measurements

$\text{{Sketch}}_{\boldsymbol{\rho}}(\boldsymbol{v}):=\left(\langle\boldsymbol{\mu}^{(j,k)},\boldsymbol{v}\rangle\right)_{j\in[\ell],k\in[b]}.$
(1)

The salient properties of CountSketch are that (when setting $b=O(1/\epsilon)$
and $\ell=O(\log n)$) the $\ell_{2}$-heavy hitters of an input
$\boldsymbol{v}$, that is, keys $i$ with
$v_{i}^{2}>\epsilon\|\boldsymbol{v}\|_{2}^{2}$, can be recovered from
$\text{{Sketch}}_{\rho}(\boldsymbol{v})$ and that the inner product of two
vectors $\boldsymbol{v}$, $\boldsymbol{u}$ can be approximated from their
respective sketches $\text{{Sketch}}_{\rho}(\boldsymbol{v})$,
$\text{{Sketch}}_{\rho}(\boldsymbol{u})$. This recovery is performed by
applying an appropriate estimator to the sketch, for example, the median
estimator [11] provides estimates on values of keys and supports heavy hitters
recovery. But recovery can also be implicit, for example, when the sketch is
used as a compression module in a Neural Network [12], the recovery of
features is learned.

Randomized data structures and algorithms, CountSketch included, are typically
analysed under an assumption that the input sequence is generated in a way
that does not depend on prior outputs and on the sketch randomness $\rho$.
This assumption, however, does not always hold, for example, when there is an
intention to construct an adversarial input or when the system has a feedback
between inputs and outputs [37, 34].

The adaptive setting, where inputs may depend on prior outputs, is more
challenging to analyse and there is growing interest in quantifying
performance and in designing methods that are robust to adaptive inputs. Works
in this vein span machine learning [39, 19, 5, 32], adaptive data analysis
[17, 25, 29, 22, 16], dynamic graph algorithms [36, 3, 18, 21, 40, 7], and
sketching and streaming algorithms [30, 3, 23, 9, 24, 42, 6, 8, 20, 14].
Robustness to adaptive inputs can trivially be achieved by using a fresh data
structure for each query, or more finely, for each time the output changes.
Hence, $\ell$ independent replicas of a non-robust data structures suffice for
supporting $\ell$ adaptive queries. A powerful connection between adaptive
robustness and differential privacy [16] and utilizing the workhorse of DP
composition, yielded essentially a wrapper around $\ell$ independent replicas
of a non-robust data structure that supports a quadratic number
$\tilde{O}(\ell^{2})$ of adaptive queries (or changes to the output) [24, 20,
7]. For the problem of recovering heavy-hitters from CountSketch, the
"wrapper" method supports $\approx\epsilon\ell^{2}$ adaptive queries. The
current state of the art [14] is a robust estimator that works with a variant
of CountSketch and supports $\tilde{O}(\ell^{2})$ adaptive queries.

Lower bounds on the performance of algorithms to adaptive inputs are obtained
by designing an attack, a sequence of input vectors, that yields a constructed
input that is adversarial to the internal randomness $\rho$. Tight lower
bounds on the robustness of statistical queries were established by [22, 38],
who designed an attack with a number of queries that is quadratic in the
sample size, which matches the known upper bounds [16]. Their construction was
based on fingerprinting codes [10]. A downside of these constructions is that
the inputs used in the attack are not "natural" and hence unlikely to shed
some understanding on practical vulnerability in the presence of feedback.
Hardt and Woodruff [23] provided an impossibility result for the task of
estimating the norm of the input within a constant factor from (general)
linear sketches. Their construction works with arbitrary correct estimators
and produces an adversarial distribution over inputs where the sketch
measurements are "far" from their expectations. The attack size, however, has
a large polynomial dependence on the sketch size and is far from the
respective upper bound. Ben-Eliezer et al [9] present an attack on the AMS
sketch [4] for the task of approximating the $\ell_{2}$-norm of the input
vector. The attack is tailored to a simplified estimator that is linear in the
set of linear measurements (whereas the "classic" estimator uses a median of
measurements and is not linear). Their attack is efficient in that the number
of queries is of the order of the sketch size, rendering the estimator non-
robust. It also has an advantage of using "natural" inputs. More recently,
[14] presented attacks that are tailored to specific estimators for
CountSketch, including an attack of size $O(\ell)$ on the classic median
estimator and an attack of size $O(\ell^{2})$ on their proposed robust
estimator.

### Contribution

Existing works proposed attacks of size that is far from the corresponding
known upper bounds or are tailored to a particular estimator. Specifically for
CountSketch, there is an upper bound of $O(\ell^{2})$ but it is not even known
whether there exist estimators that support a super-quadratic number of
adaptive inputs. This question is of particular importance because CountSketch
and its variants are the only known efficient sketching method that allow
recovery of $\ell_{2}$-heavy hitters and approximating $\ell_{2}$ norms and
inner products. Moreover, their form as linear measurements is particularly
suitable for efficient implementations and integration as components in larger
pipelines. Finally, a recent lower bound precludes hope for an efficient
deterministic (and hence fully robust) sketch [28], so it is likely that the
vulnerabilities of CountSketch are inherent to $\ell_{2}$-heavy hitter (and
approximate $\ell_{2}$-norm and inner product) recovery from a small sketch.

We construct a universal attack on CountSketch, that applies against any
unknown, potentially non-linear, possibly state maintaining, estimator. We
only require that the estimator is correct. Our attack uses $O(\ell^{2})$
queries, matching the $\tilde{O}(\ell^{2})$ robust estimator upper bound [14].
Moreover, it suffices for the purpose of the attack that the estimator only
reports a set of candidate heavy keys without their approximate values (we
only require that heavy hitters are reported with very high probability and
$0$ value keys are reported with very small probability). Our attack also
applies against a correct inner-product estimator (that distinguishes between
$\langle\boldsymbol{v},\boldsymbol{u}\rangle=0$ (reported with very small
probability) and
$\langle\boldsymbol{v},\boldsymbol{u}\rangle^{2}\geq\epsilon\|\boldsymbol{v}\|_{2}^{2}\|\boldsymbol{u}\|_{2}^{2}$
(reported with high probability.)) Additionally, we apply our attack to
correct $\ell_{2}$-norm estimators applied to an AMS sketch [4] and obtain
that an attack of size $O(\ell^{2})$ suffices to construct an adversarial
input. The AMS sketch can be viewed as a CountSketch with $b=1$ and is similar
to the Johnson Lindenstrauss transform [27].

The product of our attack (with high probability) is an adversarial input
$\boldsymbol{v}$ on which the measurement values of
$\text{{Sketch}}_{\rho}(\boldsymbol{v})$ are very biased with respect to their
distribution when $\rho\sim\mathcal{D}$. Specifically, the design of
CountSketch results in linear measurements that are unbiased for any input
$\boldsymbol{v}$ under the sketch distribution $\rho\sim\cal{D}$: For each key
$i$ and measurement vectors $\boldsymbol{\mu}$ with $\mu_{i}\not=0$ it holds
that
$\textsf{E}_{\rho}[\langle\boldsymbol{v},\boldsymbol{\mu}\rangle/\mu_{i}-v_{i}]=0$
but the corresponding expected values for our adversarial $\boldsymbol{v}$ in
$\text{{Sketch}}_{\rho}(\boldsymbol{v})$ are large ($\geq
B\epsilon\|\boldsymbol{v}\|_{2}^{2}$ for a desired $B>1$). This "bias" means
that the known standard (and robust) estimators for heavy hitters and inner
products would fail on this adversarial input. And generally estimators that
satisfy the usual design goal of being correct on any input with high
probability over the distribution of $\text{{Sketch}}_{\rho}(\boldsymbol{v})$
may not be correct on the adversarial inputs. We note however that our result
does not preclude the existence of specialized estimators that are correct on
our adversarial inputs. We only show that a construction of an input that is
adversarial to $\rho$ is possible with any correct estimator.

Finally, our attacks uses "natural" inputs that constitute of a heavy key and
random noise. The final adversarial input is a linear combination of the noise
components according to the heavy hitter reports and is the only one that
depends on prior outputs. The simplicity of this attack suggests "practical"
vulnerability of this fundamental sketching technique.

Technique Our attacks construct an adversarial input with respect to key $h$.
The high level structure is to generate "random tails,"
$(\boldsymbol{z}^{(t)})_{t\in[r]}$, which are vectors with small random
entries. Ideally, we would like to determine for each $\boldsymbol{z}^{(t)}$
whether it is biased up or down with respect to key $h$. Roughly, considering
the set $T_{h}$ of $\ell$ measurement vectors with $\mu_{h}\in\\{-1,1\\}$,
determine the sign $s^{*(t)}$ of $\frac{1}{\ell}\sum_{\boldsymbol{\mu}\in
T_{h}}\langle\boldsymbol{\mu},\boldsymbol{z}^{(t)}\rangle\cdot\mu_{h}$. If we
had that, the linear combination
$\boldsymbol{z}^{*(A)}=\sum_{t\in[r]}s^{*(t)}\boldsymbol{z}^{(t)}$ (with large
enough $r$) is an adversarial input. The intuition why this helps is that the
bias accumulates linearly with the number of tails $r$ whereas the standard
deviation (essentially the $\ell_{2}$ norm), considering randomness of the
selection of tails, increases proportionally to $\sqrt{r}$. The attack
strategy is then to design query vectors of the form
$v^{(t)}_{h}\boldsymbol{e}_{h}+\boldsymbol{z}^{(t)}$ so that from whether or
not $h$ is reported as a heavy hitter candidate we obtain $s^{(t)}$ that
correlates with $s^{*(t)}$. A higher correlation $\textsf{E}[s^{*(t)}s^{(t)}]$
yields more effective attacks: With $\textsf{E}[s^{*(t)}s^{(t)}]=\Omega(1)$ we
get attacks of size $r=O(\ell)$ and with
$\textsf{E}[s^{*(t)}s^{(t)}]=\Omega(1/\sqrt{\ell})$ we get attack of size
$r=O(\ell^{2})$. We show that we can obtain $s^{(t)}$ with
$\textsf{E}[s^{*(t)}s^{(t)}]=\Omega(1/\sqrt{\ell})$ (thus matching the upper
bound) against any arbitrary and adaptable estimator as long as it is correct.
The difficulty is that such an estimator can be non monotone in the value
$v_{h}$ of the heavy key and change between queries. Our approach is to select
the value $v_{h}$ of the heavy key in the input vectors uniformly at random
from an interval that covers the "uncertainty region" between values that must
be reported as heavy to values that are hard to distinguish from $0$ and hence
should not be reported. We then observe that in expectation over the random
choice, any correct estimator must have a slight reporting advantage with
larger $v_{h}$. Finally, we show that any particular sketch content is equally
likely with symmetrically larger $v_{h}$ with a tail that is biased down or a
smaller $v_{h}$ with a tail that is biased up. This translates to a slight
reporting advantage for $h$ as a candidate heavy hitter when the tail is
"biased up." Therefore by taking $s^{(t)}=1$ when $h$ is reported and
$s^{(t)}=-1$ otherwise we have the desired correlation.

Remark: We note that our use of "noise vectors" that have sparsity larger than
sketch size is necessary to break robustness. This because with high
probability, from a CountSketch with parameters $b=O(1/\epsilon)$ and
$\ell=O(\log n)$, we can fully recover all vectors
$\boldsymbol{v}\in\mathbb{R}^{n}$ with at most $O(1/\epsilon)$ non-zeros.
Therefore, CountSketch is fully robust to sufficiently sparse inputs, but
turns out to be less robust on inputs where a set of $O(1/\epsilon)$ heavy
entries is augmented with noise.

Related work: In terms of techniques, our work is most related to [14] in that
the structure of our attack vectors is similar to those used in [14] to
construct a tailored attack on the classic estimator. The generalization
however to a "universal" attack that is effective against arbitrary and
unknown estimators was delicate and required multiple new ideas. Our
contribution is also related and in a sense complementary to [23] that
designed attack on linear sketches that applies with any correct estimator for
(approximate) norms. Their attack is much less efficient in that its size is a
higher degree polynomial and it uses dependent (adaptive) inputs (whereas with
our attack only the final adversarial input depends on prior outputs). The
product of their attack are constructed vectors that are in the (approximate)
null space of the sketching matrix. These "noise" vectors can have large norms
but are "invisible" in the sketch. When such "noise" is added to an input with
a signal (say a heavy hitter), the "signal" is suppressed (entry no longer
heavy) but can still be recovered from the sketch. Our attack fails the sketch
matrix in a complementary way: we construct "noise" vectors that do not
involve a signal (a heavy entry) but the sketch mimics a presence of that
particular signal.

Overview: Our attack is described in Section 3 and is analysed in subsequent
sections. The query vectors used in the attack have a simple sketch structure
(described in Section 4) and simplify the estimation task (as described in
Section 5). In Section 6 we cast the attack on heavy hitters estimator as one
on a mean estimator and carry out the remaining analysis in this simplified
context. Section 7 includes detailed proofs. In Section 8 we apply our attack
technique to $\ell_{2}$ norm estimators for the AMS sketch [4].

##  2 Preliminaries

We use boldface notation for vectors $\boldsymbol{v}$, non boldface for
scalars $v$, $\langle\boldsymbol{v},\boldsymbol{u}\rangle=\sum_{i}v_{i}u_{i}$
for inner product, and $v\cdot u$ for scalar product. For a vector
$\boldsymbol{v}\in\mathbb{R}^{n}$ we refer to $i\in[n]$ as a key and $v_{i}$
as the value of the $i$th key (entry) and denote by
$\overline{v}=\frac{1}{n}\sum_{i=1}^{n}v_{i}$ the mean value. For exposition
clarity, we use $\approx$ to mean "within a small relative error." We denote
by $\mathcal{N}(v,\sigma^{2})$ the normal distribution with mean $v$ and
variance $\sigma^{2}$ and by
$\boldsymbol{u}\sim\mathcal{N}_{\ell}(v,\sigma^{2})$ a vector in
$\mathbb{R}^{\ell}$ with entries that are i.i.d. $\mathcal{N}(v,\sigma^{2})$.
The probability density function of $\mathcal{N}_{\ell}(v,\sigma^{2})$ is

$f_{v}(\boldsymbol{u})=\prod_{i\in[\ell]}\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}\left(\frac{u_{i}-v}{\sigma}\right)^{2}}\
.$ (2)

######  Definition 2.1.

(heavy hitter) For $\epsilon>0$, and a vector
$\boldsymbol{v}\in\mathbb{R}^{n}$, key $i\in[n]$ is an
$\ell_{2}$-$\epsilon$-heavy hitter if
$v_{i}^{2}\geq\epsilon\|\boldsymbol{v}\|_{2}^{2}$.

Clearly, there can be at most $1/\epsilon$ $\ell_{2}$-$\epsilon$ heavy
hitters.

######  Definition 2.2.

(Heavy Hitters Estimator) A $\ell_{2}$-$\epsilon$-heavy hitters estimator is
applied to a sketch of an input vector $\boldsymbol{v}\in\mathbb{R}^{n}$ and
returns a set of entries $K\subset[n]$. The output is correct if $K$ includes
all the $\ell_{2}$-$\epsilon$-heavy hitters keys and does not include keys
with $v_{i}=0$.

######  Remark 2.3.

This correctness definition is weaker than what the classic estimator applied
to CountSketch provides [11]: A sketch with $\ell=O(\log(n/\delta))$ provides
with probability $1-\delta$, approximate values for all $n$ keys that are
within $\epsilon\|\boldsymbol{v}_{\mathsf{tail}(1/\epsilon)}\|_{2}^{2}$,
noting that the tail (vector $\boldsymbol{v}_{\mathsf{tail}(1/\epsilon)}$ that
is our input $\boldsymbol{v}$ with $1/\epsilon$ heaviest entries nullified)
has smaller norm than $\boldsymbol{v}$, yielding tighter estimates. In
particular, this yields a correct solution to the heavy hitters problem with
probability $1-\delta$. Since our focus here is on designing an attack, our
design is stronger against weaker requirements since less information on the
randomness is being revealed.

######  Definition 2.4.

(Inner Product Estimator) An inner-product estimator is applied to sketches of
two input vectors $\boldsymbol{v},\boldsymbol{u}\in\mathbb{R}^{n}$ and returns
$s\in\\{-1,1\\}$. The output is correct if $s=-1$ when
$\langle\boldsymbol{v},\boldsymbol{u}\rangle=0$ and is $s=1$ when
$\langle\boldsymbol{v},\boldsymbol{u}\rangle^{2}\geq\epsilon\|\boldsymbol{v}\|_{2}^{2}\|\boldsymbol{u}\|_{2}^{2}$.

###  2.1 CountSketch

The sketch [11] is specified by parameters $(n,\ell,b)$, where $n$ is the
dimension of input vectors, and $d=\ell\cdot b$. The internal randomness
$\rho$ specifies a set of random hash functions $h_{r}:[n]\rightarrow[b]$
($r\in[\ell]$) with the marginals that $\forall k\in[b]$, $i\in[n]$,
$\textsf{Pr}[h_{j}(i)=k]=1/b$, and $s_{j}:[n]\rightarrow\\{-1,1\\}$
($j\in[\ell]$) so that $\textsf{Pr}[s_{j}(i)=1]=1/2$. These hash functions
define $d=\ell\cdot b$ measurement vectors that are organized as $\ell$ sets
of $b$ vectors each $\boldsymbol{\mu}^{(j,k)}$ ($j\in[\ell]$, $k\in[b]$)
where:

$\mu^{(j,k)}_{i}:=\mathbbm{1}_{\\{h_{j}(i)=k\\}}s_{j}(i).$

For an input vector $\boldsymbol{v}\in\mathbb{R}^{n}$,
$\text{{Sketch}}_{\rho}(\boldsymbol{v}):=(\langle\boldsymbol{\mu}^{(j,k)},\boldsymbol{v}\rangle)_{j,k}$
is the set of the respective measurement values. Note that for each key
$i\in[n]$ there are exactly $\ell$ measurement vectors with a nonzero $i$th
entry: $(\boldsymbol{\mu}^{(j,h_{j}(i))})_{j\in[\ell]}$ and these measurement
vectors are independent (as the only dependency is between measurement in the
same set of $b$, and there is exactly one from each set). The respective set
of $\ell$ adjusted measurements:

$(\langle\boldsymbol{\mu}^{(j,h_{j}(i))},\boldsymbol{v}\rangle\mu^{(j,h_{j}(i))}_{i})_{j\in[\ell]}$
(3)

are unbiased estimates of $v_{i}$:
$\textsf{E}_{\rho}[\langle\boldsymbol{\mu}^{(j,h_{j}(i))},\boldsymbol{v}\rangle\mu^{(j,h_{j}(i))}_{i}]=v_{i}$.

The median estimator [11] uses the median adjusted measurement to estimate the
value $v_{i}$ of each key $i$. The $O(1/\epsilon)$ keys with highest magnitude
estimates are then reported as heavy hitters. When the same randomness $\rho$
is used for $r$ non-adaptive inputs (inputs selected independently of $\rho$
and prior outputs), sketch parameter settings of $\ell=\log(r\cdot n/\delta)$
and $b=O(\epsilon^{-1})$ guarantee that with probability $1-\delta$, all
outputs are correct (in the sense of Remark 2.3).

CountSketch also supports estimation of inner products. For two vectors
$\boldsymbol{v}$, $\boldsymbol{u}$, we obtain an unbiased estimate of their
inner product from the respective inner product of the $j\in[\ell]$th row of
measurements:

$\sum_{k\in[b]}\langle\boldsymbol{\mu}^{(j,k)},\boldsymbol{v}\rangle\cdot\langle\boldsymbol{\mu}^{(j,k)},\boldsymbol{u}\rangle\
.$ (4)

The median of these $\ell$ estimates is within relative error
$\sqrt{\epsilon}$ with probability $1-\exp(\Omega(-\ell))$.

We note that pairwise independent hash functions $h_{j}$ and $s_{j}$ suffice
for obtaining the guarantees of Remark 2.3 [11] whereas 4-wise independence is
needed for approximate inner products. The analysis of the attack we present
here, however, holds even under full randomness.

###  2.2 Adversarial Input for CountSketch

######  Definition 2.5 (Adversarial input).

We say that an attack $\mathcal{A}$ that is applied to a sketch with
randomness $\rho$ and outputs $i\in[n]$ and
$\boldsymbol{z}^{(A)}\in\\{-1,0,1\\}^{n}$ (with $z^{(A)}_{i}=0$) is
$(B,\beta)$-adversarial (for $B>1$) if, with probability at least $1-\beta$
over the randomness of $\rho,\mathcal{A}$, the adjusted measurements (3)
satisfy:

$\textsf{Pr}_{\rho\sim\mathcal{D},\mathcal{A}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{\mu}^{(j,h_{j}(i))},\boldsymbol{z}^{(A)}\rangle\mu^{(j,h_{j}(i))}_{i}\geq\sqrt{\frac{B}{b}}\|\boldsymbol{z}^{(A)}\|_{2}\right]\geq
1-\beta.$ (5)

The adversarial input $\boldsymbol{z}^{(A)}$ is a noise vector (with no heavy
hitters) but $\text{{Sketch}}_{\rho}(\boldsymbol{z}^{(A)})$ "looks like" (in
terms of the average adjusted measurement of key $i$) a sketch of a vector
with a heavy key $i$. It follows from the standard analysis of CountSketch
that the event

$\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{\mu}^{(j,h_{j}(i))},\boldsymbol{v}\rangle\mu^{(j,h_{j}(i))}_{i}\geq\sqrt{\frac{B}{b}}\|\boldsymbol{v}\|_{2}\
.$ (6)

(that correspondence to (5)) is very likely for vectors $\boldsymbol{v}$ such
that $h$ is a heavy hitter (Definition 2.1) and extremely unlikely when $h$ is
not a heavy hitter, and in particular, when $v_{h}=0$. Similarly for inner
products, considering inner product $\boldsymbol{v}$ with the standard basis
vector $\boldsymbol{e}_{i}$, the sketch-based estimates (4) of each $j\in\ell$
computed from $\text{{Sketch}}_{\rho}(\boldsymbol{e}_{i})$ and
$\text{{Sketch}}_{\rho}(\boldsymbol{v})$ are equal to the respective adjusted
measurement (3) of $i$ from $\text{{Sketch}}_{\rho}(\boldsymbol{v})$. The
event (6) is very likely when
$\langle\boldsymbol{e}_{i},\boldsymbol{v}\rangle\geq\epsilon\|\boldsymbol{v}\|_{2}^{2}$
and very unlikely when $\langle\boldsymbol{e}_{i},\boldsymbol{v}\rangle=0$,
noting that for our adversarial input $\boldsymbol{z}^{(A)}$ it holds that
$\langle\boldsymbol{e}_{i},\boldsymbol{z}^{(A)}\rangle=0$.

While this follows from the standard analysis, the simple structure of our
noise vectors allows for a particularly simple argument for bounding the
probability of (6) for $\boldsymbol{v}$ with the structure of
$\boldsymbol{z}^{(A)}$ : The distribution of an adjusted measurement of a
$\boldsymbol{v}\in\\{-1,0,1\\}^{n}$ and $v_{i}=0$ with support size
$m=|\texttt{supp}{(\boldsymbol{v}}|=\|\boldsymbol{v}\|^{2}_{2}$ approaches
$\mathcal{N}(0,\frac{m}{b})$ (for large $m/b$), and thus the average
approaches $\mathcal{N}(0,\frac{m}{\ell\cdot b})$. Therefore, the probability
of (5) on a random sketch of $\boldsymbol{z}^{(A)}$ is $\leq\exp(-\ell B/2)$
(applying tail bounds on the probability of value exceeding $\sqrt{\ell B}$
standard deviations).

##  3 Attack Description

We describe our attack against heavy hitters estimators. The modifications
needed for it to apply with inner product estimator are described in Section
3.3. The attack is an interaction between the following components:

  * •

Internal randomness $\rho\sim\mathcal{D}$ that specifies linear measurement
vectors $(\boldsymbol{\mu}^{(j,k)})_{j\in[\ell],k\in[b]}$. The sketch
$\text{{Sketch}}_{\rho}(\boldsymbol{v})$ of a vector
$\boldmath{v}\in\mathbb{R}^{n}$ is the set of measurements
$(\langle\boldsymbol{\mu}^{(j,k)},\boldsymbol{v}\rangle)_{j\in[\ell],k\in[b]}$.

  * •

A query-response algorithm that at each step $t$ chooses a heavy hitters
estimator (see Definition 2.2). The choice may depend on the randomness $\rho$
and prior queries and responses
$(\text{{Sketch}}_{\rho}(\boldsymbol{v}^{(t^{\prime})}),K^{(t^{\prime})})_{t^{\prime}<t}$.
The algorithm receives $\text{{Sketch}}_{\rho}(\boldsymbol{v}^{(t)})$, applies
the estimator to the sketch, and outputs $K^{(t)}$.

  * •

An adversary that issues a sequence of input queries
$(\boldsymbol{v}^{(t)})_{t}$ and collects the responses $(K^{(t)})_{t}$. The
randomness $\rho$ and the sketches of the query vectors
$(\text{{Sketch}}_{\rho}(\boldsymbol{v}^{(t)}))_{t}$ are not known to the
adversary. The goal is to construct an adversarial input vector
$\boldsymbol{z}^{(A)}$ (see Definition 8.1).

Our adversary generates the query vectors $(\boldsymbol{v}^{(t)})_{t\in[r]}$
non-adaptively as described in Section 3.1. The attack interaction and its
properties are stated in Section 3.2.

###  3.1 Query Vectors

Our attack query vectors $(\boldsymbol{v}^{(t)})_{t\in[r]}$ of the form:

$\boldsymbol{v}^{(t)}:=v^{(t)}_{h}\boldsymbol{e}_{h}+\boldsymbol{z}^{(t)}\in\mathbb{R}^{n},$
(7)

where $h$ is a special heavy key, that is selected uniformly
$h\sim\mathcal{U}[n]$ and remains fixed, $\boldsymbol{e}_{h}$ is the standard
basis vector (axis-aligned unit vector along $h$), and the vectors
$\boldsymbol{z}^{(t)}$ are tails. The (randomized) construction of tails is
described in Algorithm 1. The tail vectors $(\boldsymbol{z}^{(t)})_{t\in[r]}$
have support of size $|\texttt{supp}(\boldsymbol{z}^{(t)})|=m$ that does not
include key $h$ ($h\not\in\texttt{supp}(\boldsymbol{z}^{(t)})$) and so that
the supports of different tails are disjoint:

$t_{1}\not=t_{2}\implies\texttt{supp}(\boldsymbol{z}^{(t_{1})})\cap\texttt{supp}(\boldsymbol{z}^{(t_{2})})=\emptyset\
.$

For query $t$ and key $i\in\texttt{supp}(\boldsymbol{z}^{(t)})$, the values
are selected i.i.d. Rademacher $z^{(t)}_{i}\sim\mathcal{U}[\\{-1,1\\}]$. Note
that
$\|\boldsymbol{v}^{(t)}\|_{2}^{2}=(v_{h}^{(t)})^{2}+\|\boldsymbol{z}^{(t)}\|_{2}^{2}=(v_{h}^{(t)})^{2}+m$.
Note that the tails, and (as we shall see) the selection of $v^{(t)}_{h}$, and
hence the input vectors are constructed non-adaptively. Only the final
adversarial input vector depends on the output of the estimator on prior
queries. The parameter $m$ is set to a value that is polynomial in the sketch
size and large enough so that certain approximations hold (see Section 4).

Input: Input dimension $n$, support size $m$, number of tails $r$

$h\leftarrow\mathcal{U}[n]$

// Special heavy hitter key

$S\leftarrow\\{h\\}$

// Keys used in support

for  _$t\in[r]$_ do

$S^{\prime}\leftarrow$ random subset of size $m$ from $[n]\setminus S$

$\boldsymbol{z}^{(t)}\leftarrow\boldsymbol{0}$

foreach  _$i\in S^{\prime}$_ do

$\boldsymbol{z}^{(t)}_{i}\sim\mathcal{U}[\\{-1,1\\}]$

$S\leftarrow S\cup S^{\prime}$

return _$h,(\boldsymbol{z}^{(t)})_{t\in[r]}$_

Algorithm 1 AttackTails

######  Remark 3.1.

The only piece of information needed from the output of the estimator is
whether the particular key $h$ is reported as a candidate heavy hitter of
$\boldsymbol{v}^{(t)}$, that is, whether $h\in K^{(t)}$. Note that disclosing
additional information can only make the estimator more vulnerable to attacks.

###  3.2 Universal Attack

Use $a=\Theta(\sqrt{\frac{\ln(1/\delta_{2})}{\ell}})$ and $c=\Theta(1)$

// With universal constants as in Lemma 5.1

Input: Initialized $\text{{CountSketch}}_{\rho}$ with parameters $(n,\ell,b)$,
Query-response algorithm, number of queries $r$, tail support size $m$

$(h,(\boldsymbol{z}^{(t)})_{t\in[r]})\leftarrow$ AttackTails$(n,m,r)$

// Algorithm 1

for  _$t\in[r]$_ do // Compute Query Vectors

$v^{(t)}_{h}\sim\mathcal{U}[a\cdot\sigma,(c+2a)\cdot\sigma]$

// $\sigma:=\sqrt{m/b}$

$\boldsymbol{v}^{(t)}\leftarrow
v^{(t)}_{h}\boldsymbol{e}_{h}+\boldsymbol{z}^{(t)}$

// Query vectors

for  _$t\in[r]$_ do // Apply Query Response

Choose a correct HH estimator $M^{(t^{\prime})}$

// With correct reporting function (Definition 6.1), may depend on
$(v^{(t^{\prime})}_{h},K^{(t^{\prime})},M^{(t^{\prime})})_{t^{\prime}<t}$ and
$\rho$

$K^{(t)}\leftarrow M^{(t)}(\text{{CountSketch}}_{\rho}(\boldsymbol{v}^{(t)}))$

// Apply estimator to sketch

if  _$h\in K^{(t)}$_ then $s^{(t)}\leftarrow 1$ else $s^{(t)}\leftarrow-1$

return
_$\boldsymbol{z}^{(A)}\leftarrow\sum_{t\in[r]}s^{(t)}\boldsymbol{z}^{(t)}$_

// Adversarial input

Algorithm 2 Universal Attack on CountSketch Heavy Hitters Estimators

Our attack interaction is described in Algorithm 2. We generate $r$ attack
tails using Algorithm 1. We then construct $r$ queries of the form (7) with
i.i.d. $v^{(t)}_{h}\sim\mathcal{U}[a\cdot\sigma,(c+2a)\cdot\sigma]$. At each
step $t\in[r]$, we feed the sketch of $\boldsymbol{v}^{(t)}$ to the HH
estimator selected by the query response algorithm and collect the output
$K^{(t)}$ of the estimator. We then set $s^{(t)}\leftarrow 1$ if $h\in
K^{(t)}$ and $s^{(t)}\leftarrow-1$ if $h\not\in K^{(t)}$. The final step
computes the adversarial input:

$\boldsymbol{z}^{(A)}:=\sum_{t\in[r]}s^{(t)}\boldsymbol{z}^{(t)}\ .$ (8)

The statements below only use measurement vectors with nonzero value for key
$h$. To simplify the notation, we use
$\boldsymbol{\mu}^{(j)}:=\boldsymbol{\mu}^{(j,h_{j}(h))}$ for $j\in[\ell]$.
For randomness $\rho$, we use the notation $\boldsymbol{\mu}^{(j)}(\rho)$ for
the respective measurement vectors and $\mathcal{A}(\rho)$ for the output
distribution of Algorithm 2 applied with randomness $\rho$.

The adversarial input has $z^{(A)}_{h}=0$ and norm
$\|\boldsymbol{z}^{(A)}\|^{2}_{2}=r\cdot m$ (it has support of size $r\cdot m$
with values in the support i.i.d Rademacher $U[\\{-1,1\\}]$). When an
adversarial input $\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0})$ is sketched
using a random $\rho\sim\mathcal{D}$ it holds that:

$\displaystyle\forall j\in[\ell],\
\textsf{E}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0}),\rho\sim\mathcal{D}}\left[\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}(\rho)\rangle\right]$
$\displaystyle=0\ $ $\displaystyle\forall j\in[\ell],\
\textsf{Var}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0}),\rho\sim\mathcal{D}}\left[\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}(\rho)\rangle\right]$
$\displaystyle\approx\frac{r\cdot m}{b}=r\sigma^{2}\ .$

and since the $\ell$ measurements are independent we get:

$\displaystyle\textsf{E}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0}),\rho\sim\mathcal{D}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}(\rho)\rangle\cdot\mu^{(j)}_{h}(\rho)\right]$
$\displaystyle=0$
$\displaystyle\textsf{Var}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0}),\rho\sim\mathcal{D}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}(\rho)\rangle\cdot\mu^{(j)}_{h}(\rho)\right]$
$\displaystyle\approx\frac{r}{\ell}\cdot\sigma^{2}$

The adversarial input $\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0})$ behaves
differently with respect to the particular randomness $\rho_{0}$ it was
constructed for. We will establish the following:

######  Lemma 3.2 (Properties of the adversarial input).

$\displaystyle\textsf{E}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0})}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}(\rho_{0})\rangle\cdot\mu^{(j)}_{h}(\rho_{0})\right]$
$\displaystyle\approx\frac{r}{\ell}\cdot\frac{2\sigma}{c+a}$
$\displaystyle\textsf{Var}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0})}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}(\rho_{0})\rangle\cdot\mu^{(j)}_{h}(\rho_{0})\right]$
$\displaystyle\approx\frac{r}{\ell}\cdot\sigma^{2}$

The proof is provided in Section 6 (following preparation in Sections 4-5 and
details in Section 7). The high level idea, as hinted in the introduction, is
that we establish that $h\in K^{(t)}$ and thus $s^{(t)}=1$ is correlated with
"positive bias", that is, with the event
$\frac{1}{\ell}\sum_{j\in[\ell]}\langle
s^{(t)}\boldsymbol{z}^{(t)},\boldsymbol{\mu}^{(j)}(\rho_{0})\rangle\cdot\mu^{(j)}_{h}(\rho_{0})>0$.
In the sum $\sum_{t\in[r]}s^{(t)}\boldsymbol{z}^{(t)}$ the bias (which is
“forced” error on the estimates) increases linearly with $r$ while the
$\ell_{2}$ norm, which corresponds to the standard deviation of the error,
increases proportionally to $\sqrt{r}$.

With Lemma 3.2 in hand, we are ready to show that $\boldsymbol{z}^{(A)}$ is an
adversarial input (see Definition 8.1).

######  Theorem 3.1 (Adversarial input).

If for $B>1$ we use attack of size $r=B\cdot\ell^{2}$ then

$\displaystyle\textsf{E}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0})}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)(\rho_{0})}\rangle\cdot\mu^{(j)}_{h}(\rho_{0})\right]$
$\displaystyle\approx\frac{2}{c+a}\sqrt{\frac{B}{b}}\|\boldsymbol{z}^{(A)}\|_{2}$
$\displaystyle\textsf{Var}_{\rho_{0}\sim\mathcal{D},\boldsymbol{z}^{(A)}\sim\mathcal{A}(\rho_{0})}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}(\rho_{0})\rangle\cdot\mu^{(j)}_{h}(\rho_{0})\right]$
$\displaystyle\approx\frac{1}{\ell\cdot b}\|\boldsymbol{z}^{(A)}\|^{2}_{2}\ .$

###### Proof.

Using Lemma 3.2, the expectation of the average with attack size $r=B\ell^{2}$
is

$\displaystyle\frac{r}{\ell}\cdot\frac{2\sigma}{c+a}$
$\displaystyle=\frac{r}{\ell}\sqrt{\frac{m}{b}}\cdot\frac{2}{c+a}$
$\displaystyle=\frac{2}{c+a}\frac{\sqrt{r}}{\ell}\frac{1}{\sqrt{b}}\sqrt{r\cdot
m}$
$\displaystyle=\frac{2}{c+a}\sqrt{\frac{B}{b}}\|\boldsymbol{z}^{(A)}\|_{2}$
since $\|\boldsymbol{z}^{(A)}\|_{2}=\sqrt{r\cdot m}$

The variance of the average is

$\displaystyle\frac{r}{\ell}\sigma^{2}=\frac{r\cdot m}{\ell\cdot
b}=\frac{1}{\ell\cdot b}\|\boldsymbol{z}^{(A)}\|^{2}_{2}$

∎

###  3.3 Attack with an inner-product estimator

We describe the modifications to Algorithm 2 needed for the attack to apply
with an inner-product estimator. We compute the same query vectors
$\boldsymbol{v}^{(t)}_{t\in[r]}$. At each step $t$, the query response
algorithm chooses a correct inner-product estimator $M^{(t)}$ (see Definition
2.4). The query is issued for the inner product of $\boldsymbol{v}^{(t)}$ with
the standard basis vector $\boldsymbol{e}_{h}$. Note that the value of the
inner product is exactly $v^{(t)}_{h}$ and the requirement of correct
reporting of the inner product (Definition 2.4) on these query vectors matches
the requirement of a correct heavy hitters reporting of the key $h$
(Definition 2.2).

The input to the estimator are the sketches
$\text{{Sketch}}_{\rho}(\boldsymbol{e}_{h})$ and
$\text{{Sketch}}_{\rho}(\boldsymbol{v}^{(t)})$. Note that the information
available to the estimator from the provided sketches on $v^{(t)}_{h}$ is the
same as with heavy-hitter queries:
$\text{{Sketch}}_{\rho}(\boldsymbol{e}_{h})$ is simply the vector with entries
$\mu_{h}^{(j)}$, which does not add information as $\rho$ and $h$ are assumed
to be known to the estimator. The same analysis therefore applies.

##  4 Sketch distribution

In this section we show that with our particular query inputs (7), for large
enough $m$, the sketch content that is relevant to determining whether $h$ is
a candidate heavy hitter is approximately
$\boldsymbol{u}^{(t)}\sim\mathcal{N}_{\ell}(v^{(t)}_{h},\sigma^{2})$ where
$\sigma=\sqrt{\frac{m}{b}}$. The random variables
$\boldsymbol{u}^{*(t)}=\boldsymbol{u}^{(t)}-v^{(t)}_{h}\boldsymbol{1}_{\ell}$
for $t\in[r]$ are approximately i.i.d. from
$\mathcal{N}_{\ell}(0,\sigma^{2})$.

$\text{{CountSketch}}_{\rho}(\boldsymbol{v}^{(t)})$ includes $\ell\cdot b$
measurements but for inputs known to be of a form (7) we can restrict the
estimator to only consider the $\ell$ adjusted measurements (3) of key $h$. We
argue below that this restriction does not limit the power of the estimator.

To simplify our notation going forward, we re-index the set of relevant
measurement vectors and use $(\boldsymbol{\mu}^{(j)})_{j\in[\ell]}$ for
$(\boldsymbol{\mu}^{(j,h_{j}(h))})_{j\in[\ell]}$. We denote by
$\boldsymbol{u}^{(t)}\in\mathbb{R}^{\ell}$ the random variable vector of the
$\ell$ adjusted measurements (see Definition 3) the sketch provides for
$v^{(t)}_{h}$ and a random tail and by
$\boldsymbol{u}^{*(t)}\in\mathbb{R}^{\ell}$ the random variable of the
respective contributions of the tail component $\boldsymbol{z}^{(t)}$ to these
values:

$\displaystyle u^{*(t)}_{j}:=$
$\displaystyle\langle\boldsymbol{z}^{(t)},\boldsymbol{\mu}^{(j)}(\rho_{0})\rangle\cdot\mu^{(j)}_{h}(\rho_{0})$
(9) $\displaystyle u^{(t)}_{j}:=$
$\displaystyle\langle\boldsymbol{v}^{(t)},\boldsymbol{\mu}^{(j)}(\rho_{0})\rangle\cdot\mu^{(j)}_{h}(\rho_{0})=v^{(t)}_{h}+u^{*(t)}_{j}\
.$ (10)

######  Lemma 4.1.

The distribution of $(\boldsymbol{u}^{*(t)})_{t\in[r]}$ (over
$\rho\in\mathcal{D}$ and random tails selection) is such that $u^{*(t)}_{j}$
are i.i.d. for $t\in[r]$, $j\in[\ell]$) with distribution

$\displaystyle M^{(t)}_{j}$ $\displaystyle\sim\mathcal{B}(m,1/b)$
$\displaystyle u^{*(t)}_{j}$ $\displaystyle\sim
2\cdot\mathcal{B}(M^{(t)}_{j},\frac{1}{2})-M^{(t)}_{j}\ .$ (11)

###### Proof.

Note that the distribution of $(\boldsymbol{u}^{*(t)})_{t\in[r]}$ does not
depend on the choices of $(v^{(t)}_{h})_{t\in[r]}$.

Consider the distribution of $u^{*(t)}_{j}$ (for $t\in[r]$, $j\in[\ell]$). The
respective measurement vector is $\boldsymbol{\mu}^{(j)}$. We have
$|\texttt{supp}(\boldsymbol{z})|=m$ and for each
$i\in\texttt{supp}(\boldsymbol{z})$, $\mu^{(j)}_{i}\not=0$ with probability
$1/b$. Therefore, the number of keys in the support that contribute to the
measurement

$M^{(t)}_{j}:=\left|\\{i\mid z^{(t)}_{i}\cdot\mu^{(j)}_{i}\not=0\\}\right|$

is a Binomial random variable $M^{(t)}_{j}\sim\mathcal{B}(m,1/b)$, hence, has
expectation $\frac{m}{b}$ and variance $\frac{m}{b}$. The contributions of the
$M^{(t)}_{j}$ keys are i.i.d. Rademacher $U\\{-1,1\\}$ (multiplying by
$\mu^{(j)}_{h}$ which does not change that). Therefore, the contribution to
the measurement, conditioned on $M^{(t)}_{j}$, has distribution

$u^{*(t)}_{j}\sim 2\cdot\mathcal{B}(M^{(t)}_{j},\frac{1}{2})-M^{(t)}_{j}\ .$

Note that the random variables $u^{*(t)}_{j}$ are symmetric and
$\textsf{E}[u^{*(t)}_{j}]=0$.

Recall that the values $\mu^{(j)}_{i}$ for all keys $i\not=h$ and $j\in[\ell]$
are i.i.d. ($0$ with probability $(b-1)/b)$ and Rademacher otherwise). Recall
that the random tails are independent of the sketch randomness and the
supports $\texttt{supp}(\boldsymbol{z}^{(t)})$ for $t\in[r]$ are disjoint.
Even when conditioned on fixing the supports for all $t\in[r]$, all values of
keys within the support, across all $t\in[r]$, are i.i.d. Rademacher.

We now argue that $\boldsymbol{u}^{*(t)}$ are i.i.d. for different $t\in[r]$.
This follows from the disjoint supports of
$\texttt{supp}(\boldsymbol{z}^{(t)})$ for different $t\in[r]$ and therefore
(9) for different $t$ only depend on disjoint parts of each set of measurement
vectors $(\boldsymbol{\boldsymbol{\mu}^{(j)}})_{j\in[\ell]}$, with only values
for keys $i\in\texttt{supp}(\boldsymbol{z}^{(t)})$.

We next observe that for any $t\in[r]$, the values $u^{*(t)}_{j}$ are i.i.d.
for $j\in[\ell]$. In this case the applicable support
$\texttt{supp}(\boldsymbol{z}^{(t)})$ is fixed. But the applicable parts of
different measurement vectors $j\in[\ell]$ are independent. Even when there is
overlap in the sets of keys other than $h$ in
$\texttt{supp}(\boldsymbol{z}^{(t)})$ that map to different measurements, the
measurement vectors randomness is independent, so the contributions of the
same key to different measurements it maps to are independent $U\\{-1,1\\}$. ∎

We are now ready justify considering only the measurement with $\mu_{h}\not=0$
in each set $j\in[\ell]$: The additional measurements have
$\boldsymbol{\mu}_{h}=0$ and thus do not depend on $v_{h}$. They do provide
information on the tail support size parameter $m$ but we can assume $m$ is
known to the estimator. These measurements also provide information on
$M^{(t)}_{j}$, the number of keys in the support that hash to our selected
measurement from the each set of $b$ measurements. This because their sum has
distribution $\mathcal{B}(\mathcal{B}(m-M^{(t)}_{j},1/b),1/2)$. But in our
analysis we assume that $m$ is chosen to be large enough so that $M^{(t)}_{j}$
is very close to its expectation $m/b$ and we may also assume that the exact
values $M^{(t)}_{j}$ are available to the estimator (Essentially, the
variations in the value only impacts the "noise" magnitude but not its form).

######  Lemma 4.2.

The distribution of the random variable $\sum_{j\in[\ell]}u^{*(t)}_{j}$
conditioned on $\rho$ and $\boldsymbol{M}^{(t)}$ is

$2\mathcal{B}\left(\sum_{j\in[\ell]}M^{(t)}_{j},1/2\right)-\sum_{j\in[\ell]}M^{(t)}_{j}\
.$

###### Proof.

Taking the sum over $j\in[\ell]$ of the distributions of $u^{*(t)}_{j}$

$\displaystyle\sum_{j\in[\ell]}\left(2\mathcal{B}(M^{(t)}_{j},1/2)-M^{(t)}_{j}\right)$
$\displaystyle=$ $\displaystyle
2\sum_{j\in[\ell]}\mathcal{B}(M^{(t)}_{j},1/2)-\sum_{j\in[\ell]}M^{(t)}_{j}$
$\displaystyle=$ $\displaystyle
2\mathcal{B}(\sum_{j\in[\ell]}M^{(t)}_{j},1/2)-\sum_{j\in[\ell]}M^{(t)}_{j}\
,$

where the last equality follows from properties of a sum of independent
Binomial random variables. ∎

######  Remark 4.3.

We choose $m$ to be large enough so that the following approximations hold:

  * (i)

The independent random variables $M^{(t)}_{j}\sim\mathcal{B}(m,1/b)$ are close
to their mean $m/b$ for all $t\in[r]$ and $j\in[\ell]$: More precisely, for
some $\alpha$ and $\delta^{\prime}$, with probability $(1-\delta^{\prime})$,
for all $t,j$, $(M^{(t)}_{j}\in 1\pm\alpha)m/b$. We bound this using Chernoff
bounds. We solve $2\exp(-\frac{m}{b}\alpha^{2}/3\leq\delta^{\prime}/(r\ell)$
to obtain $m\geq 3b\alpha^{-2}\ln(2r\ell/\delta^{\prime})$.

  * (ii)

With probability $(1-\delta^{\prime})$, $r\ell$ random variables
$\mathcal{B}(n,1/2)$ where $n$ is in $(1\pm\alpha)m/b$, are all within
$O(n^{2/3}\alpha)$ from their expected value $n/2$. When this holds, the
normal approximation to the Binomial distribution has relative error within
$1\pm\alpha$. We again apply Chernoff bounds solving for
$2\exp(-(n/2)(n^{-1/3}\alpha)^{2}/3\leq\delta^{\prime}/(r\ell)$ solving we get
$n^{1/3}\geq 6\alpha^{-2}\ln(2r\ell/\delta^{\prime})$ and therefore
$m=O(b\alpha^{-6}\ln(2r\ell/\delta^{\prime})^{3})$.

When $m/b$ is large in the sense of Remark 4.3, the distribution of
$u^{*(t)}_{j}$ is approximated well by $\mathcal{N}(0,m/b)$ and
$\boldsymbol{u}^{*(t)}$ is approximated by $\mathcal{N}_{\ell}(0,m/b)$ and
therefore

$\displaystyle\boldsymbol{u}^{(t)}$ $\displaystyle\sim$
$\displaystyle\mathcal{N}_{\ell}(v^{(t)}_{h},\frac{m}{b})$ (12)
$\displaystyle\overline{u}$ $\displaystyle\sim$
$\displaystyle\mathcal{N}(v^{(t)}_{h},\frac{m}{b}\cdot\frac{1}{\ell})\ .$ (13)

The approximation is up to a relative error of $\alpha=\alpha^{\prime}/\ell$
and discretization. We use $\alpha=\alpha^{\prime}/\ell$ so that a relative
error approximation of $1\pm\alpha^{\prime}$ holds also with respect to a
product distribution of $\ell$ such random variables. For the purpose of
cleaner presentation, we will use this approximation going forward. We use
$\sigma:=\sqrt{\frac{m}{b}}$. The analysis carries over by carefully dragging
the approximation error term that vanishes for large $m$.

##  5 Estimators

In this section we provide a framework of estimators and establish properties
common to any correct $\ell_{2}$-$\epsilon$ heavy hitters estimator that is
applied to our query vectors.

In its most general form, a query response algorithm fixes before each query
$t$ an estimator $M^{(t)}$. The estimator is applied to the content of the
sketch, which on our inputs are i.i.d. vectors
$(\boldsymbol{u}^{(t)}\sim\mathcal{N}_{\ell}(v^{(t)}_{h},\sigma^{2}))_{t\in[r]}$.
The estimator is specified by a reporting function
$p^{(t)}:\mathbb{R}^{\ell}\to[0,1]$ so that
$p^{(t)}(\boldsymbol{u}^{(t)}):=\textsf{Pr}[h\in
M^{(t)}(\boldsymbol{u}^{(t)})]$ specifies the probability that the returned
$K^{(t)}$ includes key $h$ when the sketch content is $\boldsymbol{u}^{(t)}$.
We allow the query response algorithm to modify the estimator arbitrarily
between queries and in a way that depends on sketches of prior inputs, prior
outputs, and on a maintained state from past queries
$(\boldsymbol{u}^{(t^{\prime})},K^{(t^{\prime})})_{t^{\prime}<t}$. The only
constraint that we impose is that (at each step $t$) the output is correct
with high probability: $\ell_{2}$-$\epsilon$-heavy hitters are reported and
$0$ value keys are not reported (see Definition 2.2). We show that a correct
estimator on our query inputs must satisfy the following:

######  Lemma 5.1 (Correct HH estimator basic property).

For $\delta_{1},\delta_{2}\ll 1$, there are
$a=\Theta(\sqrt{\frac{\ln(1/\delta_{2})}{\ell}})$ and $c=\Theta(1)$ so that
the following holds. If the estimator satisfies (i) if $h$ is a heavy hitter
then $\textsf{Pr}[h\in K]\geq 1-\delta_{1}$ and (ii) if $v_{h}=0$ then
$\textsf{Pr}[h\not\in K]\geq 1-\delta_{2}$. Then

  * •

$|v_{h}|\geq c\cdot\sigma$ $\implies$ $\textsf{Pr}[h\in K]\geq 1-\delta_{1}$

  * •

$|v_{h}|\leq a\cdot\sigma$ $\implies$ $\textsf{Pr}[h\not\in K]\geq
1-\frac{1}{\delta_{2}^{\Omega(1)}}$

  * •

Otherwise, unrestricted

###### Proof.

The tail vectors have $\ell_{2}^{2}$ mass $\|\boldsymbol{z}\|^{2}_{2}=m$ and
$\|\boldsymbol{v}^{(t)}\|^{2}_{2}=m+(v^{(t)}_{h})^{2}$. Key $h$ is $\ell_{2}$
$\epsilon$-heavy hitter (see Definition 2.1) when

$\displaystyle
v_{h}^{2}\geq\epsilon\cdot\|\boldsymbol{v}\|_{2}^{2}=\epsilon\cdot(v_{h}^{2}+\|\boldsymbol{z}\|_{2}^{2})\implies$
$\displaystyle
v_{h}^{2}\geq\frac{\epsilon}{1-\epsilon}\|\boldsymbol{z}\|_{2}^{2}=\frac{\epsilon}{1-\epsilon}m=\frac{b\epsilon}{1-\epsilon}\cdot\sigma\
.$

Recall that the sketch uses $b=O(1/\varepsilon)$, so when
$c\approx\frac{b\epsilon}{1-\epsilon}=\Theta(1)$ we get that $|v_{h}|\geq
c\cdot\sigma$ implies that $h$ is $\ell_{2}$ $\epsilon$-heavy hitter.
Therefore an estimator that reports a heavy key with probability at least
$1-\delta_{1}$ must have $\textsf{Pr}[h\in K]\geq 1-\delta_{1}$.

We now establish the second part. Here we show that if the probability of
reporting when $v_{h}=0$ is at most $\delta_{2}$ then the probability of
reporting when $|v_{h}|\leq a\cdot\sigma$ is at most $\delta_{2}^{1/4}$. The
probability density of a sketch $\boldsymbol{u}$ when $v_{h}=v$ is:

$f_{v}(\boldsymbol{u})=\prod_{i\in[\ell]}\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}\left(\frac{u_{i}-v}{\sigma}\right)^{2}}\
,$

We seek to bound the maximum the maximum reporting probability when $v_{h}\leq
a$ subject to reporting probability of $0$ that is at most $\delta_{2}$.
Consider the ratio

$\frac{f_{v}(\boldsymbol{u})}{f_{0}(\boldsymbol{u})}=e^{-\frac{1}{2\sigma^{2}}\left(\ell\cdot
v^{2}-2\cdot
v\cdot\sum_{i}u_{i}\right)}=e^{-\frac{1}{2\sigma^{2}}\left(\ell\cdot(v^{2}-2v\overline{u})\right)}$

Note that the ratio depends only on $\overline{u}$ and $v$ and is larger when
$\overline{u}$ is closer to $v$ than to $0$. Therefore, for the goal of
bounding the maximum reporting probability with $v$ subject on a bound on the
probability for $0$, we place the reporting probability when $0$ on the
largest values of $\overline{u}$. The distribution of $\overline{u}$ with $0$
mean is $\mathcal{N}(0,\sigma^{2}/\ell)$. For
$\overline{u}\geq\frac{\sigma}{\sqrt{\ell}}\sqrt{\ln(1/\delta_{2})}$ provides
reporting probability $\Theta(1/\delta_{2})$ for $0$. For
$v=\frac{1}{2}\frac{\sigma}{\sqrt{\ell}}\sqrt{\ln(1/\delta_{2})}$ the
reporting probability is $\frac{1}{\delta_{2}^{\Omega(1)}}$.

∎

##  6 Simplified Mean Estimation

In this section we formulate and state properties of an interaction, described
as Algorithm 3, with a mean estimator of i.i.d random variables. We then show
a correspondence between Algorithm 2 and Algorithm 3 establish properties of
Algorithm 2 through this correspondence. In Section 8 we apply this
formulation to analyse an attack on norm estimators applied to the AMS sketch.

We use the following definition:

######  Definition 6.1 (correct reporting function).

A reporting function $p:\mathbb{R}^{\ell}\to[0,1]$ is correct with respect to
parameters: $(\delta,a,c,\ell,\sigma)$ if

$\displaystyle\forall v\geq c\cdot\sigma,\
\textsf{E}_{\boldsymbol{u}\sim\mathcal{N}_{\ell}(v,\sigma^{2})}[p^{(t)}(\boldsymbol{u})]\geq
1-\delta$ $\displaystyle\forall v\leq a\cdot\sigma,\
\textsf{E}_{\boldsymbol{u}\sim\mathcal{N}_{\ell}(v,\sigma^{2})}[p^{(t)}(\boldsymbol{u})]\leq\delta\
.$

A correct reporting function can be viewed as a simple mean estimator applied
to $\ell$ i.i.d. samples from $\mathcal{N}(v,\sigma^{2})$: With probability
$1-\delta$, the output is $1$ when $|v|>c\cdot\sigma$ and $-1$ when
$|v|<a\cdot\sigma$.

We will establish the following (proof provided in Section 7):

######  Lemma 6.2 (MeanEstAttack Properties).

Consider Algorithm 3 where $b$ is such that

$\sqrt{\frac{\ell}{2\pi}}e^{-\ell b^{2}/2}\ll\frac{1}{c-a+2b}.$

Then the output $\boldsymbol{u}^{(A)}\in\mathbb{R}^{\ell}$ satisfies

$\displaystyle\textsf{E}_{\mathcal{A}}\left[\overline{u^{(A)}}\right]$
$\displaystyle\approx\frac{r}{\ell}\cdot\frac{2\sigma}{c-a+2b}$ (14)
$\displaystyle\frac{r}{\ell}\sigma^{2}\left(1-\frac{2b}{c-a+2b}\right)^{2}$
$\displaystyle\lessapprox\textsf{Var}_{\mathcal{A}}\left[\overline{u^{(A)}}\right]\lessapprox\frac{r}{\ell}\sigma^{2}$
(15)

Input: Parameters $(a,c,\sigma,\delta)$, number of queries $r$, $b\in(0,a]$, A
query response algorithm $\mathcal{A}$ that chooses
$(a,c,\sigma,\delta)$-correct reporting functions

for  _$t\in[r]$_ do // Generate queries and reporting functions

$\mathcal{A}$ chooses a $(a,c,\sigma,\delta)$-correct reporting function
$p^{(t)}:\mathbb{R}^{\ell}\to[0,1]$

// Definition 6.1. Choice may depend on
$(\boldsymbol{u}^{(t^{\prime})},s^{(t^{\prime})})_{t^{\prime}<t}$

$v^{(t)}\sim\mathcal{U}[a\cdot\sigma,(c+2b)\cdot\sigma]$

$\boldsymbol{u}^{*(t)}\sim\mathcal{N}_{\ell}(0,\sigma^{2})$

for  _$j\in[\ell]$_ do $u^{(t)}_{j}\leftarrow v^{(t)}+u^{*(t)}_{j}$

// Compute $\boldsymbol{u}^{(t)}\in\mathbb{R}^{\ell}$, note that
$\boldsymbol{u}^{(t)}\sim\mathcal{N}_{\ell}(v^{(t)},\sigma^{2})$
$s^{(t)}\leftarrow 1$ w.p. $p^{(t)}(\boldsymbol{u}^{(t)})$ and
$s^{(t)}\leftarrow-1$ otherwise

return
_$\boldsymbol{u}^{(A)}\leftarrow\sum_{t\in[r]}s^{(t)}\boldsymbol{u}^{*(t)}$_

Algorithm 3 MeanEstAttack

###  6.1 Correspondence between the attack on CountSketch and MeanEstAttack

We state the attack on CountSketch in Algorithm 2 in terms of Algorithm 3.

We first relate the correctness of an estimator to correctness of its
reporting function (proof is immediate):

######  Lemma 6.3.

If for parameters $\delta,a,c,\ell,\sigma$ an estimator satisfies (i)
$|v_{h}|\geq c\cdot\sigma$ $\implies$ $\textsf{Pr}[h\in K]\geq 1-\delta$ and
(ii) $|v_{h}|\leq a\cdot\sigma$ $\implies$ $\textsf{Pr}[h\not\in K]\geq
1-\delta$, then its reporting function $p$ is correct with respect to
parameters $(\delta,a,c,\ell,\sigma)$.

It follows that an estimator that satisfies the conditions of Lemma 5.1 has a
reporting function that is correct as in Definition 6.1 for parameters
$(\max\\{\delta_{1},\delta_{2}^{\Omega(1)}\\},a,c,\ell,\sigma)$.

In the correspondence between Algorithm 2 and Algorithm 3, the reporting
function $M^{(t)}$ corresponds to $p^{(t)}$, the values $v^{(t)}_{h}$ to
$v^{(t)}$, the adjusted measurements of key $h$ from the sketch of
$\boldsymbol{v}^{(t)}$ correspond to $\boldsymbol{u}^{(t)}$, the adjusted
measurements of key $h$ from the sketch of $\boldsymbol{z}^{(t)}$ corresponds
to $\boldsymbol{u}^{*(t)}$, and $s^{(t)}$ plays the same role. The adjusted
measurements of the output of Algorithm 2, adversarial vector
$\boldsymbol{z}^{(A)}$, correspond to the output $\boldsymbol{u}^{(A)}$ of
Algorithm 3. The parameter values $a,c$ are the same and the parameter $b$ in
Algorithm 3 (unrelated to the sketch parameter) is set to $b\leftarrow a$.

Using this correspondence, we can now provide a proof of Lemma 3.2 (Properties
of the adversarial tail). The Lemma follows as a Corollary of Lemma 6.2 using
the established relation between Algorithm 2 and Algorithm 3 and
$b=a=\Theta(\sqrt{\ln(1/\delta_{2})/\ell}$. When $\delta_{2}$ as used to
determine $a$ in Lemma 5.1 is small enough, we have
$\sigma\cdot\sqrt{\frac{2}{\pi\ell}}e^{-\ell
a^{2}/2}\approx\sigma\cdot\sqrt{\frac{2\cdot\delta_{2}}{\pi\ell}}$ and the
condition of Lemma 6.2 holds.

###### Proof of Lemma 3.2.

The contributions of the adversarial tail to the adjusted estimates in the
sketch are:

$\displaystyle\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}\rangle\cdot\mu^{(j)}_{h}=\sum_{t\in[r]}s^{(t)}\langle\boldsymbol{z}^{(t)},\boldsymbol{\mu}^{(j)}\rangle\cdot\mu^{(j)}_{h}=\sum_{t\in[r]}s^{(t)}(u^{(t)}_{j}-v^{(t)}_{h})=\sum_{t\in[r]}s^{(t)}u^{*(t)}_{j}\
.$

Therefore

$\displaystyle\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}\rangle\cdot\mu^{(j)}_{h}$
$\displaystyle=\frac{1}{\ell}\sum_{j\in[\ell]}\sum_{t\in[r]}s^{(t)}u^{*(t)}_{j}$
(16)
$\displaystyle=\sum_{t\in[r]}s^{(t)}\frac{1}{\ell}\sum_{j\in[\ell]}u^{*(t)}_{j}$
$\displaystyle=\sum_{t\in[r]}s^{(t)}\overline{u^{*(t)}}=\overline{u^{(A)}}\ .$

Using Lemma 6.2 and noting that our settings of $a,c$ (see Lemma 5.1) have
$c-a\gg a$ we obtain the claim:

$\displaystyle\textsf{E}_{\rho,\mathcal{A}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}\rangle\cdot\mu^{(j)}_{h}\right]$
$\displaystyle\approx\frac{r}{\ell}\cdot\frac{2\sigma}{c+a}$
$\displaystyle\textsf{Var}_{\rho,\mathcal{A}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{z}^{(A)},\boldsymbol{\mu}^{(j)}\rangle\cdot\mu^{(j)}_{h}\right]$
$\displaystyle\approx\frac{r}{\ell}\cdot\sigma^{2}$

∎

##  7 Proofs for MeanEstAttack Properties

We provide the proof details for Lemma 6.2. At a high level, we show that for
each $t\in[r]$, the value $s^{(t)}$ is correlated with the sign of the
normalized bias of the sample:

$\alpha^{(t)}:=\frac{\overline{u^{*(t)}}}{\sigma}=\frac{\overline{u^{(t)}}-v^{(t)}}{\sigma}\
.$ (17)

For $t\in[r]$ with reporting function $p$ we define (superscript $(t)$ omitted
for readability from $p$, $\pi$)

$\displaystyle\pi(v)$ $\displaystyle:=\textsf{Pr}[s^{(t)}=1\mid
v^{(t)}=v]=\textsf{E}_{\boldsymbol{u}\sim\mathcal{N}_{\ell}(v,\sigma^{2})}[p(\boldsymbol{u})]$
(18) $\displaystyle\pi(v\mid\alpha)$
$\displaystyle:=\textsf{Pr}\left[s^{(t)}=1\mid v^{(t)}=v\textbf{ and
}\frac{\overline{u}-v}{\sigma}=\alpha\right]=\textsf{E}_{\boldsymbol{u}\sim\mathcal{N}_{\ell}(v,\sigma^{2})\mid\frac{\overline{u}-v}{\sigma}=\alpha}[p(\boldsymbol{u})]$
(19)

The probability of $s^{(t)}=1$ when $v^{(t)}=v$ and the probability of
$s^{(t)}=1$ when $v^{(t)}=v$ and  $\alpha^{(t)}=\alpha$. Note that since
$\overline{u}\sim\mathcal{N}(v,\sigma^{2}/\ell)$ we have
$\alpha^{(t)}\sim\mathcal{N}(0,1/\ell)$.

We will establish the following:

######  Lemma 7.1 (Gap Lemma).

For $0<\alpha\leq b\leq a$ (with probability $1-O(\delta)$ over the
distribution of $\alpha$) and for any correct reporting function $p$ (and
respective $\pi$)

$\textsf{E}_{v\sim\mathcal{U}[(a,(c+2b)\cdot\sigma]}[\pi(v\mid\alpha)-\pi(v\mid-\alpha)]\approx\frac{2\alpha}{c-a+2b}.$

This Lemma implies that when $v^{(t)}\sim\sigma\cdot[a,c+2b]$ then any correct
estimator would exhibit a gap in the probability of reporting $s^{(t)}=1$,
depending on the sign of the normalized bias $\alpha^{(t)}$. The gap increases
with the magnitude $|\alpha^{(t)}|$. Note that the statement is on the
expected difference between the reporting probabilities for positive or
negative bias. The expected probabilities
$\textsf{E}_{v\sim\mathcal{U}[(a,(c+2b)\cdot\sigma]}[\pi(v\mid\alpha)$ and
$\textsf{E}_{v\sim\mathcal{U}[(a,(c+2b)\cdot\sigma]}[\pi(v\mid-\alpha)$ can
vary wildly, be both close to $0$ or close to $1$, for different correct
reporting functions.

###  7.1 Proof of Lemma 7.1

We will use two Lemmas. The first uses the fact that the reporting probability
as a function of $v^{(t)}$ has total increase of almost $1$ between
$v=a\cdot\sigma$ to $v=c\cdot\sigma$ to establish its average increases over
uniformly random sub-intervals of length $2\alpha\sigma$:

######  Lemma 7.2 (Average increase property).

For $0<\alpha\leq b\leq a$ (with probability $1-O(\delta)$ over the
distribution)

$\textsf{E}_{v\sim\mathcal{U}[(a,(c+2b)\cdot\sigma]}[\pi(v\mid\alpha)-\pi(v-2\cdot\alpha\cdot\sigma\mid\alpha)]\approx\frac{2\alpha}{c-a+2b}.$

###### Proof.

From Corollary 6.3, for almost all values of $\alpha$ (probability
$1-O(\delta)$ over the distribution of $\alpha\sim\mathcal{N}(0,1/\ell)$) we
must have that the function $\pi(v\mid\alpha)$ is very close (within a small
constant of our choice) to $0$ when $|v|\leq a\cdot\sigma$ and very close to
$1$ when $|v|\geq c\cdot\sigma$.

$\displaystyle\textsf{E}_{v\sim\mathcal{U}[a\cdot\sigma,(c+2b)\cdot\sigma]}[\pi(v\mid\alpha)-\pi(v-2\alpha\cdot\sigma\mid\alpha)]$
$\displaystyle=\frac{1}{c-a+2b}\int_{a\cdot\sigma}^{(c+2b)\cdot\sigma}\pi(v\mid\alpha)-\pi(v-2\alpha\cdot\sigma\mid\alpha)dv$
$\displaystyle=\frac{1}{c-a+2b}\left(\int_{a\cdot\sigma}^{(c+2b)\cdot\sigma}\pi(v\mid\alpha)dv-\int_{(a-2\alpha)\cdot\sigma}^{(c+2b-2\alpha)\cdot\sigma}\pi(v\mid\alpha)dv\right)$
$\displaystyle=\frac{1}{c-a+2b}\left(-\int_{(a-2\alpha)\cdot\sigma}^{a\cdot\sigma}\pi(v\mid\alpha)dv+\int_{(c+2b-2\alpha)\cdot\sigma}^{(c+2b)\cdot\sigma}\pi(v\mid\alpha)dv\right)\approx\frac{2\alpha}{c-a+2b}$

∎

The following Lemma shows that the probability of reporting $s^{(t)}=1$, is
equally likely when $v^{(t)}=v+\alpha\cdot\sigma$ and $\overline{u}=v$ and
when $v^{(t)}=v-\alpha\cdot\sigma$ and $\overline{u}=v$:

######  Lemma 7.3.

For any $\alpha>0$, reporting function $p()$, and $v$,
$\pi(v+\alpha\cdot\sigma\mid-\alpha)=\pi(v-\alpha\cdot\sigma\mid+\alpha)$.

###### Proof.

From (19):

$\displaystyle\pi(v+\alpha\cdot\sigma\mid-\alpha)$
$\displaystyle=\frac{1}{\int_{\boldsymbol{u}\mid\overline{u}=v}f_{v+\alpha\cdot\sigma}(\boldsymbol{u})d\boldsymbol{u}}\cdot\int_{\boldsymbol{u}\mid\overline{u}=v}f_{v+\alpha\cdot\sigma}(\boldsymbol{u})\cdot
p(\boldsymbol{u})d\boldsymbol{u}$
$\displaystyle\pi(v-\alpha\cdot\sigma\mid\alpha)$
$\displaystyle=\frac{1}{\int_{\boldsymbol{u}\mid\overline{u}=v}f_{v+\alpha\cdot\sigma}(\boldsymbol{u})d\boldsymbol{u}}\cdot\int_{\boldsymbol{u}\mid\overline{u}=v}f_{v-\alpha\cdot\sigma}(\boldsymbol{u})\cdot
p(\boldsymbol{u})d\boldsymbol{u}$

The probability $\pi(v+\alpha\cdot\sigma\mid-\alpha)$ is the mean over
$\boldsymbol{u}$ with $\overline{u}=v$ of
$f_{v+\alpha\cdot\sigma}(\boldsymbol{u})\cdot p(\boldsymbol{u})$. Similarly,
$\pi(v-\alpha\cdot\sigma\mid\alpha)$ is the mean over $\boldsymbol{u}$ with
$\overline{u}=v$ of $f_{v-\alpha\cdot\sigma}(\boldsymbol{u})\cdot
p(\boldsymbol{u})$. It therefore suffices to establish that
$f_{v-\alpha\cdot\sigma}(\boldsymbol{u})=f_{v+\alpha\cdot\sigma}(\boldsymbol{u})$
for $\boldsymbol{u}$ when $\overline{u}=v$ .

This is a property of a product of normal distributions: for any
$\boldsymbol{u}\in\mathbb{R}^{\ell}$ and $\alpha$, the outcome
$\boldsymbol{u}$ is equally likely with
$\mathcal{N}_{\ell}(\overline{u}+\alpha\cdot\sigma,\sigma^{2})$ and
$\mathcal{N}_{\ell}(\overline{u}-\alpha\cdot\sigma,\sigma^{2})$:

$f_{\overline{u}+\alpha\cdot\sigma}(\boldsymbol{u})=f_{\overline{u}-\alpha\cdot\sigma}(\boldsymbol{u}).$

We express $\boldsymbol{u}$ in terms of the empirical mean
$\overline{u}:=\frac{1}{\ell}\sum_{j}u_{j}$ and the "deviations" from the
empirical mean $(\Delta_{j}=u_{j}-\overline{u})_{j=1}^{\ell}$. Note that by
definition $\sum_{j\in[\ell]}\Delta_{j}=0$. Let $\alpha>0$, using (2) and
$\sum_{i}\Delta_{i}=0$ we obtain:

$\displaystyle f_{\overline{u}+\alpha\cdot\sigma}(\boldsymbol{u})=$
$\displaystyle\prod_{i\in[\ell]}\frac{1}{\sigma\sqrt{2\pi}}\exp{-\left(\frac{\overline{u}+\Delta_{i}-(\overline{u}+\alpha\cdot\sigma)}{\sigma}\right)^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{(\sigma\sqrt{2\pi})^{\ell}}\exp\left(\frac{-\sum_{i=1}^{\ell}(\Delta_{i}^{2}+\alpha^{2}\cdot\sigma^{2}-2\alpha\cdot\sigma\Delta_{i})}{\sigma^{2}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{(\sigma\sqrt{2\pi})^{\ell}}\exp\left(\frac{-\ell\alpha^{2}\cdot\sigma^{2}-\sum_{i=1}^{\ell}\Delta_{i}^{2}+2\alpha\cdot\sigma\cdot\sum_{i=1}^{\ell}\Delta_{i})}{\sigma^{2}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{(\sigma\sqrt{2\pi})^{\ell}}\exp\left(\frac{-\ell\alpha^{2}\cdot\sigma^{2}-\sum_{i=1}^{\ell}\Delta_{i}^{2}}{\sigma^{2}}\right)=\frac{1}{(\sigma\sqrt{2\pi})^{\ell}}\exp\left(-\ell\alpha^{2}-\frac{\sum_{i=1}^{\ell}\Delta_{i}^{2}}{\sigma^{2}}\right)$

The calculation for $f_{\overline{u}-\alpha\cdot\sigma}(\boldsymbol{u})$ is
similar and yields the same expression:

$\displaystyle f_{\overline{u}-\alpha\cdot\sigma}(\boldsymbol{u})=$
$\displaystyle\prod_{i\in[\ell]}\frac{1}{\sigma\sqrt{2\pi}}\exp{-\left(\frac{\overline{u}+\Delta_{i}-(\overline{u}-\alpha\cdot\sigma)}{\sigma}\right)^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{(\sigma\sqrt{2\pi})^{\ell}}\exp\left(\frac{-\sum_{i=1}^{\ell}(\Delta_{i}^{2}+\alpha^{2}\cdot\sigma^{2}+2\alpha\cdot\sigma\Delta_{i})}{\sigma^{2}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{(\sigma\sqrt{2\pi})^{\ell}}\exp\left(\frac{-\ell\alpha^{2}\cdot\sigma^{2}-\sum_{i=1}^{\ell}\Delta_{i}^{2}-2\alpha\cdot\sigma\cdot\sum_{i=1}^{\ell}\Delta_{i})}{\sigma^{2}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{(\sigma\sqrt{2\pi})^{\ell}}\exp\left(-\ell\alpha^{2}-\frac{\sum_{i=1}^{\ell}\Delta_{i}^{2}}{\sigma^{2}}\right)$

∎

Lemma 7.1 follows as a corollary of Lemma 7.2 and Lemma 7.3: From Lemma 7.2 we
get that $\pi(v-2\cdot\alpha\cdot\sigma\mid\alpha)=\pi(v\mid-\alpha)$. By
making this substitution in the statement of Lemma 7.3 we obtain Lemma 7.1.

###  7.2 Output properties

In this section we provide a proof of Lemma 6.2 that states properties of the
expectation and variance of the average entry value of the output vector.
Additionally, we bound from below the $\ell_{2}$ norm (Lemma 7.4). We use the
bound on the $\ell_{2}$ norm in Section 8.

###### Proof of Lemma 6.2.

From linearity of expectation,

$\textsf{E}_{\mathcal{A}}\left[\overline{u^{(A)}}\right]=\textsf{E}\left[\sum_{t\in[r]}s^{(t)}(\overline{u}^{(t)}-v^{(t)}))\right]=\sigma\textsf{E}\left[\sum_{t\in[r]}s^{(t)}\alpha^{(t)}\right]=\sigma\sum_{t\in[r]}\textsf{E}[s^{(t)}\alpha^{(t)}],$
(20)

where $\alpha^{(t)}$ is the normalized bias (17). We now consider the
contribution of a single query $t\in[r]$:

$\textsf{E}[s^{(t)}\alpha^{(t)}]\ .$ (21)

Recall that the distribution of $\alpha^{(t)}$ is $\mathcal{N}(0,1/\ell)$. We
condition on $|\alpha^{(t)}|=\alpha$ for $\alpha\geq 0$ which has the density
function

$2\sqrt{\frac{\ell}{2\pi}}e^{-\frac{1}{2}\ell\alpha^{2}}.$ (22)

We have $s^{(t)}\alpha^{(t)}=\alpha$ if $\alpha^{(t)}=\alpha$ and $s^{(t)}=1$
or when $\alpha^{(t)}=\alpha=-\alpha$ and $s^{(t)}=-1$. Similarly,
$s^{(t)}\alpha^{(t)}=-\alpha$ if $\alpha^{(t)}=\alpha$ and $s^{(t)}=-1$ or
when $\alpha^{(t)}=-\alpha$ and $s^{(t)}=1$.

We now express the expected contribution under this conditioning, for fixed
$v^{(t)}$ and fixed correct reporting function $p$. We use that since the
distribution of $\alpha^{(t)}$ (for fixed $v^{(t)}$) is symmetrical, there is
equal probability $1/2$ for each of $\alpha^{(t)}=\pm\alpha$. We use
$\pi(v\mid\alpha)$ as defined in (19).

$\displaystyle\textsf{E}_{p}[s^{(t)}\alpha^{(t)}\mid\alpha^{(t)}=\alpha]=\textsf{E}_{\mathcal{A}}[s^{(t)}(\frac{\overline{u}^{(t)}-v^{(t)}}{\sigma})\mid\frac{|\overline{u}^{(t)}-v^{(t)}|}{\sigma}=\alpha]=$
$\displaystyle=\frac{1}{2}\alpha\left(\pi(v^{(t)}\mid\alpha)-\pi(v^{(t)}\mid-\alpha)-(1-\pi(v^{(t)}\mid\alpha))+(1-\pi(v^{(t)}\mid-\alpha))\right)$
$\displaystyle=\frac{1}{2}\alpha\left(2\pi(v^{(t)}\mid\alpha)-2\pi(v^{(t)}\mid-\alpha)\right)=\alpha\left(\pi(v^{(t)}\mid\alpha)-\pi(v^{(t)}\mid-\alpha)\right)$

We take the expectation over
$v^{(t)}\sim\mathcal{U}[a\cdot\sigma,(c+2b)\cdot\sigma]$ and apply Lemma 7.1.
We obtain that for $\alpha\in[0,b]$:

$\displaystyle\textsf{E}_{v^{(t)},p}[s^{(t)}\alpha^{(t)}\mid\alpha^{(t)}=\alpha]=$
$\displaystyle=\alpha\textsf{E}_{v\sim\mathcal{U}[a\cdot\sigma,(c+2b)}[\pi(v\mid\alpha)-\pi(v\mid-\alpha)]\approx\alpha\frac{2\alpha}{c-a+2b}=\frac{2\alpha^{2}}{c-a+2b}$

Finally, we now take the expectation over $\alpha\geq 0$ using the density
(22):

$\displaystyle\textsf{E}_{v^{(t)},p}[s^{(t)}\alpha^{(t)}]$
$\displaystyle=\int_{0}^{\infty}(2\cdot\sqrt{\frac{\ell}{2\pi}}e^{-\frac{1}{2}\ell\alpha^{2}})\textsf{E}_{v,p}[s^{(t)}\alpha^{(t)}\mid|\alpha^{(t)}|=\alpha]d\alpha$
$\displaystyle\approx\frac{2}{c-a+2b}2\cdot\sqrt{\frac{\ell}{2\pi}}\int_{0}^{\infty}\alpha^{2}e^{-\frac{1}{2}\ell\alpha^{2}}d\alpha$
$\displaystyle=\frac{4}{c-a+2b}\cdot\sqrt{\frac{\ell}{2\pi}}\ell^{-3/2}\sqrt{\frac{\pi}{2}}=\frac{1}{\ell}\cdot\frac{2}{c-a+2b}$
(23)

Noting that the approximation holds as the contribution of
$\alpha\in[b,\infty)$ is negligible when the condition on $b$ holds:

$\displaystyle\int_{b}^{\infty}(2\cdot\sqrt{\frac{\ell}{2\pi}}e^{-\frac{1}{2}\ell\alpha^{2}})\left|\textsf{E}_{v^{(t)},p}[s^{(t)}\alpha^{(t)}\mid|\alpha^{(t)}|=\alpha]\right|d\alpha$
$\displaystyle\leq\int_{b}^{\infty}(2\cdot\sqrt{\frac{\ell}{2\pi}}e^{-\frac{1}{2}\ell\alpha^{2}})\alpha
d\alpha\leq\sqrt{\frac{2}{\pi\ell}}e^{-\ell b^{2}/2}$

Substituting (23) in (20) we establish claim (14) of the Lemma:
$\textsf{E}_{\mathcal{A}}[\overline{u^{(A)}}]\approx\frac{r}{\ell}\sigma\cdot\frac{2}{c-a+2b}$.

We now bound (using independence of $s^{(t)}\alpha^{(t)}$ for different $t$
and thus linearity of the variance)

$\textsf{Var}_{\mathcal{A}}\left[\overline{u^{(A)}}\right]=\textsf{Var}\left[\sum_{t\in[r]}s^{(t)}(\overline{u}^{(t)}-v^{(t)}))\right]=\sigma^{2}\textsf{Var}\left[\sum_{t\in[r]}s^{(t)}\alpha^{(t)}\right]=\sigma^{2}\sum_{t\in[r]}\textsf{Var}[s^{(t)}\alpha^{(t)}].$
(24)

We bound

$\textsf{Var}[s^{(t)}\alpha^{(t)}].$ (25)

We condition on $|\alpha^{(t)}|=\alpha$ and take expectation over $v$,
applying Lemma 7.1: We have $s^{(t)}\alpha^{(t)}=\alpha$ with probability

$\frac{1}{2}\textsf{E}_{v}[\pi(v\mid\alpha)-(1-\pi(v\mid-\alpha))]=\frac{1}{2}+\frac{\alpha}{c-a+2b}$

and (similarly) $s^{(t)}\alpha^{(t)}=-\alpha$ with probability
$\frac{1}{2}-\frac{\alpha}{c-a+2b}$. We obtain

$\displaystyle\textsf{Var}[s^{(t)}\alpha^{(t)}\mid|\alpha^{(t)}|=\alpha]=$
$\displaystyle=\textsf{E}[(s^{(t)}\alpha^{(t)})^{2}\mid|\alpha^{(t)}|=\alpha]-\textsf{E}[s^{(t)}\alpha^{(t)}\mid|\alpha^{(t)}|=\alpha]^{2}=\alpha^{2}\left(1-\left(\frac{2\alpha}{c-a+2b}\right)^{2}\right)\
.$ (26)

Since $\alpha\in[0,b]$ we have

$1-\frac{2b}{c-a+2b}\leq 1-\frac{2\alpha}{c-a+2b}\leq 1\ .$

Take the expectation of (26) over $\alpha\geq 0$ using these bounds and
density (22) we obtain

$\displaystyle\frac{1}{\ell}\left(1-\frac{2b}{c-a+2b}\right)^{2}\leq\textsf{Var}_{v^{(t)},p}[s^{(t)}\alpha^{(t)}]\leq\frac{1}{\ell}\
.$ (27)

Claim (15) in the statement of the Lemma follows by substituting (27) in (24).
In the regime where $c-a\gg b$, $\frac{2b}{c-a+2b}$ is small and we have

$\displaystyle\textsf{Var}_{v^{(t)},p}[s^{(t)}\alpha^{(t)}]\approx\frac{1}{\ell}\
.$

∎

We will use the following in our analysis of the attack on the AMS sketch:

######  Lemma 7.4.

Under the conditions of Lemma 6.2, the following holds:

$\displaystyle\textsf{E}_{\mathcal{A}}\left[\frac{1}{\ell}\|\boldsymbol{u}^{(A)}\|^{2}_{2}\right]$
$\displaystyle\geq
r\sigma^{2}\left(1-O(\frac{1}{\sqrt{\ell}})+\Omega\left(\frac{r}{\ell^{2}}\left(\frac{2}{c-a+2b}\right)^{2}\right)\right)$
(28)

###### Proof.

We now establish Claim (28)

$\displaystyle\textsf{E}_{\mathcal{A}}\left[\frac{1}{\ell}\|\boldsymbol{u}^{(A)}\|^{2}_{2}\right]$
$\displaystyle=\frac{1}{\ell}\sum_{j\in[\ell]}\textsf{E}_{\mathcal{A}}\left[(u^{(A)}_{j})^{2}\right]$
$\displaystyle=\frac{1}{\ell}\sum_{j\in[\ell]}\left(\textsf{Var}_{\mathcal{A}}\left[u^{(A)}_{j}\right]+\textsf{E}_{\mathcal{A}}\left[u^{(A)}_{j}\right]^{2}\right)$
$\displaystyle=\frac{1}{\ell}\sum_{j\in[\ell]}\textsf{Var}_{\mathcal{A}}\left[u^{(A)}_{j}\right]+\frac{1}{\ell}\sum_{j\in[\ell]}\textsf{E}_{\mathcal{A}}\left[u^{(A)}_{j}\right]^{2}\
.$ (29)

We apply Claim (14) to bound the second term:

$\displaystyle\frac{1}{\ell}\sum_{j\in[\ell]}\textsf{E}_{\mathcal{A}}\left[u^{(A)}_{j}\right]^{2}$
$\displaystyle\geq\textsf{E}_{\mathcal{A}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}u^{(A)}_{j}\right]$
applying the inequality $E[X^{2}]\geq E[X]^{2}$
$\displaystyle=\textsf{E}_{\mathcal{A}}[\overline{u^{(A)}}]^{2}\approx\left(\frac{r}{\ell}\sigma^{2}\cdot\frac{2}{c-a+2b}\right)^{2}$
Claim (14) (30)

We now bound from below

$\displaystyle\sum_{j\in[\ell]}\textsf{Var}_{\mathcal{A}}\left[u^{(A)}_{j}\right]$
$\displaystyle=\sum_{j\in[\ell]}\textsf{Var}_{\mathcal{A}}\left[\sum_{t\in[r]}s^{(t)}u^{*(t)}_{j}\right]\geq
r\cdot\ell\cdot\sigma^{2}\left(1-O(\frac{1}{\sqrt{\ell}})\right)\ .$ (31)

We recall that $u^{(t)}_{j}$ are i.i.d. $\mathcal{N}(0,\sigma)$. We consider a
bound where $s^{(t)}\in\\{\pm 1\\}$ is selected in a worst case way (as to
minimize variance) according to the actual
$\boldsymbol{u}^{*(t)}\sim\mathcal{N}_{\ell}(0,\sigma)$. With $\ell=1$ the
variance is minimized when the correlation are maximized which is done by
having $s^{(t)}u^{*{t)}}$ all with the same sign, that is, behaving like
i.i.d. $|\mathcal{N}(0,\sigma)|$ that have variance $(1-2/\pi)\sigma^{2}$ per
term with respective variance $r(1-2/\pi)\sigma^{2}$ for the sum. Since the
same $s^{(t)}$ multiplies all entries in $\boldsymbol{u}^{*(t)}$, we can in
expectation have at most $1/2+\sqrt{\frac{2}{\pi\ell}}$ of these values with
the same sign. Over the total of $r\cdot\ell$ terms we get expected
contribution of at least
$2\sqrt{\frac{2}{\pi\ell}}\cdot(1-2/\pi)\sigma^{2}+(1-2\sqrt{\frac{2}{\pi\ell}})\cdot\sigma^{2}$.

Finally, we substitute (30) and (31) in (29) and obtain the claim

$\displaystyle\frac{1}{\ell}\sum_{j\in[\ell]}\textsf{E}_{\mathcal{A}}\left[u^{(A)}_{j}\right]^{2}$
$\displaystyle\geq
r\cdot\sigma^{2}\left(1-O(\frac{1}{\sqrt{\ell}})\right)+\left(\frac{r}{\ell}\sigma^{2}\cdot\frac{2}{c-a+2b}\right)^{2}$
$\displaystyle=r\sigma^{2}\left(1-O(\frac{1}{\sqrt{\ell}})+\frac{r}{\ell^{2}}(\frac{2}{c-a+2b})^{2}\right)$

∎

##  8 Extension: Universal Attack on the AMS Sketch

Input: $\tau$, $\epsilon$, $\delta$

// Estimator parameters (Definition 8.3)

Initialized AMS $\text{{Sketch}}_{\rho}$ with parameters $(n,\ell)$, number of
queries $r$, tail support size $m$

$\sigma\leftarrow\tau\sqrt{1/2}$; $c\leftarrow\sqrt{1+2\epsilon}$;
$a\leftarrow 1$;
$b\leftarrow\Theta(\frac{1}{\sqrt{\ell}}\ln(\sqrt{\frac{\ell}{\epsilon}})$

$(h,(\boldsymbol{z}^{(t)})_{t\in[r]})\leftarrow$ AttackTails$(n,m,r)$

// Choose tails (Algorithm 1)

$(\boldsymbol{z}^{(t)}\leftarrow\boldsymbol{z}^{(t)}\cdot\frac{\sigma}{\sqrt{m}})_{t\in[r]}$

// Rescale tails to have $\ell_{2}$ norm $\sigma$

for  _$t\in[r]$_ do // Generate Query Vectors

$v^{(t)}_{h}\sim\mathcal{U}[a\cdot\sigma,(c+2b)\cdot\sigma]$

$\boldsymbol{v}^{(t)}\leftarrow
v^{(t)}_{h}\boldsymbol{e}_{h}+\boldsymbol{z}^{(t)}$

// Query vectors

for  _$t\in[r]$_ do // Apply Query Response

Choose an $(\epsilon,\delta,\tau)$-correct estimator $M^{(t)}$

// Definition 8.3, may depend on
$(v^{(t^{\prime})}_{h},s^{(t^{\prime})},M^{(t^{\prime})})_{t^{\prime}<t}$ and
$\rho$

$s^{(t)}\leftarrow M^{(t)}(\text{{Sketch}}_{\rho}(\boldsymbol{v}^{(t)})$

// Apply estimator to sketch

return
_$\boldsymbol{z}^{(A)}\leftarrow\sum_{t\in[r]}s^{(t)}\boldsymbol{z}^{(t)}$_

// Adversarial input

Algorithm 4 Universal Attack on AMS norm estimation

The AMS sketch [4] and the related Johnson Lindenstrauss transform [27] are
linear maps of input vectors $\boldsymbol{v}\in\mathbb{R}^{n}$ to their
sketches in $\mathbb{R}^{\ell}$. The sketches support recovery of $\ell_{2}$
norms and distances. In this section we describe an attack on the AMS sketch
that applies with any correct norm estimator.

The sketch is specified by parameters $(n,\ell)$, where $n$ is the dimension
of input vectors and $\ell$ is the number of measurements. The internal
randomness $\rho$ specifies a set of random hash functions
$s_{j}:[n]\rightarrow\\{-1,1\\}$ ($j\in[\ell]$) so that
$\textsf{Pr}[s_{j}(i)=1]=1/2$. These hash functions define $\ell$ measurement
vectors $\boldsymbol{\mu}^{(j)}$ ($j\in[\ell]$):

$\mu^{(j)}_{i}:=s_{j}(i).$

The AMS sketch analysis holds with 4-wise independent functions but our attack
analysis holds with full randomness.

Norm estimators $M$ applied to the sketch guarantee that when
$\ell=O(\epsilon^{-2}\log(1/\delta))$

$\textsf{Pr}_{\rho}[|\|\boldsymbol{v}\|_{2}^{2}-M(\text{{Sketch}}_{\rho}(\boldsymbol{v}))^{2}|\geq\epsilon\|\boldsymbol{v}\|_{2}^{2}]<\delta\
.$

In particular, for any $\boldsymbol{v}\in R^{n}$ and $j\in[\ell]$ it holds
that,
$\textsf{E}_{\rho}[\langle\boldsymbol{\mu},\boldsymbol{v}\rangle^{2}]=\|\boldsymbol{v}\|^{2}_{2}$
and
$\textsf{Var}_{\rho}[\langle\boldsymbol{\mu},\boldsymbol{v}\rangle^{2}]=O(\|\boldsymbol{v}\|^{2}_{2})$.

######  Definition 8.1 (Adversarial input for AMS).

We say that an attack $\mathcal{A}$ that is applied to a sketch with
randomness $\rho$ and outputs $\boldsymbol{z}^{(A)}\in\\{-1,0,1\\}^{n}$ is
$(\xi,\beta)$-adversarial (for $\xi>0$) if with probability at least $1-\beta$
over the randomness of $\rho,\mathcal{A}$ it holds that:

$\textsf{Pr}_{\rho,\mathcal{A}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{\mu}^{(j)},\boldsymbol{z}^{(A)}\rangle^{2}\geq(1+\xi)\cdot\|\boldsymbol{z}^{(A)}\|^{2}_{2}\right]\geq
1-\beta\ .$ (32)

Note that when $\ell\gg\frac{1}{\epsilon^{2}}\ln(1/\delta)$, for any
$\boldsymbol{v}$, we have

$\textsf{Pr}_{\rho\sim\mathcal{D}}\left[\frac{1}{\ell}\sum_{j\in[\ell]}\langle\boldsymbol{\mu}^{(j)}(\rho),\boldsymbol{v}\rangle^{2}\geq(1+\epsilon)\cdot\|\boldsymbol{v}\|^{2}_{2}\right]\leq\delta\
.$ (33)

Algorithm 4 describes an attack that constructs an adversarial input for a
sketch with randomness $\rho$. Here we consider both the accuracy $\epsilon$
(relative error) of the estimator, which is at least $\epsilon\geq
1/\sqrt{\ell}$ (otherwise correct estimators do not exist) and the bias $\xi$
in the product of the attack. The bias also must have
$\xi=\Omega(1/\sqrt{\ell})$ (otherwise $\xi$ is within the variability of the
output) and naturally we may want $\xi\geq\epsilon$, that is, bias is larger
than the accuracy of the estimators we attack.

We establish the following (the proof is presented after a brief discussion
that interprets the result):

######  Lemma 8.2.

. For $\epsilon,\xi=\Omega(1/\sqrt{\ell})$, any constant $\beta>0$, and attack
size $r=O(\xi\ell^{2}\epsilon^{2})$, the output of Algorithm 4 is
$(\xi,\beta)$-adversarial.

Intuitively, more accurate estimators (that is, smaller $\epsilon$) leak more
information on the randomness and hence are easier to attack and we expect
attack size to increase with $\epsilon$. A larger bias $\xi$ is harder to
accrue and would require a larger attack and hence attack size also increases
with $\xi$.

Interestingly, for the AMS sketch, the sketch size parameter $\ell$ controls
both robustness and accuracy, where with less accurate responses we can
support more queries. This is in contrast to heavy hitters via CountSketch,
where the parameter $b$ controls the accuracy and we use $\ell$ to control
confidence and robustness. (In principle, a larger $\ell$ in CountSketch can
also be used to increase accuracy but much less effectively for a given sketch
size than increasing $b$). We therefore study the attack size on the AMS
sketch in terms of both $\epsilon$ and $\xi$.

The Lemma implies that to generate an $O(1)$-adversarial input for a sketch of
size $\ell$ when estimators have accuracy $\epsilon=\Theta(1)$ (what we can
get in the non-adaptive setting from a sketch of size
$\ell=O(\log(n/\delta))$) it suffices to use $O(\ell^{2})$ queries. In this
case there is a matching upper bound (up to logarithmic factors) using the
"wrapper" method of [24]. The required attack size when $\xi=O(\epsilon)$ is
$r=O(\ell^{2}\epsilon^{3})$. For the smallest applicable accuracy
$\epsilon=O(1/\sqrt{\ell})$ we obtain that $r=O(\sqrt{\ell})$ queries suffice.
In this case, there is a gap with the best known upper bound which is the
trivial bound $r=\Omega(1)$ of answering a single query with the sketch. This
gap leaves an interesting open question. Our attack has a simple structure
where the only adaptive input is the final adversarial one. We conjecture that
there is more robustness in this case (thus a better upper bound) whereas a
more complex attack with multiple adaptive rounds may yield a tight lower
bound of $r=\tilde{O}(1)$ for the general case.

###  8.1 Proof of Lemma 8.2

The algorithm and analysis of the attack on the AMS sketch are similar, but
simpler, than the attack on CountSketch. We use query vectors of a similar
form with varying $v^{(t)}_{h}$ and fixed tail norm scaled to $\sigma$. The
distribution of the measurements of the tails (multiplied by $\mu^{(j)}_{h}$)
$u^{*(t)}_{j}$ is $m^{-1/2}\mathcal{B}(m,1/2)-m/2$, which approaches
$\mathcal{N}(0,\sigma^{2})$ for "large enough" $m$. These values are i.i.d.
for $j\in\ell$ and $t\in[r]$.

The sketch content that is "visible" to the estimator has respective values
$\boldsymbol{u}^{(t)}:=v_{h}^{(t)}\boldsymbol{1}_{\ell}+\boldsymbol{u}^{*(t)}$
with respective distribution $\mathcal{N}_{\ell}(v_{h}^{(t)},\sigma^{2})$. In
our attack we choose $v^{(t)}_{h}\sim\mathcal{U}[a,c+2b]\cdot\sigma$, where
$a,b,c$ are specified below. We assume that at each step $t\in[r]$, the query
response algorithm chooses an estimator that is correct with respect to
$(\epsilon,\delta)$ and $\tau$. The estimator returns only one bit,
essentially comparing the norm to $\tau$ with accuracy $\epsilon$ and
confidence $1-\delta$:

######  Definition 8.3 (Correct $\ell_{2}$-norm estimator).

A norm estimator is correct for parameters $(\epsilon,\delta)$ and $\tau$ if
$\|\boldsymbol{v}\|^{2}_{2}\geq(1+\epsilon)\tau^{2}$, the output is $1$ with
probability $\geq 1-\delta$ and if $\|\boldsymbol{v}\|^{2}_{2}\leq\tau^{2}$
then the output is $-1$ with probability $\geq 1-\delta$.

######  Lemma 8.4.

A norm estimator applied to sketches of our query inputs is correct for
parameters $(\epsilon,\delta)$ and $\tau$ if and only if its reporting
function (see Definition 6.1) is correct for parameters
$(\delta,a,c,\ell,\sigma)$ with

$\displaystyle a$ $\displaystyle=\sqrt{(\tau/\sigma)^{2}-1}$ $\displaystyle c$
$\displaystyle=\sqrt{(1+\epsilon)(\tau/\sigma)^{2}-1}\ .$

###### Proof.

We have

$\displaystyle\|\boldsymbol{v}^{(t)}\|_{2}\geq\tau$
$\displaystyle\iff\sqrt{(v^{(t)}_{h})^{2}+\sigma^{2}}\geq\tau\implies((v^{(t)}_{h})^{2}\geq\tau^{2}-\sigma^{2}=\sigma^{2}((\tau/\sigma)^{2}-1)$
$\displaystyle\implies|v^{(t)}_{h}|\geq\sigma\sqrt{((\tau/\sigma)^{2}-1)}=a\cdot\sigma\
.$ $\displaystyle\|\boldsymbol{v}^{(t)}\|^{2}_{2}\geq(1+\epsilon)\tau^{2}$
$\displaystyle\iff|v^{(t)}_{h}|\geq c\cdot\sigma\ .$

∎

We analyze Algorithm 4 using a correspondence to Algorithm 3. We set the query
vectors parameters according to the estimator parameters: We choose
$\sigma^{2}=\tau^{2}/2$ and thus

$\displaystyle a$ $\displaystyle=1$ $\displaystyle c$
$\displaystyle=\sqrt{1+2\epsilon}$

Note that $c-a=\Theta(\epsilon)$ for $\epsilon<1$ and
$c-a=1+\Theta(\sqrt{\epsilon})$ for $\epsilon>1$. We choose
$b=\Theta(\frac{1}{\sqrt{\ell}}\ln(\sqrt{\frac{\ell}{\epsilon}})$ which
satisfies the condition in Lemma 6.2. Since
$\epsilon\geq\sqrt{\ln(1/\delta)/\ell}$ (otherwise correct estimators don’t
exist), we have $b=O(\epsilon)$ and thus $c-a+2b=\Theta(\epsilon)$.

The adversarial input has $\|\boldsymbol{z}^{(A)}\|^{2}_{2}=r\cdot\sigma^{2}$
and to assess the bias we need to consider
$\textsf{E}_{\mathcal{A}}\left[\frac{1}{\ell}\|\boldsymbol{u}^{(A)}\|^{2}_{2}\right]$.
From Lemma 6.2 using a direct argument (30) we obtain

$\textsf{E}_{\mathcal{A}}\left[\frac{1}{\ell}\|\boldsymbol{u}^{(A)}\|^{2}_{2}\right]=r\sigma^{2}\frac{r}{\ell^{2}}\Omega\left(\left(\frac{2}{c-a+2b}\right)^{2}\right)=\|\boldsymbol{z}^{(A)}\|^{2}_{2}\frac{r}{\ell^{2}}\Omega(\epsilon^{-2}).$

This establishes the claim of the Lemma for the regime of high bias
$\xi=\Omega(1)$.

In order to derive tighter bounds for the regime $\xi<1$ we use a refined
bound by applying Lemma 7.4:

$\displaystyle\textsf{E}_{\mathcal{A}}\left[\frac{1}{\ell}\|\boldsymbol{u}^{(A)}\|^{2}_{2}\right]$
$\displaystyle=r\sigma^{2}\left(1-O(\frac{1}{\sqrt{\ell}})+\frac{r}{\ell^{2}}\Omega\left(\left(\frac{2}{c-a+2b}\right)^{2}\right)\right)$
$\displaystyle=\|\boldsymbol{z}^{(A)}\|^{2}_{2}\left(1-O(\frac{1}{\sqrt{\ell}})+\frac{r}{\ell^{2}}\Omega(\epsilon^{-2})\right)$

Here for $\xi=\Omega(1/\sqrt{\ell})$, we solve for
$\xi=\Omega(r\epsilon^{-2}/\ell^{2})$ and obtain the bound
$r=O(\xi\ell^{2}\epsilon^{2})$.

The confidence bounds of any fixed $\beta$ follows from the bound on the
expectation using Markov inequality.

## Conclusion

Our results suggest interesting directions for followup work. We suspect that
our attack technique can be generalized so that it applies with any randomized
linear sketch that supports recovery of heavy hitters keys or even other
families of features of the input vectors. Our attack techniques might be
applicable to trained neural networks as blackbox attacks that construct
"random noise" that mimics the presence of a signal. As discussed in the
introduction, such attacks complement [23, 26] that constructed "invisible"
noise that obfuscates the input but not the output.

## References

  * [1] Amirali Aghazadeh, Ryan Spring, Daniel LeJeune, Gautam Dasarathy, Anshumali Shrivastava, and Richard G. Baraniuk.  MISSION: ultra large-scale feature selection using count-sketches.  In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 80–88. PMLR, 2018.
  * [2] Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, and Amir Zandieh.  Oblivious sketching of high-degree polynomial kernels.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. SIAM, 2020.
  * [3] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459–467.
  * [4] 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.
  * [5] Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok.  Synthesizing robust adversarial examples.  In International conference on machine learning, pages 284–293. PMLR, 2018.
  * [6] 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.
  * [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/2111.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):6–13, 2021.
  * [10] Dan Boneh and James Shaw.  Collusion-secure fingerprinting for digital data (extended abstract).  In Don Coppersmith, editor, Advances in Cryptology - CRYPTO ’95, 15th Annual International Cryptology Conference, Santa Barbara, California, USA, August 27-31, 1995, Proceedings, volume 963 of Lecture Notes in Computer Science, pages 452–465. Springer, 1995.
  * [11] Moses Charikar, Kevin Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  In Proceedings of the 29th International Colloquium on Automata, Languages and Programming, ICALP ’02, page 693–703. Springer-Verlag, 2002.
  * [12] Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen.  Compressing neural networks with the hashing trick.  In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, page 2285–2294. JMLR.org, 2015.
  * [13] Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen.  Compressing Convolutional Neural Networks in the Frequency Domain.  In Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, pages 1475–1484. ACM, 2016.
  * [14] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer.  On the robustness of countsketch to adaptive inputs.  In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
  * [15] Edith Cohen, Rasmus Pagh, and David Woodruff.  Wor and $p$’s: Sketches for $\ell_{p}$-sampling without replacement.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21092–21104. Curran Associates, Inc., 2020.
  * [16] 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.
  * [17] David A. Freedman.  A note on screening regression equations.  The American Statistician, 37(2):152–155, 1983.
  * [18] Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Minimum cut in o(m log2 n) time.  In ICALP, volume 168 of LIPIcs, pages 57:1–57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [19] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.
  * [20] Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites.  Adaptive machine unlearning.  In Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
  * [21] 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.
  * [22] 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.
  * [23] 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.
  * [24] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer.  Adversarially robust streaming algorithms via differential privacy.  In Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2020.
  * [25] John P. A. Ioannidis.  Why most published research findings are false.  PLoS Med, (2):8, 2005.
  * [26] Rajesh Jayaram, David P. Woodruff, and Qiuyi Zhang.  Span recovery for deep neural networks with applications to input obfuscation.  In International Conference on Learning Representations, 2020.
  * [27] W. Johnson and J. Lindenstrauss.  Extensions of Lipschitz mappings into a Hilbert space.  Contemporary Math., 26, 1984.
  * [28] Akshay Kamath, Eric Price, and David P. Woodruff.  A Simple Proof of a New Set Disjointness with Applications to Data Streams.  Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, 2021\.
  * [29] Paul M. Lukacs, Kenneth P. Burnham, and David R. Anderson.  Model selection bias and Freedman’s paradox.  Annals of the Institute of Statistical Mathematics, 62(1):117, 2009\.
  * [30] Ilya 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–660, New York, NY, USA, 2008. Association for Computing Machinery.
  * [31] John E. Moody and Christian J. Darken.  Fast learning in networks of locally-tuned processing units.  Neural Comput., 1(2):281–294, 1989.
  * [32] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami.  Practical black-box attacks against machine learning.  In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pages 506–519, 2017.
  * [33] Ninh Pham and Rasmus Pagh.  Fast and scalable polynomial kernels via explicit feature maps.  New York, NY, USA, 2013. Association for Computing Machinery.
  * [34] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora.  FetchSGD: Communication-efficient federated learning with sketching.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8253–8265. PMLR, 13–18 Jul 2020\.
  * [35] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, Alex Strehl, and S. V. N. Vishwanathan.  Hash kernels.  In David van Dyk and Max Welling, editors, Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, volume 5 of Proceedings of Machine Learning Research, pages 496–503, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 16–18 Apr 2009\. PMLR.
  * [36] Yossi Shiloach and Shimon Even.  An on-line edge-deletion problem.  J. ACM, 28(1):1–4, jan 1981.
  * [37] Ryan Spring, Anastasios Kyrillidis, Vijai Mohan, and Anshumali Shrivastava.  Compressing gradient optimizers via count-sketches.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5946–5955. PMLR, 09–15 Jun 2019.
  * [38] Thomas Steinke and Jonathan Ullman.  Interactive fingerprinting codes and the hardness of preventing false discovery.  In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1588–1628, Paris, France, 03–06 Jul 2015. PMLR.
  * [39] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [40] David Wajc.  Rounding Dynamic Matchings against an Adaptive Adversary.  Association for Computing Machinery, New York, NY, USA, 2020.
  * [41] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg.  Feature hashing for large scale multitask learning.  In Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 1113–1120, New York, NY, USA, 2009. Association for Computing Machinery.
  * [42] 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 on Foundations of Computer Science (FOCS), 2021.