White-Box Adversarial Streaming Lower Bounds Beyond Two-Party Communication

Several alternatives to the classical streaming model have recently received significant attention. One such extensively studied model, that is closely related to the white-box streaming model, is the adversarially robust streaming model [6, 5]. In this model, the streaming algorithm must respond to a query after each update (insertion or deletion), and the adversary may select the next update based on the algorithm’s response. For example, to $\alpha$-approximate $F_0$, the algorithm must, after each update, output (with high probability) an $\alpha$-approximation of the number of distinct elements seen so far. The adversary can then use this information to adaptively determine the next update.

Clearly, any algorithm that works in the white-box streaming model also works in the adversarially robust model. The robust model can be viewed as a “black-box” adversarial streaming model, since the adversary does not have access to the algorithm’s internal state, only to the outputs it reveals through queries.

In contrast to our Theorem 1, which shows that for any constant $\alpha \ge 1$, $\mathrm{\Omega }(n)$ memory is required to $\alpha$-approximate $F_p$ in the white-box insertion-only model, [5] design algorithms that use sublinear space for the same task in the adversarially robust insertion-only model. The memory requirements of their algorithms match those of classical randomized algorithms for $F_p$ estimation (up to logarithmic factors). These algorithms work by changing their responses to queries only a small number of times, thereby revealing only a limited amount of their randomness. However, they fail entirely if the adversary is given access to the full internal state of the algorithm.

A major open problem posed by [5] is to determine the space complexity of adversarially robust $F_p$-estimation in the turnstile streaming model. A recent result by [15] makes substantial progress by ruling out linear sketches. Note that since the white-box lower bound in Theorem 1 is proved for insertion-only streams, it also applies to the white-box turnstile model.

The white-box streaming model, introduced by [1], captures a richer class of adversarial scenarios. As discussed above, [1] prove lower bounds for this model that are derived from deterministic two-party communication lower bounds. On the algorithmic side, the significant power granted to adversaries in the white-box model has led most research to focus on settings where adversaries are computationally bounded, often under cryptographic assumptions. Surprisingly, despite the fact that streaming algorithms in the white-box model lack even a secret key, [1, 11] were able to leverage cryptographic tools to design space-efficient algorithms for a range of classical problems, including $L_1$-heavy hitters, turnstile $L_0$ estimation, the rank decision problem, string pattern matching, sparse vector recovery, low-rank matrix and tensor recovery, and low-rank plus sparse matrix recovery.

A very recent work of [14] gives an almost-optimal $\mathrm{\Omega }(\sqrt{n})$ lower bound on the white-box streaming space complexity of the Longest Increasing Subsequence (LIS) problem. Although near-tight deterministic lower bounds for LIS have been known for decades [13, 10], no superlogarithmic randomized streaming lower bound space is currently known.

Like the white-box streaming model, the pan-private streaming model [9, 19], also considers settings where the internal state of the streaming algorithm may be exposed. However, the two models differ in their objectives. The white-box model focuses on ensuring correctness in the face of adaptive adversaries, whereas the pan-private model is concerned with privacy. In the pan-private setting, stream elements typically represent sensitive individual data (e.g., financial or medical records), and the goal is to ensure that even if the internal state of the algorithm is compromised, the privacy of each individual’s data remains protected.

We overview the proof of Theorem 1 in this section. For simplicity sake, we restrict our attention to the case of $p=0$, where the $F_p$ moment is simply the number of distinct elements in the stream and thus, estimating the $F_p$ moment is the same as estimating the number of distinct elements. Essentially the same ideas also extend to other values of $p$, as streams with few distinct elements will have a lot of repetitions and therefore, a very different $F_p$ moment than streams that have a lot of distinct elements.

As is standard, we prove the desired white-box streaming lower bound by proving a corresponding communication lower bound. For our result, we consider a $k$-party communication problem, called the Set Union ($\mathrm{𝖲𝖴}$) problem, where all the parties $i\in [k]$ gets as input a set $x_i$ of size $t$ from a universe of size $n=2kt$. The goal is to distinguish between the (“YES”) case where the sets received by all the parties are the same implying that the size of the union of all the sets is small and the (“NO”) case where the sets received by all the parties are (very) different implying that the size of the union of all the sets is large. As the size of the union is just the number of distinct elements, a lower bound for the Set Union problem also implies a lower bound for the problem of estimating the number of distinct elements.

In terms of parameters, we require that in the NO case, the size of the union of all the sets is at least $t+\left(k-1\right)\cdot t/2$, that is, on average every set other than $x_1$ contributes at least $t/2$ fresh elements to the union. As the size of the union in the YES case is $t$, showing that the YES and the NO cases are indistinguishable rules out the possibility of approximating the distinct elements to within a factor $\mathrm{\Omega }(k)$. As $k$ can be arbitrarily large, we have the desired result. We mention that the approximation factor we obtain for the $k$-party problem is tight up to constant factors. Indeed, it is easy to see that the size of the union lies in the interval $[t,kt]$ implying that a $k$-approximation is trivial. This also establishes that it is impossible to obtain Theorem 1 via two-party techniques (even for $p=0$).

We show that a white-box communication protocol with communication $o(t)$ cannot distinguish between the YES case and the NO case of the Set Union problem. This is tight up to constant factors because of a simple protocol where the first party simply sends $x_1$ and all the other parties check if their sets are the same as $x_1$ or not.

We overview the proof of Theorem 3 in this section, focusing on the case $k=3$, which can be easily generalized to any $k>3$. Fix a 3-party white-box communication protocol $\pi$ that computes a total function $f$. As mentioned in Section 2.1, the first party can easily be derandomized. Let ${\mathrm{𝗌𝗎𝖼𝖼}}_{x_1}(r_1)$ denote the maximum success probability of $\pi$ in computing $f$, given that the first party’s input is $x_1$ and its random string is $r_1$. In our derandomized protocol, like in the derandomized protocol of [1], the first party fixes its random string to the string $r_1$ that maximizes ${\mathrm{𝗌𝗎𝖼𝖼}}_{x_1}(r_1)$.

Crucially, the first party can compute ${\mathrm{𝗌𝗎𝖼𝖼}}_{x_1}(r_1)$ by enumerating all possible white-box adversaries $𝒜$, calculating the success probability of $\pi$ against each $𝒜$ conditioned on $x_1$ and $r_1$, and taking the minimum. To compute the success probability against a fixed $𝒜$, the first party iterates over all random strings for the second and third parties, simulates $\pi$, and compares the output to the correct value of $f$.

Like the first party, to derandomize its strategy, the second party aims to fix its randomness to the string $r_2$ that maximizes ${\mathrm{𝗌𝗎𝖼𝖼}}_{x_1,x_2}(r_2)$, the protocol’s success probability given inputs $x_1$, $x_2$ and the random string $r_2$ for the second party (note that the first party is now deterministic). However, the second party does not know $x_1$; it only observes the message $m_1$ sent by the first party.

The key observation is that if $\pi$ computes a total function, then for every $x_3$, $f(x_1,x_2,x_3)=f(x_1^{\prime },x_2,x_3)$, as long as on input $x_1^{\prime }$ the first party also sends the message $m_1$. Since for a fixed $r_2$, $\pi$ gives the same output on inputs $(x_1,x_2,x_3)$ and $(x_1^{\prime },x_2,x_3)$, and since $f(x_1,x_2,x_3)=f(x_1^{\prime },x_2,x_3)$, we get that the value of ${\mathrm{𝗌𝗎𝖼𝖼}}_{x_1,x_2}(r_2)$ only depends on the message $m_1$, and not on the specific value of $x_1$. Therefore, the second party can compute this value using any input $x_1^{\prime }$ consistent with the received message $m_1$, instead of $x_1$.

We note that this argument does not extend to partial functions, since when computing ${\mathrm{𝗌𝗎𝖼𝖼}}_{x_1,x_2}(r_2)$, the second party must only consider adversaries $𝒜$ that generate inputs satisfying the promise of $f$. For example, suppose the promise of $f$ requires that $x_1=x_3$. If the second party substitutes the actual $x_1$ with some $x_1^{\prime }\ne x_1$ when simulating such an adversary, then the third party receives $x_3=x_1^{\prime }$, which differs from the true input $x_1$ held by the first party. As a result, the generated input tuple is “inconsistent”, as it violates the promise of the function.

We note that in the proof of Theorem 1, we are able to avoid the consistency issue and successfully derandomize party $j=k-i$ by restricting our attention to adversaries that assign the same input to all of the first $j$ parties. As a result, since party $j$ knows its own input, it also knows the inputs of all earlier parties and therefore does not need to generate inputs for them.

Observe that this issue of consistency does not arise in the case of total functions, where all input combinations are valid by definition, so any choice of $x_1^{\prime }$ remains consistent with any $x_3$.

In the case of two-party ($k=2$) partial functions, no consistency issues arise, as there is no third party involved, and therefore no risk of violating the promise. This fact makes the derandomization of [1] work. We note that their derandomization also requires $f$ to be boolean (if not a total function).

Theorem 3 and the derandomization result of [1] leave open the possibility that partial functions or relations, $f(x_1,\mathrm{\dots },x_k)$, that are either boolean with $k\ge 3$ or non-boolean with $k=2$, might have white-box communication protocols that require significantly less memory than deterministic ones. Theorems 5 and 6 show that large separations are possible in both these cases. Note that Theorem 5 implies Theorem 4.

Roughly speaking, the inputs $a,b$ and $c$ to the partial function $f(a,b,c)$ are vectors of length $n$. It is promised that $a_i=b_i$ for at least $10\%$ of the indices $i\in [n]$. Additionally, for every index $i$ where $a_i\ne b_i$, it is promised that $c_i=\perp$. The goal is to distinguish between the following two cases: (i) For all indices $i$ where $a_i=b_i$, we have $c_i=b_i$; or (ii) For all such indices $i$, we have $c_i\ne b_i$.

The following is a white box protocol for $f$: The second party sends to the third party a set of $100$ random pairs $(i,b_i)$ (no message from the first party to the second). The pairs are selected using reservoir sampling, which, upon receiving $b_i$, flips coins to decide whether to add $(i,b_i)$ to the set. Note that had the protocol decided ahead of time on this random set of indices, the white-box adversary could have made sure that $a_i\ne b_i$ for all $i$’s in the set. Next, the third party goes over all indices $i$ in the set, searching for one with $c_i\ne \perp$. Such an index $i$ should exist with high probability, and if $c_i=b_i$, the algorithm identifies case (i); otherwise, if $c_i\ne b_i$, it identifies case (ii).

To complete the proof of Theorem 5, we show an $\mathrm{\Omega }(n)$ lower bound on the memory required by any deterministic algorithm that solves $f$. Observe that our derandomization argument from the proof of Theorem 3 fails when applied to the above white-box protocol for $f$. This is because $c$ determines the set of indices where $a_i=b_i$. Therefore, without knowing this set, the second party cannot generate an input $a^{\prime }$ such that $a^{\prime }$ and $b$ are consistent with the third party’s input $c$.

Roughly speaking, the relation $g(a,b)$ considers input vectors $a$ and $b$ with the same promise as in $f$. The goal is to output a set of $100$ indices such that, for at least one of them, $a_i=b_i$.

A white-box protocol for $g$ simply has the second party output a uniformly random set of $100$ coordinates (note that there is no communication between the parties). An $\mathrm{\Omega }(n)$ deterministic lower bound for $g$ is derived from that of $f$.

For integers $n,k\ge 1$, $[n]$ denotes $\{1,\mathrm{\dots },n\}$, $[k,n]$ denotes $\{k,\mathrm{\dots },n\}$, and $\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)$ represents the collection of all $k$-subsets of $[n]$. Throughout, logarithms are base-$2$.

A total function is a function that is defined for every input in its domain, whereas a partial function may only be defined on a subset of the inputs.

The standard approach of proving streaming lower bounds is via communication complexity. So we define the following (one-way) white-box communication model. Let $\pi$ be a $k$-party protocol and $𝒜$ be an adversary. Initially, $m_0=\perp$. At the $i$-th step, the $i$-th party computes $m_i$ based on $m_{i-1}$, its input $x_i$, and its (private) randomness $r_i$⁸⁸8The definition of the model can be modified to compute $m_i$ based on $m_{i-1},x_i$, and $r_1,\mathrm{\dots },r_i$. This essentially corresponds to free access to a random oracle for streaming algorithms. Our lower bounds in this paper hold even against this strongest form of randomness. In particular, in the hybrid argument for proving Lemma 11, we partially derandomize a prefix of parties. This is essentially the same as revealing their randomness to all later parties., where $x_i\in X_i$ is picked by the adversary (possibly randomly) based on $m_1,\mathrm{\dots },m_{i-1},x_1,\mathrm{\dots },x_{i-1},r_1,\mathrm{\dots },r_{i-1}$. At the end, the $k$-th party outputs $m_k$.

Let $f:X_1\times \mathrm{\cdots }\times X_k\to 2^Y$ be a relation. The success probability of $\pi$ in solving $f$ against $𝒜$ is defined to be $\mathrm{Pr}(m_k\in f(x_1,\mathrm{\dots },x_k))$, where the probability is over both $r_i$ and the randomness of $𝒜$, and $x_1,\mathrm{\dots },x_k$ are the input generated by $𝒜$ on those randomness. Also define the communication complexity of $\pi$ to be the maximum length of $m_i$ over all $i\in [k]$ and all possible inputs $x_1,\mathrm{\dots },x_k$. Note that the communication complexity is defined to be the maximum per-party communication due to the following connection between streaming and communication.

We remark that ${\mathrm{𝖲𝖴}}_{k,n,t,w}$ is similar to the communication problem used by [7], but our proof approach is quite different and tailored to white-box communication. To see the connection between ${\mathrm{𝖲𝖴}}_{k,n,t,w}$ and $\alpha$-approximate $F_p$ moment estimation, we have the following reductions.

This section constitutes a proof of Lemma 11. We first define the following sets of adversaries ${𝐀}_i$. For $i\in [k]$, an adversary is in ${𝐀}_i$ if for any protocol, the generated input satisfies all requirements below.

1. 1.

   $x_1=\mathrm{\cdots }=x_{k-i+1}$.

2. 2.

   $|{\bigcup }_{i^{\prime }=1}^k{x}_{i^{\prime }}|=|{\bigcup }_{i^{\prime }=k-i+1}^k{x}_{i^{\prime }}|\ge t+(i-1)tw$.

3. 3.

   $x_1$ is uniformly random over $\left(\genfrac{}{}{0pt}{}{[n]}{t}\right)$.

Intuitively, adversaries in ${𝐀}_i$ generate input such that the first $k-i+1$ parties get a (partial) YES case while the last $i$ parties get a (partial) NO case. We say the input is of type $i$ if the first two requirements above are satisfied.

For protocol $\pi$ and adversary $𝒜$, let $q(\pi ,𝒜)$ denote the probability of $\pi$ outputting YES against $𝒜$ (over the randomness of both $\pi$ and $𝒜$)¹⁰¹⁰10Although ${\mathrm{𝖲𝖴}}_{k,n,t,w}$ is a promise problem, any protocol for it can be arbitrarily extended to also output YES/NO on input not in YES/NO cases.. Also let $q_i(\pi )={\max }_{𝒜\in {𝐀}_i}q(\pi ,𝒜)$ for $i\in [k]$. Fix a protocol ${\pi }^{\ast }$ with communication $C$ and probability $\delta >1/2$. For any adversary $𝒜\in {𝐀}_1$, it only generates type-$1$ inputs, which are always in the YES case by Definition 8, so $q({\pi }^{\ast },𝒜)\ge \delta$. This further implies $q_1({\pi }^{\ast })\ge \delta$. Similarly, we have $q_k({\pi }^{\ast })\le 1-\delta$. Consider the maximization $Q={\max }_{\pi }(q_1(\pi )-q_k(\pi ))$ over all protocols $\pi$ with (per-party) communication at most $C$. Altogether, this means $Q\ge q_1({\pi }^{\ast })-q_k({\pi }^{\ast })\ge 2\delta -1=\mathrm{\Omega }(1)$.

On the other hand, however, we show that $Q=o(1)$ if $C=o(t(1-w)-O(\log n))$. This is a contradiction, hence proving Lemma 11. To this end, it is sufficient to show that $Q_i={\max }_{\pi }(q_i(\pi )-q_{i+1}(\pi ))=o(1/k)$ for all $i\in [k-1]$, where the maximization is over all protocols $\pi$ with communication at most $C$.

Fix $i$ from now on. Let $j=k-i$. Let ${\pi }_i^{\prime }$ be a protocol with communication at most $C$ such that $Q_i=q_i({\pi }_i^{\prime })-q_{i+1}({\pi }_i^{\prime })$. Observe that $q_i(\cdot )$ and $q_{i+1}(\cdot )$ only involve adversaries in ${𝒜}_i$ and ${𝒜}_{i+1}$, who only generate type-$i$ and type-$(i+1)$ inputs. Therefore, each of the first $j$ parties of ${\pi }_i^{\prime }$ knows that $x_1=\mathrm{\dots }=x_j$. In this case, the $j$-th party can simulate the first $j$ parties and compute by itself the same message it would have in ${\pi }_i^{\prime }$.

Let ${\pi }_i^{\prime \prime }$ be the protocol obtained from ${\pi }_i^{\prime }$ by replacing the messages of the first $j-1$ parties by the empty message and having the $j$-th party simulate the first $j$ parties to compute $m_j$. So we have $q_i({\pi }_i^{\prime \prime })-q_{i+1}({\pi }_i^{\prime \prime })=q_i({\pi }_i^{\prime })-q_{i+1}({\pi }_i^{\prime })$. Now, for any possible randomness $r_j$ for the $j$-th party, let ${\pi }_{i,r_j}^{\prime \prime }$ be the protocol obtained from ${\pi }_i^{\prime \prime }$ by fixing the randomness of the $j$-th party to $r_j$. We select ${\pi }_i$ to be ${\pi }_{i,r_j}^{\prime \prime }$ for the $r_j$ that maximizes $q_i({\pi }_{i,r_j}^{\prime \prime })-q_{i+1}({\pi }_{i,r_j}^{\prime \prime })$. We next show that $q_i({\pi }_i)-q_{i+1}({\pi }_i)\ge q_i({\pi }_i^{\prime \prime })-q_{i+1}({\pi }_i^{\prime \prime })=q_i({\pi }_i^{\prime })-q_{i+1}({\pi }_i^{\prime })=Q_i$. As shown above, since we are considering only $q_i(\cdot )$ and $q_{i+1}(\cdot )$, we always that $x_1=\mathrm{\dots }=x_j$, and thus it suffices for the adversary to only select inputs for parties $[j,k]$. Indeed, we have

So we get that $q_i({\pi }_i)-q_{i+1}({\pi }_i)\ge q_i({\pi }_i^{\prime \prime })-q_{i+1}({\pi }_i^{\prime \prime })$, as claimed.

Let ${𝒜}_i$ be an adversary in ${𝐀}_i$ such that $q_i({\pi }_i)=q({\pi }_i,{𝒜}_i)$. It suffices to construct another adversary ${𝒜}^{\prime }\in {𝐀}_{i+1}$ such that $q({\pi }_i,{𝒜}^{\prime })\ge q({\pi }_i,{𝒜}_i)-o(1/k)$. Let $M_j:x_j\mapsto m_j$ be the function computed by the $j$-th party in ${\pi }_i$¹¹¹¹11$M_j$ depends solely on $x_j$, but not $m_{j-1},r_j$, because the first $j-1$ parties do no computation and the $j$-th party is deterministic.. Consider the adversary ${𝒜}^{\prime }={𝒜}^{\prime }({\pi }_i)$, who generates input $x_1^{\prime },\mathrm{\dots },x_k^{\prime }$ as follows:

1. 1.

   Let $x_1=\mathrm{\cdots }=x_j$ be generated by ${𝒜}_i$. Sample $x_j^{\prime }$ uniformly at random from $Z_j(x_j)=\{x_j^{\prime }\mid M_j(x_j^{\prime })=M_j(x_j)\}$. For the first $j$ parties, generate $x_1^{\prime }=\mathrm{\cdots }=x_j^{\prime }$.

2. 2.

   For $\mathrm{\ell }\in [j+1,k]$, let $x_{\mathrm{\ell }}$ be generated by ${𝒜}_i$, who pretends that for $i^{\prime }\in [\mathrm{\ell }-1]$, the $i^{\prime }$-th party gets $x_{i^{\prime }}$ as input¹²¹²12In particular, this means $x_{j+1}=x_j=\mathrm{\cdots }=x_1$.. If $|({\bigcup }_{i^{\prime }=j}^{\mathrm{\ell }-1}{x}_{i^{\prime }}^{\prime })\cup x_{\mathrm{\ell }}|+(k-\mathrm{\ell })t\ge t+itw$, then generate $x_{\mathrm{\ell }}^{\prime }=x_{\mathrm{\ell }}$ for the $\mathrm{\ell }$-th party. Otherwise, for all parties $i^{\prime }\in [\mathrm{\ell },k]$, generate $x_{i^{\prime }}^{\prime }$ that is disjoint from $x_1^{\prime },\mathrm{\dots },x_{i^{\prime }-1}^{\prime }$.

We first claim ${𝒜}^{\prime }\in {𝐀}_{i+1}$. The first requirement is satisfied because $x_1^{\prime }=\mathrm{\cdots }=x_j^{\prime }$ and $j=k-(i+1)+1$. For the second requirement, let ${\mathrm{\ell }}^{\ast }\in [j,k]$ be the largest index such that $|({\bigcup }_{i^{\prime }=j}^{{\mathrm{\ell }}^{\ast }-1}{x}_{i^{\prime }}^{\prime })\cup x_{{\mathrm{\ell }}^{\ast }}|+(k-{\mathrm{\ell }}^{\ast })t\ge t+itw$ during the execution¹³¹³13This is well defined because the inequality is always satisfied by index $j$.. By Item 2 of Remark 12, we have

So ${𝒜}^{\prime }$ always generates type-$(i+1)$ input. Regarding the third requirement, as $x_1$ is uniformly random over $\left(\genfrac{}{}{0pt}{}{[n]}{t}\right)$ due to ${𝒜}_i\in {𝐀}_i$, the probability of ${𝒜}^{\prime }$ generating any $x_1^{\prime }$ is

Therefore, ${𝒜}^{\prime }\in {𝐀}_{i+1}$.

Finally, we conclude the proof of Lemma 11 by showing $q({\pi }_i,{𝒜}^{\prime })\ge q({\pi }_i,{𝒜}_i)-o(1/k)$. Observe that by Item 1 of Remark 12, the resampling of ${𝒜}^{\prime }$ ensures that $m_j$ remains the same. As a result, if this were the only deviation from ${𝒜}_i$, i.e., $x_{\mathrm{\ell }}^{\prime }=x_{\mathrm{\ell }}$ for all $\mathrm{\ell }\in [j+1,k]$, the joint distribution of $x_{\mathrm{\ell }},r_{\mathrm{\ell }},m_{\mathrm{\ell }}$ for $\mathrm{\ell }\in [j+1,k]$ was exactly the same as if ${\pi }_i$ were executed against ${𝒜}_i$. In particular, this means that the probability of outputting YES would be $q({\pi }_i,{𝒜}_i)$. In the actual execution of ${\pi }_i$ against ${𝒜}^{\prime }$, this probability is lowered only in the case for some $\mathrm{\ell }\in [j+1,k]$, which also implies . Note that $|{\bigcup }_{i^{\prime }=j+1}^k{x}_{i^{\prime }}|=|{\bigcup }_{i^{\prime }=k-i+1}^k{x}_{i^{\prime }}|\ge t+(i-1)tw$ as ${𝒜}_i\in {𝐀}_i$ always generates type-$i$ input. Combining the two inequalities, we get , where $X^{\prime }={\bigcup }_{i^{\prime }=j+1}^k{x}_{i^{\prime }}$. Let $Z_j[m_j]=\{x_j\mid M_j(x_j)=m_j\}$. Altogether, we have