# Fast White-Box Adversarial Streaming Without a Random Oracle

Ying Feng Carnegie Mellon University. E-mail<EMAIL_ADDRESS>Aayush
Jain Carnegie Mellon University. E-mail<EMAIL_ADDRESS>David P.
Woodruff Carnegie Mellon University. E-mail<EMAIL_ADDRESS>
###### Abstract

Recently, the question of adversarially robust streaming, where the stream is
allowed to depend on the randomness of the streaming algorithm, has gained a
lot of attention. In this work, we consider a strong white-box adversarial
model (Ajtai et al. PODS 2022), in which the adversary has access to all past
random coins and the parameters used by the streaming algorithm. We focus on
the sparse recovery problem and extend our result to other tasks such as
distinct element estimation and low-rank approximation of matrices and
tensors. The main drawback of previous work is that it requires a random
oracle, which is especially problematic in the streaming model since the
amount of randomness is counted in the space complexity of a streaming
algorithm. Also, the previous work suffers from large update time. We
construct a near-optimal solution for the sparse recovery problem in white-box
adversarial streams, based on the subexponentially secure Learning with Errors
assumption. Importantly, our solution does not require a random oracle and has
a polylogarithmic per item processing time. We also give results in a related
white-box adversarially robust distributed model. Our constructions are based
on homomorphic encryption schemes satisfying very mild structural properties
that are currently satisfied by most known schemes.

##  1 Introduction

The streaming model of computation has emerged as an increasingly popular
paradigm for the analysis of massive datasets, where the overwhelming size of
the data places restrictions on the memory, computation time, and other
resources available to the algorithm. In the streaming model, the input data
is implicitly defined through a stream of data elements that sequentially
arrive one-by-one. One can also delete a previous occurrence of an item. An
algorithm makes one pass over the stream and uses limited space to approximate
a desired function of the input. In the formalization of Alon, Matias, and
Szegedy [AMS96], the data is represented as an underlying $n$-dimensional
vector that is initialized to $0^{n}$, and then undergoes a sequence of
additive updates to its coordinates. The algorithm aims to optimize the space
and time to process these updates, while being able to respond to queries
about this underlying vector.

This model captures key resource requirements of algorithms for many practical
settings such as Internet routers and traffic logs [LSO+06, ZKWX05, SKL+06,
VSGB05, CM05, CG08], databases [SAC+79, DJMS02, FN85, Lig18, SDNR96, BHM+05],
sensor networks [HQWW22, Gab07], financial transaction data [ABS23], and
scientific data streams [CCD+03, SGV02]. See [Mut05] for an overview of
streaming algorithms and their applications.

A large body of work on streaming algorithms has been designed for oblivious
streams, for which the sequence of updates may be chosen adversarially, but it
is chosen independently of the randomness of the streaming algorithm.
Recently, there is a growing body of work on robust streaming algorithms in
the black-box adversarial model [BY20, BJWY21, HKM+20, WZ21, ABD+21, KMNS21,
BHM+21, MN21, ACSS21, BEO22, CGS22], in which the adversary can monitor the
outputs of the streaming algorithm and choose future stream updates based on
these outputs. While useful in a number of applications, there are other
settings where the adversary may also have access to the internal state of the
algorithm, and this necessitates looking at a stronger adversarial model known
as the white-box adversarial streaming model.

###  1.1 White-box Adversarial Streaming Model

We consider the white-box adversarial streaming model introduced in [ABJ+22],
where a sequence of stream updates is chosen adaptively by an adversary who
sees the full internal state of the algorithm at all times, including the
parameters and the previous randomness used by the algorithm. The interaction
between an adversary and the streaming algorithm is informally depicted as the
following game.

  * Consider a multi-round, two-player game between $\mathsf{StreamAlg}$, the streaming algorithm, and an adversary $\mathcal{A}$. Prior to the beginning of the game, fix a query function $f$, which asks for a function of an underlying dataset that will be implicitly defined by the stream. In each round:

    1. 1.

$\mathcal{A}$ computes an update $x$ for the stream, which depends on all
previous stream updates, all previous internal states, and the randomness used
by $\mathsf{StreamAlg}$.

    2. 2.

$\mathsf{StreamAlg}$ acquires a fresh batch of random bits, uses $x$ to update
its data structures, and (if asked) outputs a response to the query function
$f$.

    3. 3.

$\mathcal{A}$ observes the random bits, the internal state of
$\mathsf{StreamAlg}$, and the response.

The goal of $\mathcal{A}$ is to make $\mathsf{StreamAlg}$ output an incorrect
query at some round during the game.

The white-box adversarial model captures characteristics of many real-world
attacks, where an adaptive adversary has access to the entirety of the
internal states of the system. In comparison to the oblivious stream model or
the black-box adversarial model [BJWY21], this model allows for richer
adversarial scenarios.

For example, consider a distributed setting where a centralized server
collects statistics of a database generated by remote users. The server may
send components of its internal state $S$ to the remote users in order to
optimize the total communication over the network. The remote users may use
$S$ in some process that generates downstream data. Thus, future inputs depend
on the internal state $S$ of the algorithm run by the central coordinator. In
such settings, the white-box robustness of the algorithms is crucial for
optimal selection of query plans [SAC+79], online analytical processing
[SDNR96], data integration [BHM+05], and data warehousing [DJMS02].

Many persistent data structures provide the ability to quickly access previous
versions of information stored in a repository shared across multiple
collaborators. The internal persistent data structures used to provide version
control may be accessible and thus visible to all users of the repository.
These users may then update the persistent data structure in a manner that is
not independent of previous states [DSST89, FK03, Kap04].

Dynamic algorithms often consider an adaptive adversary who generates the
updates upon seeing the entire data structure maintained by the algorithm
during the execution [Cha10, CH21, RSW22]. For example, [Waj20] assumes the
entire state of the algorithm (including the set of randomness) is available
to the adversary after each update, i.e., a white-box model.

Moreover, robust algorithms and adversarial attacks are important topics in
machine learning [SZS+14, GSS14], with a large body of recent literature
focusing on adversarial robustness of machine learning models against white-
box attacks [IEM18, MMS+18, SST+18, TKP+18, CZM+18, KGB17, LCLS17].

###  1.2 Prior Work in the White-Box Model

We aim to design white-box adversarially robust (WAR) streaming algorithms
with provable correctness guarantees against such powerful adversaries. In
general, it is difficult to design non-trivial WAR algorithms, due to the fact
that many widely used space-saving techniques are subject to attacks when all
parameters and generated randomness of the system are immediately revealed to
the adversary. In the streaming community, both [ABJ+22] and [FW23] explicitly
study the white-box model for data streams and suggest the use of cryptography
in designing WAR algorithms (see also [BJWY21] for the use of cryptography for
black box robustness). A similar model to the white-box model has also been
independently developed in the cryptography community in the study of property
preserving hashing [BLV19].

In this work, the central problem we consider is $k$-sparse recovery as
follows:

Sparse Recovery: given an input vector $\bm{x}$, if $\bm{x}$ contains at most
$k$ non-zero entries, recover $\bm{x}$. Otherwise, report _invalid input_.

A primitive for sparse recovery in the white-box model can be used for tasks
such as distinct element estimation, low rank approximation of matrices and
tensors, and finding a maximum matching [ABJ+22, FW23]. Sparse recovery is
also itself a critical data acquisition and processing problem that arises in
signal and image processing, machine learning, data networking, and medicine,
see [ABJ+22, FW23] and the references therein.

We note that a weaker definition of sparse recovery assumes that the input
vector $\bm{x}$ is promised to be $k$-sparse, and only under this promise
recovers $\bm{x}$. If the input is not $k$-sparse, the algorithm can output
any vector. This problem can in fact be solved deterministically (and thus
also in the white-box model) with low memory (see, e.g., [BIR08], for a
version with fast update time, though other simpler schemes based on MDS codes
exist). The drawback under this weaker definition though is that, without
knowing the sparsity of the input ahead of time, a user of the algorithm
cannot tell whether the output is a correct recovery or garbage. In the latter
case, the client might ignorantly use the garbage output in subsequent
applications and propagate such an error.

[FW23] solves this problem based on the assumed hardness of the Short-Integer-
Solution (SIS) problem, which is a problem that is studied in lattice-based
cryptography. The robust version of the property preserving hashing [BLV19]
can also be applied to solve the same problem. However, a notable drawback of
all prior solutions proposed is their reliance on either a random oracle or a
prohibitively long random string. This is because a key component of these
algorithms is a giant, random matrix $\mathbf{A}$ for which it is hard to find
a vector $\bm{x}$ with small entries for which $\mathbf{A}\bm{x}$ is sparse.
Long random strings are especially problematic in data streams, where the
resource measure is the total space complexity, including the randomness, and
there is a large body of work on derandomizing such algorithms, see, e.g.,
[Nis92, Ind06, KNW10, KPTW23]. Since it was previously unknown how to generate
$\mathbf{A}$ pseudorandomly while maintaining this hardness property, previous
work [FW23] relies on a random oracle to heuristically compress such a matrix
$\mathbf{A}$. This assumes that the algorithm is given read access to a long
string of random bits, which is often implemented with hash-based heuristic
functions such as AES or SHA256. Unfortunately, this heuristic cannot be
proven secure using a standard reduction-style security proof. This motivates
a central question of this work: Do there exist efficient streaming algorithms
in the white-box model without a random oracle?

###  1.3 Our Results

Our algorithms make use of the hardness assumptions of the Learning with Error
(LWE) problem and its variant, Ring LWE. Both problems are popular in
cryptography known for building homomorphic encryption schemes. In this
section, we state the efficiency of our algorithms under the sub-exponential
hardness assumptions of these problems. However, we stress that in contrast to
[FW23], our algorithms are robust even under weaker polynomial hardness
assumptions. We let $n$ be the dimension of the underlying input vector, and
for notational convenience, we assume that the entries of the vector are
integers bounded in absolute value by $\operatorname{\mathsf{poly}}(n)$ at all
times during the stream. We use $\widetilde{\mathcal{O}}(f)$ to denote
$f\cdot\operatorname{\mathsf{poly}}(\log n)$.

Our main result is informally stated as follows:

######  Theorem 1.1 (Informal).

Assuming the sub-exponential hardness111Sub-exponential hardness means that we
assume that for adversaries of size $2^{\lambda^{\beta}}$, where $\lambda$ is
the security parameter and $\beta>0$ is some constant, a sample from an LWE
distribution is indistinguishable from a uniformly random sample.  of the
Learning with Errors (LWE) problem, there is a WAR streaming algorithm for
$k$-sparse recovery, which:

  * ·

takes $\widetilde{\mathcal{O}}(k)$ bits of space,

  * ·

has $\widetilde{\mathcal{O}}(1)$ update time, and

  * ·

has $\widetilde{\mathcal{O}}(k^{1+c})$ report time for an arbitrarily small
constant $c>0$.

This matches (up to a poly-logarithmic factor) the optimal space and update
time complexity for the weaker $k$-sparse recovery problem under the easier
oblivious streaming setting. On the other hand, assuming polynomial security
of the LWE problem, there is a multiplicative overhead of $n^{\epsilon}$ for
arbitrary constant $\epsilon>0$ on our space and time complexities.

#### Adversarial Model in the Distributed Setting.

We introduce and formalize the white-box adversarial model for distributed
data processing as a means of modeling the existence of one or more malicious
parties in a distributed system. We also study the sparse recovery problem in
a white-box distributed model. A WAR streaming algorithm can be naively
converted to a WAR distributed algorithm under certain conditions, yet the
resulting processing time of the servers is ${\mathcal{O}}(n)$ times that of
the streaming update time. In contrast to this suboptimal time implied by the
naive conversion, we show that we can achieve a near-optimal processing time
in a white-box distributed model assuming the polynomial hardness of Ring-LWE,
which is a variant of the LWE problem defined over a polynomial ring. This is
because Ring-LWE supports SIMD (Single-Instruction Multiple-Data) style
operations that have been exploited in the design of efficient homomorphic
encryption schemes in cryptography. We informally state our result as follows:

######  Theorem 1.2 (Informal).

Assuming the hardness of Ring-LWE, there exists a WAR distributed protocol for
$k$-sparse recovery, which:

  * ·

uses $\widetilde{\mathcal{O}}(k)$ bits of communication between each server
and the coordinator,

  * ·

has $\widetilde{\mathcal{O}}(n)$ processing time on each server, and

  * ·

the coordinator spends $\widetilde{\mathcal{O}}(\max(n,k^{1+c}))$ time to
output the solution given the messages from the servers, for an arbitrarily
small constant $c>0$.

We summarize the complexities of our sparse recovery algorithms in Table 1, as
compared to the best-known upper bounds for these problems in the white-box
adversarial model.

Table 1: A summary of the bit complexities and runtime of our $k$-sparse recovery algorithm, as compared to the best-known upper bounds for these problems in the white-box adversarial model [FW23]. The SIS assumption used in the previous work is proven to be equivalently hard to the LWE assumption we use, up to different parameters. The TIME columns refer to the update time in the streaming model and processing time in the distributed model. $c$ denotes an arbitrarily small positive constant. | Model | Assumption | Space | Time | Rand. Oracle?
---|---|---|---|---|---
Prev. | Streaming | subexp SIS | $\widetilde{\mathcal{O}}(k)$ | $\widetilde{\mathcal{O}}(k)$ | $\checkmark$
Distributed | subexp SIS | $\widetilde{\mathcal{O}}(k)$ | $\widetilde{\mathcal{O}}(nk)$ | $\checkmark$
Ours | Streaming | subexp LWE | $\widetilde{\mathcal{O}}(k)$ | $\widetilde{\mathcal{O}}(1)$ |
Streaming | poly LWE | $\widetilde{\mathcal{O}}(n^{c}+k)$ | $\widetilde{\mathcal{O}}(n^{c})$ |
Distributed | subexp LWE | $\widetilde{\mathcal{O}}(k)$ | $\widetilde{\mathcal{O}}(n)$ |
Distributed | poly LWE | $\widetilde{\mathcal{O}}(n^{c}+k)$ | $\widetilde{\mathcal{O}}(n^{1+c})$ |
Distributed | poly Ring-LWE | $\widetilde{\mathcal{O}}(n^{c}+k)$ | $\widetilde{\mathcal{O}}(n)$ |

#### Extensions to matrix and tensor recoveries.

Similar to [FW23], generalizing our construction produces low-rank matrix and
tensor recovery algorithms, again with the crucial property that they do not
assume a random oracle or store a large random seed.

Consider a data stream updating the entries of an underlying matrix or tensor,
which can be represented as its vectorization in a stream. Let $n\geq m$ be
the dimensions of an underlying input matrix, and let $n$ be the dimension
parameter of an underlying data tensor in $\mathbb{R}^{n^{d}}$ for some
$d\in{\mathcal{O}}(1)$ (we assume all dimensions of the tensor are the same
only for ease of notation). We have the following results in the streaming
model:

######  Theorem 1.3 (Informal).

Assuming the sub-exponential hardness of the Learning with Errors (LWE)
problem, there is a WAR streaming algorithm for rank-$k$ matrix recovery,
which takes $\widetilde{\mathcal{O}}(nk)$ bits of space. There is also a WAR
streaming algorithm for rank-$k$ tensor recovery, which takes
$\widetilde{\mathcal{O}}(nk^{\lceil\log d\rceil})$ bits of space.

We remark that the above matrix recovery algorithm performs
$\widetilde{\mathcal{O}}(nk)$ measurements using $n$-sparse matrices, which
can be converted into a distributed protocol with
$\widetilde{\mathcal{O}}(n^{2}k)$ processing time. This improves upon the
matrix recovery algorithm in the previous work [FW23] which, if implemented in
a distributed setting, would require $\widetilde{\mathcal{O}}(n^{3}k)$
processing time at each server.

#### Additional Applications.

Our $k$-sparse recovery algorithm can be used to construct an $L_{0}$-norm
estimation algorithm following the same recipe in [FW23]. In short, by running
our $k$-sparse recovery algorithm with the sparsity parameter $k$ set to
$n^{1-\alpha}$ for some constant $\alpha$, we can get an
$n^{\alpha}$-approximation to the $L_{0}$ norm of a vector. In comparison to
[FW23], our construction again removes the need for a random oracle or the
need to store a lot of randomness.

###  1.4 Technical Overview

We leverage structural properties of lattice-based assumption to address all
drawbacks listed above. In particular, departing from the previous
construction of [FW23], we work with a suitable fully homomorphic encryption
(FHE) scheme to achieve the desired property. We start with an intuitive
explanation of the previous construction in [FW23].

#### Previous Construction

One general framework for solving the sparse recovery problem is to run a weak
recovery algorithm as a black-box subroutine, which potentially provides a
garbage output, in addition to an additional “tester” scheme to verify whether
the recovery output matches the original input (i.e., is a correct recovery)
or is garbage. In the oblivious streaming setting, such a “tester” can be
efficiently implemented using, e.g., a random polynomial “fingerprint” [CJ19].
However, this approach is not WAR as the randomness of the sampler is revealed
and thus not independent of the stream.

Instead, [FW23] uses a random matrix $\mathbf{A}$ to implement a WAR tester,
which is assumed to be heuristically compressed by an idealized hash function.
During the stream, [FW23] maintains a hash $h=\mathbf{A}\bm{x}$, where
$\bm{x}$ is the data vector implicitly defined by the stream. In the testing
stage, it acknowledges an output $\bm{x^{\prime}}$ to be a correct recovery if
and only if $\bm{x^{\prime}}$ is $k$-sparse and $\mathbf{A}\bm{x^{\prime}}$
equals the hash $h$. The idea is that if there exists a $k$-sparse collision
$\bm{x^{\prime}}$ satisfying $\mathbf{A}(\bm{x}-\bm{x^{\prime}})=0$ and
$\bm{x^{\prime}}\neq\bm{x}$, then an adversary can brute-force over all
$k$-sparse vectors to find such $\bm{x}-\bm{x^{\prime}}$, which is a solution
to the SIS problem. To spawn $n$ matrix columns and support the brute-force
reduction, the security parameter (i.e., the number of rows of $\mathbf{A}$)
needs to be in $\omega(k\log n)$, assuming the sub-exponential security of
SIS.

#### Efficient Reduction.

The number of matrix rows in the previous construction depends on the sparsity
parameter $k$ due to a brute-forcing step in the reduction. To grant enough
time for iterating through all $k$-sparse vectors (with
$\operatorname{\mathsf{poly}}(n)$-bounded entries), the security parameter has
to be greater than $k\log n$, which results in $\widetilde{\mathcal{O}}(k)$
time to process every single update. Our first idea is to construct a poly-
time reduction in order to remove such a dependency on $k$. This allows us to
achieve better space and time efficiency, in addition to basing the
construction on a polynomial hardness assumption.

The observation is that the non-existence of a sparse collision is an overly
strong condition. Instead, for our purpose, we only need to ensure that such a
collision, if it exists, cannot be found by the poly-time weak recovery scheme
that the algorithm runs. Thus, in the reduction, instead of brute-forcing over
all $k$-sparse vectors, we let the adversary run the same poly-time weak
recovery scheme that the algorithm does. If a collision $\bm{x^{\prime}}$
satisfying $\mathbf{A}\bm{x}=\mathbf{A}\bm{x^{\prime}}$ is output by the
scheme, then the adversary can still break the security assumption.

#### Reducing the Amount of Randomness.

The rest of our effort will be attributed to reducing the size of the state of
the algorithm. Rather than using a truly random giant matrix to hash the data
as in the previous construction, we would like to design a short digest
(ideally linear-sized in the security parameter) and generate the columns of
the hash matrix on the fly. This naturally yields correlated columns as
opposed to the truly random columns in an SIS matrix. We aim to show that in
this setting, the chance of finding a collision is still negligible.

#### Streaming Friendly Collision-Resistant Hash.

Our main insight from cryptography to address the issue above is that we could
construct a hash function family $\mathcal{H}$, with special properties to
help solve our streaming problem:

  * •

The hash key $h\leftarrow\mathcal{H}$ is small in size, ideally polynomial in
the security parameter $\lambda$ (or even polylogarithmic assuming
subexponential time assumptions).

  * •

The hash should be computable in a streaming fashion and it should be
updatable where each update takes polynomial time in the security parameter
$\lambda$ (or even polylogarithmic time assuming subexponential time
assumptions).

  * •

The hash key should be pseudorandom. In other words, in our real-world
implementation, the white-box adversarial streaming model does not allow us to
use any structured randomness (such as with hidden planted secrets). In the
proof, however, we could introduce these secrets which will be important for
our construction.

  * •

The hash should satisfy collision-resistance.

#### Constructing Streaming Friendly Hashing from FHE.

How could we build such a hash function? The SIS based hash function does have
a fast update time. On the other hand, we could take an arbitrary collision
resistant function that compresses the number of bits by a factor of $1/2$ and
use it to perform a Merkle tree style hashing to hash strings of arbitrary
length. Such a hash will have $\operatorname{\mathsf{poly}}(\lambda)$-sized
hashing keys. Unfortunately, the first idea suffers from a large hashing key
size, which could be shortened in the random oracle (RO) model by using the RO
to store the SIS matrix. Moreover, the second proposal will not support
positive and negative stream updates to the coordinates of the underlying
vector.

Our main idea is to leverage a suitably chosen Fully Homomorphic Encryption
(FHE) scheme satisfying mild structural properties (that are satisfied
currently by most schemes based on LWE and Ring-LWE) to build such a hash
function. Our construction bears a resemblance to the construction of a
collision resistant function from a private information retrieval scheme,
where the private information retrieval scheme is implemented by a fully
homomorphic encryption scheme.

We directly explain the idea in the context of our construction. In our hash
function, the hash key consists of $L=O(\log n)$ ciphertexts
$\mathsf{ct}_{1},\ldots,\mathsf{ct}_{L}$. We assume that our FHE scheme has
pseudorandom ciphertexts and pseudorandom public keys. In our actual scheme,
these ciphertexts will be generated as random strings. It is only in the proof
that they will correspond to encryptions of carefully chosen values.

The idea is that from these $L$ ciphertexts, we will derive $n$ evaluated
ciphertexts $\widehat{\mathsf{ct}}_{j}$ for $j\in[n]$ by evaluating $L$
ciphertexts on simple functions $C_{1},\ldots,C_{n}$ (described later). These
$n$ ciphertexts will correspond to columns of the SIS type hashing. The hash
of a vector $\bm{x}$ is computed as the linear combination
$\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}_{i}$ where $\bm{x}_{i}$ is the
$i^{th}$coordinate. Here the sum is done over the field on which the FHE
ciphertexts live.

The circuits $C_{1},\ldots,C_{n}$ are chosen keeping the security proof in
mind. The ciphertexts $\mathsf{ct}_{1},\ldots,\mathsf{ct}_{L}$ are “thought”
to encrypt a value $m\in\\{0,1\\}^{L}$ that will be chosen in the proof, and
each $C_{i}(\cdot)$ on input $m$ outputs $1$ if $i=m$ and $0$ otherwise.
Observe that these circuits are polynomial in $L=O(\log n)$ sized and
therefore can be evaluated on $\mathsf{ct}_{1},\ldots,\mathsf{ct}_{L}$ in
polynomial in $(\lambda,\log n)$ time guaranteeing fast updates.

How do we prove security? The idea is that if an adversary breaks collision-
resistance it will produce two vectors $\bm{x}\neq\bm{x^{\prime}}$, so that
the corresponding hashes
$\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}_{i}=\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}^{\prime}_{i}$.
Suppose one could know exactly one coordinate $v\in[n]$ so that
$\bm{x}_{v}\neq\bm{x}^{\prime}_{v}$. Then we could set $m=v$. In this case
$\widehat{\mathsf{ct}_{v}}$ encrypts $1$ and the other ciphertexts encrypt
$0$. In this case,
$\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}_{i}=\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}^{\prime}_{i}$
would lead to a contradiction if our FHE scheme has a special property (that
is satisfied by common FHE schemes). The property is that if
$\widehat{\mathsf{ct}_{i}}$ encrypts bit $\mu_{i}\in\\{0,1\\}$ and
$\bm{x}_{i}$ are small norm then there is a decryption algorithm that uniquely
binds $\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}_{i}$ to
$\sum_{i\in[n]}\mu_{i}\bm{x}_{i}$. If this holds, then the equality
$\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}_{i}=\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}^{\prime}_{i}$
would imply $\bm{x}_{v}=\bm{x}^{\prime}_{v}$ which is a contradiction.

This leads us to two remaining problems:

  1. 1.

Given that we do not know $\bm{x}$ and $\bm{x^{\prime}}$ ahead of time, how do
we decide which index $m$ to encrypt such that it will help identify whether
$\bm{x}=\bm{x^{\prime}}$?

  2. 2.

Moreover, a WAR algorithm cannot actually encrypt FHE ciphertexts, since all
randomness and parameters used by the algorithm will be exposed to the
adversary. Instead, we want our digest to be unstructured and truly random.

#### FHE with a Pseudorandom Property.

We solve both issues above by considering a pseudorandom property of the FHE
scheme and show that a random guess of the index $m$ actually suffices. We
assume that the distributions of public keys and ciphertexts of the FHE scheme
are indistinguishable, respectively, from some truly random distributions from
the perspective of the adversary.

We sample truly random digests in our construction, and perform a random guess
of $m\in[n]$ in the proof. If an adversary finds a collision pair
$\bm{x}\neq\bm{x^{\prime}}$ with probability $\gamma$, then with probability
$p\geq\gamma/n$, our guess pins down a coordinate of disagreement
$\bm{x}_{m}\neq\bm{x^{\prime}}_{m}$. In the proof, we then switch the
ciphertexts to encrypt $m$. The chance of guessing the disagreement is still
$p$, as otherwise one can distinguish the pseudorandom ciphertext. However, as
argued earlier, $\bm{x}_{m}\neq\bm{x^{\prime}}_{m}$ roughly implies
$\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}_{i}\neq\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x^{\prime}}_{i}$,
and thus two distinct vectors cannot form a hash collision that fools our
“tester”.

In our complexity analysis, we instantiate the FHE scheme using GSW [GSW13],
which satisfies the additional properties required by our construction. We
remark that in addition to GSW, most current FHE schemes based on LWE and
Ring-LWE also exhibit these properties, and thus they are not an artifact
obtained from a particular FHE scheme.

#### Ring-LWE for the Distributed Setting.

In the distributed model, each remote server receives as input a length-$n$
vector. The goal is to design a protocol such that each server can efficiently
compute a short summary of their partition of data. Adapting the above
streaming algorithm to this setting, each server needs to evaluate $n$
ciphertexts in order to compute a linear combination
$\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\bm{x}_{i}$.

Using a polynomially secure LWE-based FHE scheme, it is unclear how to speed
up such $n$-many individual evaluations as each computation takes
$\operatorname{\mathsf{poly}}(\lambda)$ operations, resulting in a total
complexity of $n\operatorname{\mathsf{poly}}(\lambda)$, where $\lambda$ is the
security parameter. Therefore, we appeal to the Ring-LWE assumption, which is
an algebraic variant of LWE that works over the ring
$\mathbb{Z}_{p}[x]/(x^{N}+1)$. Over this ring, we can exploit the SIMD
property of Ring-LWE by packing the data as ring elements, i.e., we represent
the input vectors as partitioned segments of length proportional to the
security parameter (rather than the vector length $n$), and efficiently
operate on them segment-by-segment using the Fast Fourier Transform. This
improves the processing time of each server to be almost linear in the
dimension of the data. We refer the reader to Section 5 for more details.

#### Summary.

Leveraging FHE or lattice-based assumptions in algorithm design are relatively
new techniques. We think it would be good to explore their applications more
broadly in robust algorithms, beyond the recovery problems or even the
adversarial settings considered here.

##  2 Preliminaries

#### Basic Notations.

For a finite set $S$, we write $x\xleftarrow{\$}S$ to denote a uniform sample
$x$ from $S$. Our logarithms are in base $2$. For $n\in\mathbb{R}$, we use
$\lceil n\rceil$ to denote rounding $n$ up to the nearest integer. For a
vector $\bm{x}$, $\lVert\bm{x}\rVert_{0}$ denotes the $\ell_{0}$ norm of
$\bm{x}$, which is the number of its non-zero entries. We abbreviate PPT for
probabilistic polynomial-time. A function
$\mathsf{negl}:\mathbb{N}\to\mathbb{R}$ is negligible if for every constant
$c>0$ there exists an integer $N_{c}$ such that $\mathsf{negl}(x)<x^{-c}$ for
all $x>N_{c}$. Let $\mathds{1}(p)$ for some proposition $p$ be an indicator
variable, which equals $1$ if $p$ is true and $0$ otherwise. We use
$\bm{b}_{i}$ to denote the standard basis vector, whose $i$-th entry equals
$1$ and $0$ anywhere else.

###  2.1 Lattice Preliminaries

#### General definitions.

A _lattice_ $\mathcal{L}$ is a discrete subgroup of $\mathbb{R}^{g}$, or
equivalently the set
$\mathcal{L}(\bm{b}_{1},\dots,\bm{b}_{m})=\left\\{\sum_{i=1}^{g}x_{i}\bm{b}_{i}~{}:~{}x_{i}\in\mathbb{Z}\right\\}$
of all integer combinations of $g$ vectors
$\bm{b}_{1},\dots,\bm{b}_{m}\in\mathbb{R}^{g}$ that are linearly independent.
Such $\bm{b}_{i}$’s form a _basis_ of $\mathcal{L}$. The lattice $\mathcal{L}$
is said to be _full-rank_ if $g=m$. We denote by $\lambda_{1}(\mathcal{L})$
the so-called first minimum of $\mathcal{L}$, defined to be the length of a
shortest non-zero vector of $\mathcal{L}$.

#### Discrete Gaussian and Related Distributions.

For any $s>0$, define $\rho_{s}(\bm{x})=\exp(-\pi\|\bm{x}\|^{2}/s^{2})$ for
all $\bm{x}\in\mathbb{R}^{g}$. We write $\rho$ for $\rho_{1}$. For a discrete
set $S$, we extend $\rho$ to sets by $\rho_{s}(S)=\sum_{\bm{x}\in
S}\rho_{s}(\bm{x})$. Given a lattice $\mathcal{L}$, the _discrete Gaussian_
$\mathcal{G}_{\mathcal{L},s}$ is the distribution over $\mathcal{L}$ such that
the probability of a vector $\bm{y}\in\mathcal{L}$ is proportional to
$\rho_{s}(\bm{y})$:
$\Pr_{X\leftarrow\mathcal{G}_{\mathcal{L},s}}[X=\bm{y}]=\frac{\rho_{s}(\bm{y})}{\rho_{s}(\mathcal{L})}.$

The discrete Gaussian is not bounded but with overwhelming probability a
sample from $\mathcal{G}_{\mathcal{L},s}$ is bounded by $s\sqrt{g}$ in
$\ell_{2}$ norm.

#### Lattice Problems.

We consider worst-case and average-case problems over lattices. We start by
defining the gap version of the shortest vector problem.

######  Definition 2.1.

For any function $\gamma=\gamma(g)\geq 1$, the decision problem
$\mathsf{GapSVP}_{\gamma}$ (Gap Shortest Vector Problem) is defined as
follows: the input is a basis $\bm{B}$ for a lattice
$\mathcal{L}\subset\mathbb{R}^{g}$ and a real number $d>0$ that satisfy the
promise that $\lambda_{1}(\mathcal{L}(\bm{B}))\leq d$, or
$\lambda_{1}(\mathcal{L}(\bm{B}))\geq\gamma d$. The goal is to decide whether
$\lambda_{1}(\mathcal{L}(\bm{B}))\leq d$, or
$\lambda_{1}(\mathcal{L}(\bm{B}))\geq\gamma d$.

This problem is known to be $\mathsf{NP}$ hard for $\gamma=g^{o(1)}$ [Kho04,
HR07], and is known to be inside $\mathsf{NP}\cap\mathsf{coNP}$ for
$\gamma=O(\sqrt{g})$ [AR05, GG00]. The problem is believed to be intractable
by polynomial time adversaries even for $\gamma=2^{g^{\epsilon}}$ for
$0<\epsilon<1$.

Next, we define the Learning with Errors problem $\mathsf{LWE}$.

######  Definition 2.2 (Learning with Errors).

Suppose we are given an integer dimension $g\in\mathbb{N}$, a modulus
$q\in\mathbb{N}$, a sample complexity $h\geq\Omega(g\cdot\log q)$ and a
parameter $\sigma\in\mathbb{R}^{\geq 0}$. Define an error distribution as the
discrete Gaussian $\chi^{h}_{\sigma}:=\mathcal{G}_{\sigma,\mathbb{Z}^{h}}$. We
define $\mathsf{LWE}_{g,h,q,\chi^{h}_{\sigma}}$ as follows: sample a matrix
$\mathbf{A}\leftarrow\mathbb{Z}^{g\times h}_{q}$ and a secret
$\bm{s}\in\mathbb{Z}^{1\times g}_{q}$. Sample an error vector
$\bm{e}\leftarrow\chi^{h}_{\sigma}$. The problem is to distinguish
$(\mathbf{A},\bm{s}\mathbf{A}+\bm{e}\mod q)$ from $(\mathbf{A},\bm{r})$ where
$\bm{r}$ is random in $\mathbb{Z}^{1\times h}_{q}$.

Under quantum and classical reductions it can be shown that
$\mathsf{LWE}_{g,h,q,\chi_{\sigma}}$ is harder to solve than
$\mathsf{Gap\mbox{-}SVP}_{\gamma}$ with $\gamma=g\frac{q}{\sigma}$.

We also consider the Ring-LWE problem, which is an average-case lattice
problems over ideal lattices.

######  Definition 2.3 (Ring-LWE).

Let $q\geq 1$ be a prime number, and let $g$ be a power of $2$. Let $g,\sigma$
be positive integers. The $\mathsf{Ring\mbox{-}LWE}_{g,h,q,\chi_{\sigma}}$
problem is defined as follows: Consider $R=\frac{\mathbb{Z}_{q}[x]}{x^{g}+1}$.
Sample at random $\bm{a}_{1},\cdots,\bm{a}_{h}\leftarrow R$ and a secret
polynomial $\bm{s}\leftarrow R$. Sample $h$ error polynomials
$\bm{e}_{1},\cdots,\bm{e}_{h}$ such that each $\bm{e}_{i}$ is a
$g$-dimensional vector
$\bm{e}_{i}\leftarrow\chi_{\sigma}=\mathcal{G}_{\sigma,\mathbb{Z}^{g}}$. The
problem is to distinguish the tuple
$(\bm{a}_{1},\cdots,\bm{a}_{h},\\{\bm{s}\bm{a}_{i}+\bm{e}_{i}\\}_{i\in[h]})$
from $(\bm{a}_{1},\cdots,\bm{a}_{h},\\{\bm{r}_{i}\\}_{i\in[h]})$ where
$\bm{r}_{1},\cdots,\bm{r}_{h}$ are random polynomials in $R$.

The Ring-LWE problem is as hard as worst-case problems over ideal lattices
[LPR10]. Ring LWE is sometimes advantageous to use over LWE because of shorter
parameters. One ring LWE element is of dimension $g$, and requires only one
ring element as a coefficient, as opposed to $g$ vectors in the case of LWE.
Moreover, ring multiplication can be sped up using number-theoretic transforms
[SV11].

###  2.2 Fully Homomorphic Encryption

#### Notation.

We denote the security parameter of a cryptographic scheme by $\lambda$. We
write PPTλ to denote probabilistic poly-time in $\lambda$. We say two
ensembles of distributions
$\\{{\mathcal{D}}_{\lambda}\\}_{\lambda\in\mathbb{N}}$ and
$\\{{\mathcal{D}}^{\prime}_{\lambda}\\}_{\lambda\in\mathbb{N}}$ are
computationally indistinguishable, denoted by $\approx_{c}$, if for any non-
uniform PPT adversary ${\mathcal{A}}$ there exists a negligible function
$\mathsf{negl}$ such that ${\mathcal{A}}$ can distinguish between the two
distributions with probability at most $\mathsf{negl}(\lambda)$.

######  Remark 2.1.

We also define $({\mathcal{T}},\epsilon)$-indistinguishability, where
${\mathcal{T}}$ and $\epsilon$ are two functions in $\lambda$. We say that two
distribution ensembles $\\{{\mathcal{D}}_{\lambda}\\}_{\lambda\in\mathbb{N}}$
and $\\{{\mathcal{D}}^{\prime}_{\lambda}\\}_{\lambda\in\mathbb{N}}$ are
$({\mathcal{T}},\epsilon)$-indistinguishable, denoted by
$\approx_{({\mathcal{T}},\epsilon)}$, if there exists an integer $\lambda_{0}$
such that for all $\lambda>\lambda_{0}$, for every adversary $\mathcal{A}$,
${\mathcal{A}}$ can distinguish between the two distributions with probability
at most $\epsilon(\lambda)$.

######  Definition 2.4 (FHE).

A fully homomorphic encryption $\mathsf{FHE}$ scheme is a tuple of _PPT λ_
algorithms
$\mathsf{FHE}=(\mathsf{FHE}.\mathsf{Setup},\mathsf{FHE}.\mathsf{Enc},\mathsf{FHE}.\mathsf{Eval},\mathsf{FHE}.\mathsf{Dec})$
with the following properties:

  * •

$\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})\to(\mathsf{sk},\mathsf{pk})$ : On
input a security parameter $\lambda$, the setup algorithm outputs a key pair
$(\mathsf{pk},\mathsf{sk})$.

  * •

$\mathsf{FHE}.\mathsf{Enc}(\mathsf{pk},\mu)\to\mathsf{ct}$ : On input a public
key $\mathsf{pk}$ and a message $\mu\in\\{0,1\\}$, the encryption algorithm
outputs a ciphertext $\mathsf{ct}$.

  * •

$\mathsf{FHE}.\mathsf{Eval}(\mathsf{pk},C,\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\ell})\to\widehat{\mathsf{ct}}$
: On input a public key $\mathsf{pk}$, a circuit
$C:\\{0,1\\}^{\ell}\to\\{0,1\\}$ of depth at most
$\operatorname{\mathsf{poly}}(\lambda)$, and a tuple of ciphertexts
$\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\ell}$, the evaluation algorithm outputs
an evaluated ciphertext $\widehat{ct}$.

  * •

$\mathsf{FHE}.\mathsf{Dec}(\mathsf{pk},\mathsf{sk},\widehat{\mathsf{ct}})\to\widehat{\mu}$
: On input a public key $\mathsf{pk}$, a secret key $\mathsf{sk}$, and a
ciphertext $\widehat{\mathsf{ct}}$ , the decryption algorithm outputs a
message $\widehat{\mu}\in\\{0,1,\bot\\}$.

We also require an $\mathsf{FHE}$ scheme to satisfy compactness, correctness,
and security properties as follows:

######  Definition 2.5 ($\mathsf{FHE}$ Compactness).

We say that a $\mathsf{FHE}$ scheme is compact if there exists a polynomial
$\operatorname{\mathsf{poly}}(\cdot)$ such that for all security parameters
$\lambda$, circuits $C:\\{0,1\\}^{\ell}\to\\{0,1\\}$ of depth at most
$\operatorname{\mathsf{poly}}(\lambda)$, and $\mu_{i}\in\\{0,1\\}$ for
$i\in[\ell]$, the following holds: Given
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})$,
$\mathsf{ct}_{i}\leftarrow\mathsf{FHE}.\mathsf{Enc}(\mathsf{pk},\mu_{i})$ for
$i\in[\ell]$,
$\widehat{\mathsf{ct}}\leftarrow\mathsf{FHE}.\mathsf{Eval}(\mathsf{pk},C,\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\ell})$,
we always have
$\lvert\widehat{\mathsf{ct}}\rvert\leq\operatorname{\mathsf{poly}}(\lambda)$.

######  Definition 2.6 ($\mathsf{FHE}$ Correctness).

We say that a $\mathsf{FHE}$ scheme is correct if for all security parameters
$\lambda$, circuit $C:\\{0,1\\}^{\ell}\to\\{0,1\\}$ of depth at most
$\operatorname{\mathsf{poly}}(\lambda)$, and $\mu_{i}\in\\{0,1\\}$ for
$i\in[\ell]$, the following holds: Given
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})$,
$\mathsf{ct}_{i}\leftarrow\mathsf{FHE}.\mathsf{Enc}(\mathsf{pk},\mu_{i})$ for
$i\in[\ell]$,
$\widehat{\mathsf{ct}}\leftarrow\mathsf{FHE}.\mathsf{Eval}(\mathsf{pk},C,\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\ell})$,

$\mathsf{Pr}[\mathsf{FHE}.\mathsf{Dec}(\mathsf{pk},\mathsf{sk},\widehat{\mathsf{ct}})=f(\mu_{1},\cdots,\mu_{\ell})]=1.$

######  Definition 2.7 ($\mathsf{FHE}$ Security).

We say that a $\mathsf{FHE}$ scheme satisfies security if for all security
parameter $\lambda$, the following holds: For any PPTλ adversary
$\mathcal{A}$, there exists a negligible function $\mathsf{negl}$ such that

$\mathsf{adv}_{\mathcal{A},\mathsf{FHE}}:=2\cdot\lvert
1/2-\Pr[\mathsf{Expt}_{\mathcal{A},\mathsf{FHE}}(1^{\lambda})=1]\rvert<\mathsf{negl}(\lambda),$

where the experiment $\mathsf{Expt}_{\mathcal{A},\mathsf{FHE}}$ is defined as
follows:

$\mathsf{Expt}_{\mathcal{A},\mathsf{FHE}}(1^{\lambda}):$

  1. 1.

On input the security parameter $1^{\lambda}$, the challenger runs
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})$,
and $\mathsf{ct}\leftarrow\mathsf{FHE}.\mathsf{Enc}(\mathsf{pk},b)$ for
$b\xleftarrow{\$}\\{0,1\\}$. It provides $(\mathsf{pk},\mathsf{ct})$ to
$\mathcal{A}$.

  2. 2.

$\mathcal{A}$ outputs a guess $b^{\prime}$. The experiment outputs $1$ if and
only if $b=b^{\prime}$.

######  Remark 2.2.

The security definition above is in terms of PPTλ adversaries and
$\mathsf{negl}$ advantage, but it can be lifted to a
$({\mathcal{T}},\epsilon)$ setting similar to Remark 2.1 as follows: We say
that a $\mathsf{FHE}$ scheme is $({\mathcal{T}},\epsilon)$-secure if there
exists an integer $\lambda_{0}$, such that for all $\lambda>\lambda_{0}$, for
any non-uniform probabilistic ${\mathcal{T}}(\lambda)$ time adversary, the
advantage $\mathsf{adv}_{\mathcal{A},\mathsf{FHE}}$ of the above experiment is
at most $\epsilon(\lambda)$.

#### Additional properties.

Our construction of robust streaming algorithms will be based on an
$\mathsf{FHE}$ scheme satisfying a few additional properties. We refer to this
type of $\mathsf{FHE}$ scheme as a pseudorandom $\mathsf{FHE}$
($\mathsf{PFHE}$) scheme.

######  Definition 2.8 (Pseudorandom $\mathsf{FHE}$ ($\mathsf{PFHE}$)).

Let $\mathsf{FHE}$ be a fully homomorphic encryption scheme _(Definition
2.4)_. We call $\mathsf{FHE}$ a $({\mathcal{T}},\epsilon)$-pseudorandom
$\mathsf{FHE}$ scheme if for all security parameters $\lambda$, it satisfies
the following additional properties:

  * •

$\mathsf{FHE}.\mathsf{Eval}$ is deterministic.

  * •

_(Pseudorandom $\mathsf{pk}$)_. There exists an explicit distribution
$\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$, such that the following two
distributions are $({\mathcal{T}},\epsilon)$-indistinguishable:

$\\{\mathsf{pk}:(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})\\}\approx_{({\mathcal{T}},\epsilon)}\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$

  * •

_(Pseudorandom $\mathsf{ct}$)_. There exists an explicitly distribution
$\mathcal{D}_{\widetilde{\mathsf{ct}}(\lambda)}$, such that the following two
distributions are $({\mathcal{T}},\epsilon)$-indistinguishable:

$\left\\{\mathsf{ct}:\begin{aligned}
(\mathsf{pk},\mathsf{sk})&\leftarrow\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})\\\
\mu&\in\\{0,1\\}\\\
\mathsf{ct}&\leftarrow\mathsf{FHE}.\mathsf{Enc}(\mathsf{pk},\mu)\\\
\end{aligned}\right\\}\approx_{({\mathcal{T}},\epsilon)}\mathcal{D}_{\widetilde{\mathsf{ct}}(\lambda)}$

  * •

_( $\mathbb{Z}$ Linear Homomorphism)_. Given
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})$,
the set of all ciphertexts is a subset of a vector space over $\mathbb{Z}_{q}$
for some $q=q(\lambda)$. Let
${\mathcal{M}}=\sum_{i\in[k]}x_{i}\cdot\mathsf{ct}_{i}\mod q$ be an arbitrary
linear combination of ciphertexts. Denote
$\mu_{i}\leftarrow\mathsf{FHE}.\mathsf{Dec}(\mathsf{pk},\mathsf{sk},\mathsf{ct}_{i})$.
Suppose ${\mathcal{M}}$ satisfies:

    1. 1.

$x_{i}\in\mathbb{Z}$ for all $i\in[k]$

    2. 2.

$k\cdot\max_{i\in[k]}x_{i}\ll q$

then we have the following:
$\lvert{\mathcal{M}}\rvert\leq\operatorname{\mathsf{poly}}(\lambda)$. Also,
there exists a $\operatorname{\mathsf{poly}}(\lambda)$-time decoding algorithm
$\mathsf{LinearDec}$, such that
$\Pr[\mathsf{LinearDec}(\mathsf{pk},\mathsf{sk},{\mathcal{M}})=\sum_{i\in[k]}x_{i}\cdot\mu_{i}]=1$.

As in a standard $\mathsf{FHE}$ scheme, we also require $\mathsf{PFHE}$ to
satisfy compactness, correctness, and security.

There exist FHE schemes based on LWE and Ring-LWE [GSW13, BGV12, BV11]
assumptions. We will focus on the GSW scheme in our streaming construction and
the BV scheme in the distributed setting. Both of them satisfy the above
definition (or a slight variant) of $\mathsf{PFHE}$.

###  2.3 Streaming Algorithms

In this section, we recall the streaming model, the structure of a streaming
algorithm, and the formal definition of white-box adversarial robustness.

#### Streaming Model.

The streaming model captures key resource requirements of algorithms for
database, machine learning, and network tasks, where the size of the data is
significantly larger than the available storage. This model was formalized by
Alon, Matias, and Szegedy [AMS96] as a vector undergoing additive updates to
its coordinates. In this model, the input data takes the form of a sequence of
updates. These updates assume the existence of a fixed-length underlying
vector which represents the current dataset, and dynamically modify this
vector one coordinate at a time.

Given a dimension parameter $n\in\mathbb{N}$, the model behaves as follows:

  * •

At the beginning of the stream, an underlying vector $\bm{x}$ is initialized
to $0^{n}$.

  * •

The input stream is a sequence of $T\leq\operatorname{\mathsf{poly}}(n)$
additive updates $(x_{1},\cdots,x_{T})$. Each update $x_{t}$ for $t\in[T]$ is
a tuple $x_{t}:=(i_{t},\Delta_{t})$, where $i_{t}\in[n]$ denotes a coordinate
of $\bm{x}$ and $\Delta_{t}$ is an arbitrary value.

$x_{t}:=(i_{t},\Delta_{t})$ is interpreted as updating
$\bm{x}_{i_{t}}\leftarrow\bm{x}_{i_{t}}+\Delta_{t}$. Thus at any time
$t^{\prime}\in[T]$ during the stream, $\bm{x}$ is the accumulation of all past
updates, with its $i$-th coordinate for $i\in[n]$: $\bm{x}_{i}=\sum_{t\leq
t^{\prime}}\mathds{1}(i_{t}=i_{t_{0}})\cdot\Delta_{t}.$

A streaming algorithm receives the stream of updates and uses limited memory
to compute a function of $\bm{x}$. We stress that during the stream, the
underlying vector $\bm{x}$ is not explicitly available to the algorithm, but
is instead implicitly defined by the sequence of past updates.

In this work, we consider a bounded integer stream, which assumes that
throughout the stream, $\bm{x}$ is promised to be in the range
$\\{-N,-N+1,\cdots,N-1,N\\}^{n}$ for some integer
$N\in\operatorname{\mathsf{poly}}(n)$.

#### Streaming Algorithm.

A streaming algorithm maintains some internal state during the stream, which
evolves upon receiving new updates. It takes one pass over all updates and
then uses its maintained state to compute a function of the underlying dataset
$\bm{x}$. In the streaming model, the dimension parameter $n$ (the length of
$\bm{x}$) is typically large. Therefore, a streaming algorithm usually
optimizes the size of the state so that it takes a sublinear number of bits of
space in $n$ to represent.

We define the general framework for streaming algorithms as follows:

######  Definition 2.9 (Streaming Algorithm).

Given a query function ensemble $\mathcal{F}=\\{f_{n}:\mathbb{Z}^{n}\to
X\\}_{n\in\mathbb{N}}$ for some domain $X$, a streaming algorithm
$\mathsf{StreamAlg}$ that computes $\mathcal{F}$ contains a tuple of
operations $\mathsf{StreamAlg}$ $=$ $(\mathsf{StreamAlg}.\mathsf{Setup}$,
$\mathsf{StreamAlg}.\mathsf{Update},\mathsf{StreamAlg}.\mathsf{Report})$, with
the following properties:

  * •

$\mathsf{StreamAlg}.\mathsf{Setup}(n)$ : On input a dimension parameter $n$,
the setup operation initializes an internal data structure $\mathcal{DS}$
within the memory of $\mathsf{StreamAlg}$.

  * •

$\mathsf{StreamAlg}.\mathsf{Update}(x_{t})$ : On input an additive update
$x_{t}:=(i_{t},\Delta_{t})$, the update operation modifies $\mathcal{DS}$.

  * •

$\mathsf{StreamAlg}.\mathsf{Report}()\to r$: The report operation uses
$\mathcal{DS}$ to compute a query response $r\in X$.

A response $r$ is said to be correct if $r=f_{n}(\bm{x})$, where
$\bm{x}\in\mathbb{Z}^{n}$ is the accumulation of all past updates such that
$\bm{x}_{i}=\sum_{t}\mathds{1}(i_{t}=i)\cdot\Delta_{t}$ for $i\in[n]$.

In this work, we only consider exact computations of query functions
($r=f_{n}(\bm{x})$), though the above definition can also be generalized to
approximation problems ($r\approx f_{n}(\bm{x})$).

#### White-box Adversarial Stream.

In the conventional oblivious stream model, the sequence of updates may be
chosen adversarially, but is assumed to be chosen independently of the
randomness of a streaming algorithm $\mathsf{StreamAlg}$. In contrast, in the
white-box adversarial streaming model, a sequence of stream updates
$(x_{1},\cdots,x_{T})$ is adaptively generated by an adversary who sees the
full internal state of $\mathsf{StreamAlg}$ at all times, including
$\mathcal{DS}$ and any other parameters and randomness used by
$\mathsf{StreamAlg}$. We say that a streaming algorithm is white-box
adversarially robust if it guarantees to output correct responses even against
such powerful adversaries. This is described as the following game:

######  Definition 2.10 (White-Box Adversarially Robustness).

We say a streaming algorithm $\mathsf{StreamAlg}$ is white-box adversarially
robust (WAR) if for all dimension parameters $n\in\mathbb{N}$, the following
holds: For any PPT adversary $\mathcal{A}$, the following experiment
$\mathsf{Expt}_{\mathcal{A},\mathsf{StreamAlg}}(n)$ outputs $1$ with
probability at most $\mathsf{negl}(n)$:

$\mathsf{Expt}_{\mathcal{A},\mathsf{StreamAlg}}(n):$

  1. 1.

The challenger and $\mathcal{A}$ agree on a query function ensemble
$\mathcal{F}=\\{f_{n}:\mathbb{Z}^{n}\to X\\}_{n\in\mathbb{N}}$ for some domain
$X$. On input a dimension parameter $n$, let $f_{n}\in\mathcal{F}$ be the
query function of the experiment.

  2. 2.

The challenger runs $\mathsf{StreamAlg}.\mathsf{Setup}(n)$. It then provides
all internal states of $\mathsf{StreamAlg}$ to $\mathcal{A}$, including
$\mathcal{DS}$ and any other parameters and randomness previously used by
$\mathsf{StreamAlg}$.

  3. 3.

For some $T\in\operatorname{\mathsf{poly}}(n)$, at each time $t\in[T]$:

     * -

$\mathcal{A}$ outputs an adaptive update $x_{t}:=(i_{t},\Delta_{t})$ for
$t\in[T]$. Also, $\mathcal{A}$ may issue a query.

     * -

The challenger runs $\mathsf{StreamAlg}.\mathsf{Update}(x_{t})$, and outputs a
response $r_{t}\leftarrow\mathsf{StreamAlg}.\mathsf{Report}()$ if it is
queried.

The challenger then provides all internal states of $\mathsf{StreamAlg}$ to
$\mathcal{A}$, including $\mathcal{DS}$ and any other parameters and
randomness used by $\mathsf{StreamAlg}$.

  4. 4.

The experiment outputs $1$ if and only if at some time $t\in[T]$ in the
stream, $\mathsf{StreamAlg}$ output an incorrect response $r_{t}\neq
f_{n}(\bm{x})$, where $\bm{x}$ is the underlying data vector with
$\bm{x}_{i}=\sum_{j\in[t]}\mathds{1}(i_{j}=i)\cdot\Delta_{j}$ for $i\in[n]$.

##  3 Streaming $K$-Sparse Recovery

#### Sparse Recovery Problem.

We study the sparse recovery problem for vectors in white-box adversarial
streaming settings. There exist deterministic (thus WAR) streaming algorithms
that recover $k$-sparse vectors assuming that the input vector is $k$-sparse .
However, their outputs can be arbitrary when the input violates such an
assumption. In contrast, our algorithm has the crucial property that it can
detect if the input violates the sparsity constraint. We describe the problem
as follows:

######  Definition 3.1 ($k$-Sparse Recovery).

Given a sparsity parameter $k$ and an input vector $\bm{x}\in\mathbb{Z}^{n}$,
output $\bm{x}$ if $\lVert\bm{x}\rVert_{0}\leq k$ and report $\bot$ otherwise.

Here and throughout, for the sparsity to make sense we always assume $k\leq
n$, though $k$ can be a function in $n$. Before tackling this problem, we
first consider a relaxation for it, which only guarantees correct recovery
when the input vector $\bm{x}$ is $k$-sparse. In other words, we have no
constraint on the function output when $\lVert\bm{x}\rVert_{0}>k$.

######  Definition 3.2 (Relaxed $k$-Sparse Recovery).

Given a sparsity parameter $k$ and an input vector $\bm{x}\in\mathbb{Z}^{n}$,
output $\bm{x}\in\mathbb{Z}^{n}$ if $\lVert\bm{x}\rVert_{0}\leq k$.

As mentioned earlier, there exists a space- and time-efficient, deterministic
streaming algorithm that solves the relaxed $k$-sparse recovery problem, which
we will refer to as $\mathsf{StreamAlg}_{0}$ in our algorithm. With
$\mathsf{StreamAlg}_{0}$ and a $\mathsf{PFHE}$, we are now ready to construct
a WAR streaming algorithm for the $k$-sparse recovery problem.

######  Construction 3.1.

Let $\mathsf{StreamAlg}_{0}$ be an algorithm for the Relaxed $k$-Sparse
Recovery problem. Let $\mathsf{PFHE}$ be a pseudorandom $\mathsf{FHE}$. Let
$\lambda={\mathcal{S}}(n)$ be the security parameter of $\mathsf{PFHE}$, for
some function ${\mathcal{S}}$ in $n$ that we will specify later. Choose
$q\in\operatorname{\mathsf{poly}}(n)$ with $q\gg n\cdot N$ to be the modulus
of $\mathsf{PFHE}$ ciphertexts, where $N\in\operatorname{\mathsf{poly}}(n)$ is
a bound on the stream length. All computations will be modulo $q$. Our
construction is as follows:

  * •

$\mathsf{StreamAlg}.\mathsf{Setup}(n)$:

Run $\mathsf{StreamAlg}_{0}.\mathsf{Setup}(n)$.

Define $\ell=\lceil\log n\rceil$. For each $i\in[n]$, define a circuit
$C_{i}:\\{0,1\\}^{\ell}\to\\{0,1\\}$, such that:

$C_{i}(\mu_{1},\mu_{2},\cdots,\mu_{\ell})=\begin{cases}1&\text{if
$(\mu_{1},\mu_{2},\cdots,\mu_{\ell})$ is the bit representation of $i$}\\\
0&\text{otherwise}.\end{cases}$

Take $\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$ to be the distribution
of pseudo-public key in Definition 2.8. Sample
$\widetilde{\mathsf{pk}}\leftarrow\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$.
Similarly, take $\mathcal{D}_{\widetilde{\mathsf{ct}}(\lambda)}$ to be the
distribution of pseudo-ciphertext in Definition 2.8. Sample
$\widetilde{\mathsf{ct}_{1}},\widetilde{\mathsf{ct}_{2}},\cdots,\widetilde{\mathsf{ct}_{\ell}}\leftarrow\mathcal{D}_{\widetilde{\mathsf{ct}}(\lambda)}$.
Store
$(\widetilde{\mathsf{pk}},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\ell}})$
and $sketch:=0$.

  * •

$\mathsf{StreamAlg}.\mathsf{Update}(i_{t},\Delta_{t})$:

Run $\mathsf{StreamAlg}_{0}.\mathsf{Update}(i_{t},\Delta_{t})$.

Evaluate
$\widehat{\mathsf{ct}_{i_{t}}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\widetilde{\mathsf{pk}},C_{i_{t}},\widetilde{\mathsf{ct}_{1}},\widetilde{\mathsf{ct}_{2}},\cdots,\widetilde{\mathsf{ct}_{\ell}})$.
Then update

$sketch\leftarrow sketch+\Delta_{t}\cdot\widehat{\mathsf{ct}_{i_{t}}}.$

  * •

$\mathsf{StreamAlg}.\mathsf{Report}()$:

Let $\bm{x}^{\prime}\leftarrow\mathsf{StreamAlg}_{0}.\mathsf{Report}()$.

If $\lVert\bm{x}^{\prime}\rVert_{0}>k$, output $\bot$. Otherwise, evaluate
$\widehat{\mathsf{ct}_{i}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\widetilde{\mathsf{pk}},C_{i},\widetilde{\mathsf{ct}_{1}},\widetilde{\mathsf{ct}_{2}},\cdots,\widetilde{\mathsf{ct}_{\ell}})$
for all $i\in[n]$. Then compute

$hash\leftarrow\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\cdot\bm{x^{\prime}}_{i}.$

Output $\bm{x}^{\prime}$ if $hash=sketch$, and output $\bot$ otherwise.

#### Robustness.

Recall that in the $\mathsf{FHE}$ Preliminary section, we define the
$({\mathcal{T}},\epsilon)$-security of a $\mathsf{FHE}$ scheme, where
${\mathcal{T}}$ and $\epsilon$ are functions in $\lambda$. Also, in
Construction 3.1, we set $\lambda={\mathcal{S}}(n)$ for some function
$\mathcal{S}$. We will show that given appropriate relationships between these
functions, the $\mathsf{StreamAlg}$ scheme in Construction 3.1 is WAR. We
state our main theorem as follows:

######  Theorem 3.1 (WAR of Construction 3.1).

Suppose $\mathsf{StreamAlg}_{0}$ is a deterministic, polynomial time streaming
algorithm for Relaxed $k$-Sparse Recovery, and $\mathsf{PFHE}$ is a
pseudorandom $\mathsf{FHE}$ scheme with $({\mathcal{T}},\epsilon)$-security.
Let $\lambda={\mathcal{S}}(n)$ be the $\mathsf{PFHE}$ security parameter for
some function $\mathcal{S}$.

If for all $n\in\mathbb{N}$, functions ${\mathcal{T}},\epsilon,$ and
${\mathcal{S}}$ satisfy:

  * ·

${\mathcal{T}}(\mathcal{S}(n))=\Omega(\operatorname{\mathsf{poly}}n)$

  * ·

$\epsilon(\mathcal{S}(n))\leq\mathsf{negl}(n)$ for some negligible function
$\mathsf{negl}$.

then the $\mathsf{StreamAlg}$ scheme in _Construction 3.1_ is a WAR streaming
algorithm for the $k$-Sparse Recovery problem.

######  Remark 3.1.

Roughly, we need
$\operatorname{\mathsf{poly}}(n)\subseteq{\mathcal{T}}(\mathcal{S}(n))$ to
convert between the runtime of a $\mathsf{PFHE}$ adversary and a
$\mathsf{StreamAlg}$ adversary. We also need
$\epsilon(\mathcal{S}(n))\leq\mathsf{negl}(n)$ to convert between the
advantage of a $\mathsf{PFHE}$ adversary and a $\mathsf{StreamAlg}$ adversary.

###### Proof (of Theorem 3.1).

We first show that at any time during the stream, if the underlying vector
$\bm{x}$ is $k$-sparse, then the query response of $\mathsf{StreamAlg}$ is
correct.

######  Lemma 3.1.

Suppose $\mathsf{PFHE}$ satisfies _Definition 2.8_ and
$\mathsf{StreamAlg}_{0}$ solves the Relaxed $k$-Sparse Recovery problem. Then
the following holds: at any time $t\in[T]$, if the current underlying vector
$\bm{x}$ satisfies $\lVert\bm{x}\rVert_{0}\leq k$, then
$\mathsf{StreamAlg}.\mathsf{Report}$ correctly outputs $\bm{x}$.

###### Proof.

By the correctness of the $\mathsf{StreamAlg}_{0}$ scheme, when
$\lVert\bm{x}\rVert_{0}\leq k$, $\mathsf{StreamAlg}_{0}.$ $\mathsf{Report}$
outputs $\bm{x}^{\prime}=\bm{x}$. Since Definition 2.8 restricts
$\mathsf{PFHE}.\mathsf{Eval}$ to be deterministic, we essentially have
$hash=\sum_{i\in[n]}\widehat{ct}_{i}\cdot\bm{x^{\prime}}_{i}\hskip
3.00003pt\text{ and }\hskip
3.00003ptsketch=\sum_{i\in[n]}\widehat{ct}_{i}\cdot\bm{x}_{i}$ for the same
set of ciphertexts $\widehat{ct}_{i}$. Thus $hash=sketch$ follows from
$\bm{x}^{\prime}=\bm{x}$. In this case, $\mathsf{StreamAlg}.\mathsf{Report}$
correctly outputs $\bm{x}$ as desired.

∎

It remains to show the correctness of responses in the case when the
underlying data vector is denser than $k$. Our proof proceeds via a sequence
of hybrid experiments between an adversary $\mathcal{A}$ and a challenger.

  * •

$\mathbf{Hybrid}_{0}$: This is a real WAR experiment
$\mathsf{Expt}_{\mathcal{A},\mathsf{StreamAlg}}(n)$ from Definition 2.10,
where the challenger runs the $\mathsf{StreamAlg}$ scheme from Construction
3.1. On input a dimension parameter $n$, the challenger samples
$\widetilde{\mathsf{pk}}\leftarrow\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$
and
$\widetilde{\mathsf{ct}_{1}},\widetilde{\mathsf{ct}_{2}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}}\leftarrow\mathcal{D}_{\widetilde{\mathsf{ct}}(\lambda)}$ from the
distributions of pseudo-public key and pseudo-ciphertext (Definition 2.8) and
provides them to $\mathcal{A}$.

$\mathcal{A}$ outputs $T\in\operatorname{\mathsf{poly}}(n)$ -many adaptive
updates $x_{t}:=(i_{t},\Delta_{t})$ upon seeing past internal states of
$\mathsf{StreamAlg}$. At any time $t\in[T]$, these updates implicitly define
an underlying vector $\bm{x}$, whose $i$-th coordinate
$\bm{x}_{i}=\sum_{t}\mathds{1}(i_{t}=i)\cdot\Delta_{t}$ for $i\in[n]$.

  * •

$\mathbf{Hybrid}_{1}$: This is the same experiment as $\mathbf{Hybrid}_{0}$,
except that $\mathcal{A}$ now runs some additional extraction on itself:

    * -

At each time $t\in[T]$, $\mathcal{A}$ computes the underlying vector $\bm{x}$
defined by all of its past updates.

    * -

$\mathcal{A}$ runs an additional instance of the $\mathsf{StreamAlg}_{0}$
scheme from Definition 3.2 (which solves the Relaxed k-Sparse Recovery
problem):

      1. 1.

Before $\mathcal{A}$ generates its first update, it initializes its
$\mathsf{StreamAlg}_{0}$ instance to be in the same state as the
$\mathsf{StreamAlg}_{0}$ scheme run by the challenger. (i.e., $\mathcal{A}$
runs $\mathsf{StreamAlg}_{0}.\mathsf{Setup}(n)$ using the same set of
randomness used by the challenger.)

      2. 2.

At each time $t\in[T]$, after $\mathcal{A}$ generates an update $x_{t}$, it
calls
$\mathsf{StreamAlg}_{0}.\mathsf{Update}(x_{t})$ and then
$\mathsf{StreamAlg}_{0}.\mathsf{Report}()$ to get a query response
$\bm{x}^{\prime}$.

We note that if $\mathcal{A}$ runs in $\operatorname{\mathsf{poly}}(n)$ time
in $\mathbf{Hybrid}_{0}$, then it still runs in
$\operatorname{\mathsf{poly}}(n)$ time in $\mathbf{Hybrid}_{1}$ since
computing $\bm{x}$ is trivial and $\mathsf{StreamAlg}_{0}$ runs in poly-time.

For an adversary $\mathcal{A}$, we write $\mathsf{Hyb}_{i}(\mathcal{A})$ to
denote the output of $\mathbf{Hybrid}_{i}$.

######  Lemma 3.2.

For any adversaries $\mathcal{A}$,
$\lvert\Pr[\mathsf{Hyb}_{0}(\mathcal{A})=1]-\Pr[\mathsf{Hyb}_{1}(\mathcal{A})=1]\rvert=0$.

###### Proof.

This just follows from the fact that the additional extractions run by
$\mathcal{A}$ do not affect the output of the experiments. ∎

  * •

$\mathbf{Hybrid}_{2}$: Same as $\mathbf{Hybrid}_{1}$, except that at the
beginning of the experiment, the challenger samples a random coordinate
$m\xleftarrow{\$}[n]$ which will be hidden from $\mathcal{A}$. The experiment
outputs $1$ if at some time $t\in[T]$ both of the following holds:

    1. 1.

$\mathsf{StreamAlg}$ outputs an incorrect response $r_{t}\neq f_{n}(\bm{x})$
(i.e., the same condition for $\mathsf{Hyb}_{1}(\mathcal{A})=1$),

    2. 2.

The $m$-th coordinates of $\bm{x}$ and $\bm{x^{\prime}}$ extracted by
$\mathcal{A}$ satisfy $\bm{x}_{m}\neq\bm{x^{\prime}}_{m}$,

We show that with the additional success condition, the success probability of
$\mathbf{Hybrid}_{2}$ drops by at most a $1/n$ multiplicative factor compared
to $\mathbf{Hybrid}_{1}$.

######  Lemma 3.3.

For any adversaries $\mathcal{A}$,
$\Pr[\mathsf{Hyb}_{2}(\mathcal{A})=1]\geq\Pr[\mathsf{Hyb}_{1}(\mathcal{A})=1]/n$.

Before proving Lemma 3.3, we make the following observation:

######  Claim 3.1.

At any time $t\in[T]$ during the $\mathbf{Hybrid}_{2}$ experiment, if
$\mathsf{StreamAlg}$ outputs an incorrect response $r_{t}\neq f_{n}(\bm{x})$,
and $\bm{x}$ and $\bm{x^{\prime}}$ are the vectors extracted by $\mathcal{A}$
at time $t$, then $\bm{x^{\prime}}\neq\bm{x}$.

###### Proof.

By Lemma 3.1, $r_{t}\neq f_{n}(\bm{x})$ can occur only when
$\lVert\bm{x}\rVert_{0}>k$ and $r_{t}\neq\bot$. In this case, by the
construction of $\mathsf{StreamAlg}.\mathsf{Report}$, $r_{t}$ should be a
$k$-sparse vector, and thus different from $\bm{x}$. Also, using deterministic
$\mathsf{StreamAlg}_{0}.\mathsf{Update}$ and
$\mathsf{StreamAlg}_{0}.\mathsf{Report}$, $\mathcal{A}$ exactly extracts
$\bm{x^{\prime}}=r_{t}$, so $\bm{x^{\prime}}\neq\bm{x}$. ∎

Lemma 3.3 then follows from Claim 3.1:

###### Proof (of Lemma 3.3)..

Claim 3.1 states that $\bm{x^{\prime}}\neq\bm{x}$, and in particular,
$\bm{x^{\prime}}$ and $\bm{x}$ disagree on at least one coordinate. Recall
that the random coordinate $m$ is hidden from $\mathcal{A}$ at all times, so
with probability at least $1/n$, $m$ collides with a coordinate where
$\bm{x^{\prime}}$ and $\bm{x}$ disagree. In this case, both conditions in
$\mathbf{Hybrid}_{2}$ are satisfied, so
$\Pr[\mathsf{Hyb}_{2}(\mathcal{A})=1\mid\mathsf{Hyb}_{1}(\mathcal{A})=1]\geq
1/n$. ∎

  * •

$\mathbf{Hybrid}_{3}$: Same as $\mathbf{Hybrid}_{2}$, except that the
challenger now generates an actual public key
$\mathsf{pk}:(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{PFHE}.\mathsf{Setup}(1^{\lambda})$
to replace $\widetilde{\mathsf{pk}}$.

  * •

$\mathbf{Hybrid}_{4}$: Same as $\mathbf{Hybrid}_{3}$, except that the
challenger now uses the random coordinate $m\xleftarrow{\$}[n]$ (whose bits
are denoted as $m_{1}m_{2}\cdots m_{\lceil\log n\rceil}$) that was sampled
privately as the message in the ciphertexts: It generates $\lceil\log n\rceil$
actual ciphertexts
$\mathsf{ct}_{i}\leftarrow\mathsf{PFHE}.\mathsf{Enc}(\mathsf{pk},m_{i})$ for
$i\in[\lceil\log n\rceil]$ to replace
$(\widetilde{\mathsf{ct}_{1}},\widetilde{\mathsf{ct}_{2}},\cdots,$
$\widetilde{\mathsf{ct}_{\lceil\log n\rceil}})$. i.e.,
$(\mathsf{ct}_{1},\mathsf{ct}_{2},\cdots,\mathsf{ct}_{\lceil\log n\rceil})$
encrypts the bit representation of $m$.

######  Lemma 3.4.

Given that $\mathsf{PFHE}$ satisfies _Definition 2.8_, for any PPTn
adversaries $\mathcal{A}$,
$\lvert\Pr[\mathsf{Hyb}_{2}(\mathcal{A})=1]-\Pr[\mathsf{Hyb}_{3}(\mathcal{A})=1]\rvert\leq\mathsf{negl}(n)$
for some negiligble function $\mathsf{negl}$.

###### Proof.

The only difference in $\mathcal{A}$’s views in $\mathbf{Hybrid}_{2}$ and
$\mathbf{Hybrid}_{3}$ is the way the challenger generates
$\widetilde{\mathsf{pk}}$ or $\mathsf{pk}$. In $\mathbf{Hybrid}_{2}$, the
challenger samples
$\widetilde{\mathsf{pk}}\leftarrow\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$;
and in $\mathbf{Hybrid}_{3}$, the challenger runs
$\mathsf{pk}:(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{PFHE}.\mathsf{Setup}(1^{\lambda})$.
Thus $\mathcal{A}$ distinguishing these two hybrids will distinguish the two
distributions
$\\{\mathsf{pk}:(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{FHE}.\mathsf{Setup}(1^{\lambda})\\}$
and $\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$ with the same advantage.
Also by the $({\mathcal{T}},\epsilon)$-indistinguishability in Definition 2.8,
for any $\operatorname{\mathsf{poly}}(n)\leq{\mathcal{T}}(\lambda)$-sized
adversaries, the latter two distributions can be distinguished with
probability at most $\epsilon(\lambda)\leq\mathsf{negl}(n)$. ∎

######  Lemma 3.5.

Given that $\mathsf{PFHE}$ satisfies _Definition 2.8_, for any PPTn
adversaries $\mathcal{A}$,
$\lvert\Pr[\mathsf{Hyb}_{3}(\mathcal{A})=1]-\Pr[\mathsf{Hyb}_{4}(\mathcal{A})=1]\rvert\leq\mathsf{negl}(n)$
for some negiligble function $\mathsf{negl}$.

###### Proof.

Similar to Lemma 3.4, the only difference in $\mathcal{A}$’s views in
$\mathbf{Hybrid}_{3}$ and $\mathbf{Hybrid}_{4}$ is the way the challenger
generates
$(\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}})$ or $(\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\lceil\log n\rceil})$.
Recall that we have:
$\left\\{\mathsf{ct}\right\\}\approx_{({\mathcal{T}},\epsilon)}\mathcal{D}_{\widetilde{\mathsf{ct}}(\lambda)}$
from Definition 2.8. Therefore for any PPTn adversary $\mathcal{A}$, the
advantage of distinguishing
$(\widetilde{\mathsf{ct}_{1}},\widetilde{\mathsf{ct}_{2}},\cdots,$
$\widetilde{\mathsf{ct}_{\lceil\log n\rceil}})$ in $\mathbf{Hybrid}_{3}$ from
a ciphertext sequence
$(\mathsf{ct}_{1},\mathsf{ct}_{2},\cdots,\mathsf{ct}_{\lceil\log n\rceil})$
where each
$\mathsf{ct}_{i}\leftarrow\mathsf{PFHE}.\mathsf{Enc}(\mathsf{pk},m_{i})$ is at
most $\lceil\log n\rceil\cdot\epsilon(\lambda)=\mathsf{negl}(n)$. Thus
$\mathcal{A}$ cannot distinguish between $\mathbf{Hybrid}_{3}$ and
$\mathbf{Hybrid}_{4}$ with non-negligible advantage, as otherwise either the
pseudorandom-$\mathsf{ct}$ property in Definition 2.8 would be broken.

∎

Now that we have related the success probability between the above consecutive
hybrid experiments, we will show next that
$\Pr[\mathsf{Hyb}_{4}(\mathcal{A})=1]=0$.

######  Lemma 3.6.

Given that $\mathsf{PFHE}$ satisfies _Definition 2.8_, for any PPTn
adversaries $\mathcal{A}$, $\Pr[\mathsf{Hyb}_{4}(\mathcal{A})=1]=0$.

###### Proof.

As in the proof for Claim 3.1, if $\mathsf{Hyb}_{4}(\mathcal{A})=1$, at some
time $t$ we must have $r_{t}=\bm{x^{\prime}}\neq\bm{x}$. Additionally, we
have:

  * ·

$\bm{x^{\prime}}_{m}\neq\bm{x}_{m}$, which is among the condition of
$\mathsf{Hyb}_{4}(\mathcal{A})=1$, and

  * ·

$hash=sketch$, which is verified in $\mathsf{StreamAlg}.\mathsf{Report}$.

Recall the $\mathsf{StreamAlg}$ scheme computes
$hash:=\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\cdot\bm{x^{\prime}}_{i}$ and
$sketch:=\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\cdot\bm{x}_{i}$, where
$\widehat{\mathsf{ct}_{i}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\mathsf{pk},C_{i},\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\lceil\log
n\rceil}),\hskip 3.00003pt\text{for }\hskip 3.00003ptC_{i}(\mu)=1$ iff
$\mu=i$. Therefore, given that
$(\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\lceil\log n\rceil})$ encrypts $m$ in
$\mathbf{Hybrid}_{4}$, $\widehat{\mathsf{ct}_{m}}$ should encode $1$, and
$\widehat{\mathsf{ct}_{i}}$ encodes $0$ for all $i\neq m$. Thus by the linear
homomorphism property of $\mathsf{PFHE}$, there exists a deterministic
decoding algorithm such that $hash$ decodes to $\bm{x}^{\prime}_{m}$ and
$sketch$ decodes to $\bm{x}_{m}$. However, since
$\bm{x^{\prime}}_{m}\neq\bm{x}_{m}$, this essentially implies $hash\neq
sketch$, contradicting the condition in $\mathsf{StreamAlg}.\mathsf{Report}$.

∎

Finally, summarizing Lemma 3.2 to Lemma 3.6:

  1. 1.

$\lvert\Pr[\mathsf{Hyb}_{0}(\mathcal{A})=1]-\Pr[\mathsf{Hyb}_{1}(\mathcal{A})=1]\rvert=0$

  2. 2.

$\Pr[\mathsf{Hyb}_{2}(\mathcal{A})=1]\geq\Pr[\mathsf{Hyb}_{1}(\mathcal{A})=1]/n$

  3. 3.

$\lvert\Pr[\mathsf{Hyb}_{2}(\mathcal{A})=1]-\Pr[\mathsf{Hyb}_{3}(\mathcal{A})=1]\rvert=\mathsf{negl}(n)$

  4. 4.

$\lvert\Pr[\mathsf{Hyb}_{3}(\mathcal{A})=1]-\Pr[\mathsf{Hyb}_{4}(\mathcal{A})=1]\rvert=\mathsf{negl}(n)$

  5. 5.

$\Pr[\mathsf{Hyb}_{4}(\mathcal{A})=1]=0$

We have that for any adversaries $\mathcal{A}$,
$\Pr[\mathsf{Hyb}_{0}(\mathcal{A})=1]\leq\mathsf{negl}(n)\cdot
n=\mathsf{negl}(n).$ i.e., The real WAR game between $\mathcal{A}$ and a
challenger running the $\mathsf{StreamAlg}$ scheme from Construction 3.1
outputs $1$ with probability at most $\mathsf{negl}(n)$.

∎

##  4 Efficiency

In this section, we discuss the space and time complexity of Construction 3.1.
We start by instantiating $\mathsf{StreamAlg}_{0}$ and $\mathsf{PFHE}$ used in
our construction.

###  4.1 Deterministic Relaxed Sparse Recovery

There exist space- and time-efficient streaming algorithms for the relaxed
$k$-sparse recovery problems. Given a sparse vector $\bm{x}\in\mathbb{Z}^{n}$,
many of these algorithms perform some linear measurement
$\Phi:\mathbb{Z}^{n}\to\mathbb{Z}^{r}$ on $\bm{x}$ with $r\ll n$ to get a
compressed representation $\Phi(\bm{x})$, which is often referred to as a
sketch of $\bm{x}$. This sketch is later used to reconstruct $\bm{x}$. The
linearity property is useful for incrementally maintaining the sketch during
the stream. Many algorithms implement the above specification using a random
measurement matrix $\Phi$. However, in our attempt to remove the random oracle
assumption within sub-linear total space, we cannot afford to store an
$n$-column random matrix during the stream. Instead, we use algorithms which
are deterministic, such that the measurements themselves incur no space
overhead.

######  Theorem 4.1 ([GLPS17]).

There exists a streaming algorithm $\mathsf{StreamAlg}_{0}$ for the Relaxed
$k$-Sparse Recovery problem, such that given an input parameter $n$, for an
integer stream with entries bounded by $\operatorname{\mathsf{poly}}(n)$:

  * ·

$\mathsf{StreamAlg}_{0}.\mathsf{Setup},\mathsf{Update}$, and $\mathsf{Report}$
are all deterministic.

  * ·

$\mathsf{StreamAlg}_{0}$ takes $\widetilde{\mathcal{O}}(k)$ bits of space.

  * ·

$\mathsf{StreamAlg}_{0}.\mathsf{Update}$ runs in $\widetilde{\mathcal{O}}(1)$.

  * ·

$\mathsf{StreamAlg}_{0}.\mathsf{Report}$ runs in
$\widetilde{\mathcal{O}}(k^{1+c})$ for an arbitrarily small constant $c>0$.

The deterministic Relaxed k-Sparse Recovery algorithm in Theorem 4.1 achieves
nearly optimal space and time. However, the measurement is “constructed” non-
explicitly using the probabilistic method. For explicit construction, we
consider the following result:

######  Theorem 4.2 ([Jaf11]).

There exists a streaming algorithm $\mathsf{StreamAlg}_{0}$ for $k$-Sparse
Recovery without Detection, such that given an input parameter $n$, for an
integer stream with entries bounded by $\operatorname{\mathsf{poly}}(n)$:

  * ·

$\mathsf{StreamAlg}_{0}.\mathsf{Setup},\mathsf{Update}$, and $\mathsf{Report}$
are all deterministic.

  * ·

$\mathsf{StreamAlg}_{0}$ takes $\widetilde{\mathcal{O}}(k)$ bits of space.

  * ·

$\mathsf{StreamAlg}_{0}.\mathsf{Update}$ runs in (amortized)
$\widetilde{\mathcal{O}}(1)$.

  * ·

$\mathsf{StreamAlg}_{0}.\mathsf{Report}$ runs in
$\widetilde{\mathcal{O}}(k^{2})$.

The above theorem except the amortized runtime has been shown in [Jaf11].

###### Proof (of the runtime in Theorem 4.2).

The measurement $\Phi$ in Theorem 4.2 is a $2k\times n$ Vandermonde matrix
explicitly defined 222For our discussion, we choose a Vandermonde matrix that
is easy to describe. Though many other Vandermonde matrices also satisfy the
specifications. as $\Phi_{i,j}=j^{i-1}$ over $\mathbb{Z}_{p}$, where $p>2M$ is
a large enough prime for $M\in\operatorname{\mathsf{poly}}(n)$ being the bound
on the magnitude of the stream entries. The reconstruction algorithm uses the
same idea as the algebraic algorithm for decoding Reed-Solomon codes. It uses
the sketch to construct an error-locator polynomial; the roots of this
polynomial identify the signals appearing in the sparse superposition.

We note that the Vandermonde matrix is dense but structured. Thus to achieve
the claimed $\widetilde{\mathcal{O}}(1)$ update time, we buffer every $2k$
stream updates and then efficiently process them in one batch. We need the
following result for fast multi-point evaluation of polynomials and the
Transposition Principle:

######  Theorem 4.3 ([vzGG13]).

Let $R$ be a ring, and let $q\in R[x]$ be a degree-$d$ polynomial. Then given
at most $d$ distinct points $x_{1},\cdots,x_{d}\in R$, all values
$q(x_{1}),\cdots,q(x_{d})$ can be computed using
$\mathcal{O}(d\log^{2}d\log\log d)$ total operations over $R$.

######  Theorem 4.4 (Transposition Principle, [Sho94]).

Let $K$ be a field and $\mathbf{A}$ be an $r\times w$ matrix over $K$. Suppose
there exists an arithmetic circuit of size $s$ that can compute
$\mathbf{A}\bm{y}$ for arbitrary length-$w$ vector $\bm{y}$ over $K$. Then
there exists an $\mathcal{O}(s)$-time algorithm that transforms this circuit
to compute $\mathbf{A^{\top}}\bm{x}$ for arbitrary length-$r$ vector $\bm{x}$
over $K$, with the size of the new circuit in ${\mathcal{O}}(s)$.

Theorem 4.3 and Theorem 4.4 together show the following update time for
Vandermonde measurements:

######  Proposition 4.1.

Suppose $\Phi$ is a $2k\times n$ Vandermonde matrix as described above. Let
$x_{1},x_{2},\cdots,x_{2k}$ be a sequence of updates with
$x_{t}:=(i_{t},\Delta_{t})$ for each $t\in[2k]$. Define
$\bm{v}=\sum_{t\in[2k]}\bm{b}_{i_{t}}\cdot\Delta_{t}$, then $\Phi(\bm{v})$ can
be computed using $\widetilde{\mathcal{O}}(k)$ time.

###### Proof (of Proposition 4.1).

Without loss of generality, we assume all updated coordinates
$i_{1},i_{2},\cdots,$ $i_{2k}$ are distinct, as one can always compress
multiple updates to the same coordinate as a single update. Then
$i_{1},i_{2},\cdots,i_{2k}$ index $2k$ columns of $\Phi$ and $2k$ coordinates
of $\bm{v}$ (which are the only coordinates that can possibly be non-zero).
Let $\mathbf{A}$ be the indexed $2k\times 2k$ column sub-matrix and
$\bm{v^{\prime}}$ be the $2k$-length vector containing only
$i_{1},i_{2},\cdots,i_{2k}$-th entries of $\bm{v}$ in their original order. We
have $\Phi\bm{v}=\mathbf{A}\bm{v^{\prime}}$.

Observe that the column submatrix $\mathbf{A}$ is still a Vandermonde matrix,
and each row $i$ of $\mathbf{A}^{\top}$ takes the form
$[1,\alpha_{i},\alpha_{i}^{2},\cdots,\alpha_{i}^{2k-1}]$ for some
$\alpha_{i}\in[n]$. For an arbitrary vector $u\in\mathbb{Z}_{p}^{2k}$, we
interpret it as the coefficient vector of a degree-$2k$ polynomial in
$\mathbb{Z}_{p}^{2k}$. Then $\mathbf{A}^{\top}\bm{u}$ can be computed as
evaluating the polynomial at $2k$ points
$\alpha_{1},\alpha_{2},\cdots\alpha_{2k}$, which takes
$\widetilde{\mathcal{O}}(k)$ time using the fast multi-point evaluation in
Theorem 4.1. By the Transposition Principle, this implies asymptotically the
same runtime for evaluating $\mathbf{A}\bm{v^{\prime}}$ thus $\Phi\bm{v}$. ∎

Therefore, once we buffer the updates into $2k$-sized batches and amortize the
cost of processing each batch to the future $2k$ updates, we get
$\widetilde{\mathcal{O}}(1)$ amortized runtime for
$\mathsf{StreamAlg}_{0}.\mathsf{Update}$.

∎

###  4.2 Pseudorandom FHE

We focus on GSW [GSW13], a standard LWE based fully homomorphic encryption
scheme, for our instantiation. To start with, we briefly review the
construction of GSW. We omit $\mathsf{Dec}$ since it is not involved in our
scheme. Instead, we will describe a decoding algorithm $\mathsf{LinearDec}$
for linear combinations of ciphertexts (which largely resembles the original
$\mathsf{Dec}$ of GSW) when showing the $\mathbb{Z}$ Linear Homomorphism
property of GSW.

  * •

$\mathsf{Setup}(1^{\lambda})$: Choose a modulus $q$, a lattice dimension
parameter $g$, and error distribution $\chi$ parametrized by $\lambda$. Also,
choose some $h=\Theta(g\log q)$. Let $params=(g,h,q,\chi)$ be parameters for
$\mathsf{LWE}_{g,h,q,\chi}$ .

  * •

$\mathsf{SecretKeyGen}(params)$: Sample
$\overline{\bm{s}}\leftarrow\mathbb{Z}_{q}^{g}$. Output
$\mathsf{sk}=\bm{s}^{\top}=[-\overline{\bm{s}}^{\top}\mid 1]$.

  * •

$\mathsf{PublicKeyGen}(params,\mathsf{sk})$: Sample a matrix
$\overline{\mathbf{A}}\leftarrow\mathbb{Z}^{g\times h}_{q}$ uniformly and an
error vector $\bm{e}\leftarrow\chi^{h}$. Let
$\bm{\alpha}=\overline{\bm{s}}^{\top}\cdot\overline{\mathbf{A}}+\bm{e}^{\top}$.
Set $\mathsf{pk}=\mathbf{A}$ to be the $(g+1)$-row matrix consisting of $g$
rows of $\overline{\mathbf{A}}$ followed by $\bm{\alpha}$.

  * •

$\mathsf{Enc}(params,\mathsf{pk},\mu)$: Sample a uniform matrix
$\mathbf{R}\leftarrow\\{0,1\\}^{h\times h}$. For $\mathsf{pk}=\mathbf{A}$,
output $\mathbf{A}\cdot\mathbf{R}+\mu\cdot\mathbf{G}$ where $\mathbf{G}$ is a
gadget matrix.

We assume that our set of LWE parameters $params$ is
$({\mathcal{T}},\epsilon)$-secure, such that for any ${\mathcal{T}}(\lambda)$
time adversary, the advantage of distinguishing an LWE sample from a uniformly
random sample is at most $\epsilon(\lambda)$. We now verify that GSW satisfies
the additional properties required by $\mathsf{PFHE}$.

#### GSW Satisfies $\mathsf{PFHE}$ Properties.

  * -

$\mathsf{Eval}$ is deterministic by the construction of GSW.

  * -

(Pseudorandom $\mathsf{pk}$, $\mathsf{ct}$.) This is just the built-in
security of GSW shown via the LWE hardness and the Left-over Hash lemma.
Assuming the $({\mathcal{T}},\epsilon)$-hardness of
$\mathsf{LWE}_{g,h,q,\chi}$, we have:

$\left\\{(\mathbf{A},\mathbf{A}\cdot\mathbf{R}+\mu\cdot\mathbf{G}):\begin{aligned}
\mathbf{A}&\leftarrow\mathsf{PublicKeyGen}\\\
\mathbf{R}&\leftarrow\\{0,1\\}^{h\times h}\\\
\mu&\in\\{0,1\\}\end{aligned}\right\\}\approx_{({\mathcal{T}},\epsilon)}\left\\{(\mathbf{U}_{1},\mathbf{U}_{2}):\begin{aligned}
\mathbf{U}_{1}&\leftarrow\mathbb{Z}_{q}^{(g+1)\times h}\\\
\mathbf{U}_{2}&\leftarrow\mathbb{Z}_{q}^{(g+1)\times
h}\end{aligned}\right\\}.$

  * -

($\mathbb{Z}$ Linear Homomorphism.) Consider the following arbitrary linear
combination, where each ciphertext
$\mathsf{ct}_{i}=\mathbf{A}\cdot\mathbf{R}_{i}+\mu_{i}\cdot\mathbf{G}$ for
$i\in[k]$:

${\mathcal{M}}=\sum_{i\in[k]}x_{i}\cdot\mathsf{ct}_{i}=\mathbf{A}\cdot(\sum_{i\in[k]}x_{i}\mathbf{R}_{i})+(\sum_{i\in[k]}x_{i}\mu_{i})\cdot\mathbf{G}$

For $k\cdot\max_{i\in[k]}x_{i}\ll q$ , it can be deterministically decrypted
using the normal GSW decryption for integer messages. For completeness, we
briefly describe $\mathsf{LinearDec}$ as follows:

    * –

$\mathsf{LinearDec}(\mathsf{pk},\mathsf{sk},{\mathcal{M}})$: Compute

$\displaystyle\mathsf{sk}\cdot{\mathcal{M}}$
$\displaystyle=[-\overline{\bm{s}}^{\top}\mid
1]\cdot\mathbf{A}\cdot(\sum_{i\in[k]}x_{i}\mathbf{R}_{i})+(\sum_{i\in[k]}x_{i}\mu_{i})\cdot[-\overline{\bm{s}}^{\top}\mid
1]\cdot\mathbf{G}$
$\displaystyle=\bm{e}^{\top}\cdot(\sum_{i\in[k]}x_{i}\mathbf{R}_{i})+(\sum_{i\in[k]}x_{i}\mu_{i})\cdot[-\overline{\bm{s}}^{\top}\mid
1]\cdot\mathbf{G}$
$\displaystyle\approx(\sum_{i\in[k]}x_{i}\mu_{i})\cdot[-\overline{\bm{s}}^{\top}\mid
1]\cdot\mathbf{G}$

Since it is easy to solve LWE with respect to $\mathbf{G}$, we can recover
$(\sum_{i\in[k]}x_{i}\mu_{i})\cdot[-\overline{\bm{s}}^{\top}\mid 1]$ and hence
$\sum_{i\in[k]}x_{i}\mu_{i}$ (modulo q).

#### Efficiency Based on Subexponential LWE.

We choose the lattice dimension parameter $g=\lambda$, the modulus $q$ and the
noise $\sigma$ with subexponential modulus-to-noise ratio, and the sample
complexity $h\in\Theta(g\cdot\log q)$. The subexponential hardness of LWE
requires the below indistinguishability to hold for adversaries of size
${\mathcal{T}}(\lambda)=2^{\lambda^{\beta}}$ for some constant $\beta>0$, with
subexponentially small distinguishing advantage
$\epsilon(\lambda)=2^{-\lambda^{c}}$ for some constant $c>0$ denoted by
$\approx_{\epsilon}$:

$\left\\{\begin{aligned} (\mathbf{A},\bm{s}\cdot\mathbf{A}+\bm{e})&\mod q:\\\
\mathbf{A}&\leftarrow\mathbb{Z}^{g\times h}_{q}\\\
\bm{s}&\leftarrow\mathbb{Z}^{1\times g}_{q}\\\ \bm{e}&\leftarrow\chi^{1\times
h}_{\sigma}\end{aligned}\right\\}\approx_{\epsilon}\left\\{(\mathbf{A},\bm{u}):\begin{aligned}
\mathbf{A}&\leftarrow\mathbb{Z}^{g\times h}_{q}\\\
\bm{u}&\leftarrow\mathbb{Z}^{1\times g}_{q}\\\ \end{aligned}\right\\}$

We set the security parameter be $\lambda=\log^{r}n$ for some constant
$r>1/\beta$ and $r>1/c$. This satisfies the relationship between functions
required by the Robustness Theorem 3.1: ${\mathcal{T}}(\log^{r}n)=2^{{(\log
n)^{r\beta}}}=\Omega(\operatorname{\mathsf{poly}}n)$ and
$\epsilon(\log^{r}n)=2^{{-(\log n)^{rc}}}\leq\mathsf{negl}(n)$ for some
negligible functions $\mathsf{negl}$.

Given these parameters, using GSW to implement $\mathsf{PFHE}$ and Theorem 4.1
to implement $\mathsf{StreamAlg}_{0}$, we get the following result:

######  Proposition 4.2.

Let ${\mathcal{R}}(\mathcal{A})$ denote the runtime of an algorithm
$\mathcal{A}$. Assuming the above subexponential hardness of LWE, we have the
following complexity regarding $\mathsf{StreamAlg}$ in Construction 3.1:

  1. 1.

$(\widetilde{\mathsf{pk}},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}})$ and $sketch$ can be stored using $\widetilde{\mathcal{O}}(1)$
total bits of space.

  2. 2.

${\mathcal{R}}(\mathsf{StreamAlg}.\mathsf{Update})=\widetilde{\mathcal{O}}(1)+{\mathcal{R}}(\mathsf{StreamAlg}_{0}.\mathsf{Update})$.

  3. 3.

${\mathcal{R}}(\mathsf{StreamAlg}.\mathsf{Report})=\widetilde{\mathcal{O}}(k)+{\mathcal{R}}(\mathsf{StreamAlg}_{0}.\mathsf{Report})$.

###### Proof.

Recall that computations in $\mathsf{StreamAlg}$ are modulo $q$ with
$q\in\operatorname{\mathsf{poly}}(n)$ and $q\gg n\cdot N$, where
$N\in\operatorname{\mathsf{poly}}(n)$ is the bound of the stream. Thus all
entries have bit complexity in ${\mathcal{O}}(\log n)$.

  1. 1.

$\widetilde{\mathsf{pk}},sketch$, and $\widetilde{\mathsf{ct}}_{i}$ for
$i\in\lceil\log n\rceil$ are all ${\mathcal{O}}(g)\times{\mathcal{O}}(h)$
matrices over $\mathbb{Z}_{q}$. For
$g=\lambda\in\operatorname{\mathsf{poly}}(\log n)$ and $h\in\Theta(g\cdot\log
q)$, they can be stored using ${\mathcal{O}}(\operatorname{\mathsf{poly}}(\log
n))=\widetilde{\mathcal{O}}(1)$ total bits of space.

  2. 2.

The second bullet point considers the following operation:

     * •

Evaluate
$\widehat{\mathsf{ct}_{i_{t}}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\widetilde{\mathsf{pk}},C_{i_{t}},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\ell}})$.
Then update $sketch$ as $sketch\leftarrow
sketch+\Delta_{t}\cdot\widehat{\mathsf{ct}_{i_{t}}}$.

Updating $sketch$ takes $\widetilde{\mathcal{O}}(1)$ time. For evaluation,
recall that $C_{i_{t}}$ is a point function checking whether the input bits
equal $i_{t}$. This can be naively implemented using ${\mathcal{O}}(\log n)$
arithmetic operations, each of which runs in $\operatorname{\mathsf{poly}}\log
n$ time as described in $\mathsf{Eval}_{+}$ and $\mathsf{Eval}_{\times}$
above. Thus the total runtime is $\widetilde{\mathcal{O}}(1)$.

  3. 3.

The third bullet point considers the following operation:

     * •

(If $\lVert\bm{x}^{\prime}\rVert_{0}>k$, output $\bot$. Otherwise:) Evaluate
$\widehat{\mathsf{ct}_{i}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\widetilde{\mathsf{pk}},C_{i},\widetilde{\mathsf{ct}_{1}},$
$\cdots,\widetilde{\mathsf{ct}_{\ell}})$ for $i\in[n]$. Then compute
$hash\leftarrow\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\cdot\bm{x^{\prime}}_{i}$.

Observe that although the construction is described as evaluating $n$-many
$\widehat{\mathsf{ct}_{i}}$, one for each coordinate of $\bm{x}^{\prime}$, at
this line of the algorithm $\bm{x}^{\prime}$ is guaranteed to have at most $k$
non-zero entries. Thus $k$ evaluations (corresponding to non-zero coordinates
of $\bm{x}^{\prime}$) suffice for computing the linear combination $hash$.
Each evaluation is $\widetilde{\mathcal{O}}(1)$, so the total runtime is
$\widetilde{\mathcal{O}}(k)$.

∎

#### Efficiency of $\mathsf{PFHE}$ Based on Polynomial LWE.

Under the polynomial LWE assumption, we set $\lambda=n^{w}$ for an arbitrarily
small constant $w>0$. The $({\mathcal{T}},\epsilon)$-security then reduces to
the standard definition in terms of PPT adversaries and negligible advantage.
We again choose $g=\lambda$ and $h\in\Theta(g\cdot\log q)$. The complexity is:

######  Proposition 4.3.

Let ${\mathcal{R}}(\mathcal{A})$ denote the runtime of an algorithm
$\mathcal{A}$. Assuming the polynomial hardness of LWE, we have the following
complexity regarding $\mathsf{StreamAlg}$ in Construction 3.1:

  1. 1.

$(\widetilde{\mathsf{pk}},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}})$ and $sketch$ can be stored in $\widetilde{\mathcal{O}}(n^{w_{1}})$
bits of space.

  2. 2.

${\mathcal{R}}(\mathsf{StreamAlg}.\mathsf{Update})=\widetilde{\mathcal{O}}(n^{w_{2}})+{\mathcal{R}}(\mathsf{StreamAlg}_{0}.\mathsf{Update})$.

  3. 3.

${\mathcal{R}}(\mathsf{StreamAlg}.\mathsf{Report})=\widetilde{\mathcal{O}}(k\cdot
n^{w_{3}})+{\mathcal{R}}(\mathsf{StreamAlg}_{0}.\mathsf{Report})$.

where $w_{1},w_{2}$, and $w_{3}$ are arbitrarily small positive constants.

###### Proof.

The proof is exactly the same as the proof for Proposition 4.2, except that
now the dimension of the ciphertext matrices blows up from
$\operatorname{\mathsf{poly}}\log n$ to $n^{w}$ for an arbitrarily small
$w>0$.

∎

###  4.3 Complexity of Construction 3.1

Putting together Sections 4.1 and 4.2, we summarize the complexity of our
construction in Table 2 below.

Table 2: A summary of the time and space complexities of the $\mathsf{StreamAlg}$ scheme in Construction 3.1, given different instantiations of $\mathsf{StreamAlg}_{0}$ and $\mathsf{PFHE}$. $c$ denotes an arbitrarily small positive constant. Relaxed Rec. Scheme | LWE Assumption | Space | Update Time | Report Time
---|---|---|---|---
Theorem 4.1 | subexp | $\widetilde{\mathcal{O}}(k)$ | $\widetilde{\mathcal{O}}(1)$ | $\widetilde{\mathcal{O}}(k^{1+c})$
Theorem 4.2 | subexp | $\widetilde{\mathcal{O}}(k)$ | $\widetilde{\mathcal{O}}(1)$ | $\widetilde{\mathcal{O}}(k^{2})$
Theorem 4.1 | poly | $\widetilde{\mathcal{O}}(k+n^{c})$ | $\widetilde{\mathcal{O}}(n^{c})$ | $\widetilde{\mathcal{O}}(k\cdot(k^{c}+n^{c}))$
Theorem 4.2 | poly | $\widetilde{\mathcal{O}}(k+n^{c})$ | $\widetilde{\mathcal{O}}(n^{c})$ | $\widetilde{\mathcal{O}}(k\cdot(k+n^{c}))$

##  5 Distributed $K$-Sparse Recovery from Ring LWE

###  5.1 Distributed Computation

In the distributed computation model, the dataset is split over multiple
servers. The goal is to design a communication protocol for servers to
collectively compute a function on the aggregated dataset. In this work, we
consider the message-passing coordinator model (see, e.g., [PVZ15]), where
there are $T$ servers and a single central coordinator. Each server
$s_{t}:t\in[T]$ receives a partition of data in the form of an $n$-dimensional
vector $\bm{x}_{t}$, and communicates with the central coordinator through a
two-way, single-round communication channel. At the end of the communication,
the coordinator needs to compute or approximate a function $f_{n}(\bm{x})$ of
the aggregated vector $\bm{x}=\sum_{t\in[T]}\bm{x}_{t}$. We aim to design
protocols that minimize the total amount of communication through the channel
and speed up the computation at each server and the coordinator. See also
[WZ12] and the references therein on the distributed model.

Similar to the streaming model, we focus on designing a robust protocol in a
white-box adversarial distributed setting, where the dataset is generated and
partitioned across each server by a white-box adversary who monitors the
internal state of the coordinator and the servers. We define the model as
follows:

######  Definition 5.1 (Distributed Protocol).

Given a query function ensemble $\mathcal{F}=\\{f_{n}:\mathbb{Z}^{n}\to
X\\}_{n\in\mathbb{N}}$ for some domain $X$, a distributed protocol
$\mathsf{DistProt}$ that computes $\mathcal{F}$ contains a tuple of algorithms
$\mathsf{DistProt}=(\mathsf{DistProt}.\mathsf{Setup},$
$\mathsf{DistProt}.\mathsf{Server},\mathsf{DistProt}.\mathsf{Coordinator})$,
with the following properties:

  * •

$\mathsf{DistProt}.\mathsf{Setup}(n,\rho_{0})\to\zeta$ : On input a parameter
$n$, the coordinator samples randomness $\rho_{0}$ and uses $\rho_{0}$ to
compute some state $\zeta$. It sends $\zeta$ to all servers.

  * •

$\mathsf{DistProt}.\mathsf{Server}(\zeta,\bm{x}_{t},\rho_{t})\to p_{t}$ : On
input a state $\zeta$ and a data partition $\bm{x}_{t}\in\mathbb{Z}^{n}$, the
$t$-th server samples randomness $\rho_{t}$ and uses it to compute a packet
$p_{t}$. It sends $p_{t}$ back to the coordinator.

  * •

$\mathsf{DistProt}.\mathsf{Coordinator}(p_{1},\cdots,p_{T},\rho_{c})\to r$: On
input $T$ packets $p_{1},\cdots,p_{T}$, the coordinator samples randomness
$\rho_{c}$ and computes a query response $r\in X$.

A response $r$ is said to be correct if $r=f_{n}(\bm{x})$ where
$\bm{x}=\sum_{t\in[T]}\bm{x}_{t}$.

As in the streaming setting, we again assume bounded integer inputs, such that
an arbitrary subset sum of $\\{\bm{x}_{t}:t\in[T]\\}$ is in $[-N,N]^{n}$ for
some $N\in\operatorname{\mathsf{poly}}(n)$.

######  Definition 5.2.

We say that a distributed protocol $\mathsf{DistProt}$ is white-box
adversarially robust if for all dimension parameters $n\in\mathbb{N}$, the
following holds: For any PPT adversary $\mathcal{A}$, the following experiment
$\mathsf{Expt}_{\mathcal{A},\mathsf{DistProt}}(n)$ outputs $1$ with
probability at most $\mathsf{negl}(n)$:

$\mathsf{Expt}_{\mathcal{A},\mathsf{DistProt}}(n):$

  1. 1.

The challenger and $\mathcal{A}$ agree on a query function ensemble
$\mathcal{F}=\\{f_{n}:\mathbb{Z}^{n}\to X\\}_{n\in\mathbb{N}}$ for some domain
$X$. On input a dimension parameter $n$, let $f_{n}\in\mathcal{F}$ be the
query function of the experiment.

  2. 2.

The challenger samples all randomness $\rho_{0}$, $\rho_{t}:t\in[T]$, and
$\rho_{c}$ for the servers and the coordinator. It then provides
$\rho_{0},\rho_{1},\cdots,\rho_{T}$ and $\rho_{c}$ to $\mathcal{A}$.

  3. 3.

$\mathcal{A}$ generates $T$ partitions of data
$\bm{x}_{1},\cdots,\bm{x}_{T}\in\mathbb{Z}^{n}$ and provides them to the
challenger.

  4. 4.

The challenger executes the protocol to sequentially compute the following:

    1. (i)

$\zeta\leftarrow\mathsf{DistProt}.\mathsf{Setup}(n,\rho_{0})$.

    2. (ii)

$p_{t}\leftarrow\mathsf{DistProt}.\mathsf{Server}(\zeta,\bm{x}_{t},\rho_{t})$
for all $t\in[T]$.

    3. (iii)

$r\leftarrow\mathsf{DistProt}.\mathsf{Coordinator}(p_{1},\cdots,p_{T},\rho_{c})$.

  5. 5.

The experiment outputs $1$ if and only if at some time $r\neq f_{n}(\bm{x})$.

######  Remark 5.1.

We remark on the connection between the streaming model and the distributed
model. There exists a well-known reduction from a streaming algorithm to a
distributed protocol under the oblivious setting: Each server runs
$\mathsf{StreamAlg}.\mathsf{Update}$ on the same initial state
$\zeta\leftarrow\mathsf{StreamAlg}.\mathsf{Setup}$, using all entries of
$\bm{x}_{t}$ (its data partition) as updates. It then sends the resulting
sketch to the coordinator. As long as the sketches are linear, the coordinator
can run $\mathsf{StreamAlg}.\mathsf{Report}$ on the sum of all sketches to
compute a query response.

One may use the same recipe to construct a WAR distributed protocol from a WAR
streaming algorithm. In general, the robustness is retained by such a
reduction if $\mathsf{StreamAlg}.\mathsf{Update}$ and
$\mathsf{StreamAlg}.\mathsf{Report}$ are deterministic. (Otherwise, the
adversaries in the experiment $\mathsf{Expt}_{\mathcal{A},\mathsf{DistProt}}$
would have additional views to all “future” randomness, while adversaries in
the streaming experiment $\mathsf{Expt}_{\mathcal{A},\mathsf{StreamAlg}}$ only
monitor the past randomness already used by $\mathsf{StreamAlg}$.) Our
Construction 3.1 satisfies this condition.

###  5.2 Distributed Protocol Construction

For completeness, we briefly describe the distributed protocol for $k$-Sparse
Recovery as follows, which essentially follows the same route as our streaming
Construction 3.1.

######  Construction 5.1.

Similar to Construction 3.1, let $\mathsf{PFHE}$ be a pseudorandom
$\mathsf{FHE}$ scheme. And let $\mathsf{StreamAlg}_{0}$ be a streaming
algorithm for the Relaxed $k$-Sparse Recovery problem. We assume that
$\mathsf{StreamAlg}_{0}$ performs a deterministic linear measurement
$\Phi_{n}$ on an arbitrary length-$n$ input vector, as described in the
previous instantiation Section 4.1.

  * •

$\mathsf{DistProt}.\mathsf{Setup}(n)$ : Let $\lambda={\mathcal{S}}(n)$ be the
security parameter of $\mathsf{PFHE}$. Sample
$\widetilde{\mathsf{pk}}\leftarrow\mathcal{D}_{\widetilde{\mathsf{pk}}(\lambda)}$
and
$\widetilde{\mathsf{ct}_{1}},\widetilde{\mathsf{ct}_{2}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}}\leftarrow\mathcal{D}_{\widetilde{\mathsf{ct}}(\lambda)}$. Send
$\zeta:=(\widetilde{\mathsf{pk}},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\log
n}})$ to all servers

  * •

$\mathsf{DistProt}.\mathsf{Server}(\zeta,\bm{x_{t}})$ : Given
$\zeta:=(\widetilde{\mathsf{pk}},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}})$, evaluate $\widehat{\mathsf{ct}_{i}}\leftarrow\mathsf{PFHE}.$
$\mathsf{Eval}(\widetilde{\mathsf{pk}},C_{i},\widetilde{\mathsf{ct}_{1}},\cdots,$
$\widetilde{\mathsf{ct}_{\lceil\log n\rceil}})$ for $i\in[n]$, where $C_{i}$
is the same point function as in Construction 3.1.

Compute $\Phi_{n}(\bm{x_{t}})$ and
$sketch_{t}\leftarrow\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\cdot(\bm{x_{t}})_{i}$,
where $(\bm{x_{t}})_{i}$ denotes the $i$-th coordinate of $\bm{x_{t}}$. Send
$p_{t}:=(sketch_{t},\Phi_{n}(\bm{x_{t}}))$ to the coordinator.

  * •

$\mathsf{DistProt}.\mathsf{Coordinator}(p_{1},\cdots,p_{T})$: Let
$\bm{x}^{\prime}\leftarrow\mathsf{StreamAlg}_{0}.\mathsf{Report}(\sum_{t\in[T]}\Phi_{n}(\bm{x_{t}}))$,
i.e., the output of running the reconstruction algorithm of
$\mathsf{StreamAlg}_{0}$ on the sum of all measurement results. If
$\lVert\bm{x}^{\prime}\rVert_{0}>k$, output $\bot$.

Otherwise, evaluate
$\widehat{\mathsf{ct}_{i}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\widetilde{\mathsf{pk}},C_{i},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}})$ for $i\in[n]$. Then compute
$hash\leftarrow\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\cdot\bm{x^{\prime}}_{i}.$
Output $\bm{x}^{\prime}$ if $hash=\sum_{t\in[T]}sketch_{t}$, and output $\bot$
otherwise.

###  5.3 Efficiency

In this section, we focus on showing that we can use BV [BV11], a Ring-LWE
based $\mathsf{FHE}$ scheme, to achieve near-linear processing time on
$\mathsf{DistProt}.\mathsf{Server}$ under the polynomial ring-LWE assumption.

As a warm-up, we state the complexity of Constrution 5.1 using GSW to
implement $\mathsf{PFHE}$:

######  Proposition 5.1.

Let ${\mathcal{R}}(\mathcal{A})$ denote the runtime of an algorithm or an
evaluation $\mathcal{A}$, we have the following complexity regarding
$\mathsf{DistProt}$ in Construction 5.1:

  * •

Assuming the subexponential hardness of LWE:

    1. 1.

The total bits of communication between an arbitrary server and the
coordinator is $\widetilde{\mathcal{O}}(1)$ \+ $size(\Phi_{n}(\bm{x}))$.

    2. 2.

${\mathcal{R}}(\mathsf{DistProt}.\mathsf{Coordinator})=\widetilde{\mathcal{O}}(k)+{\mathcal{R}}(\mathsf{StreamAlg}_{0}.\mathsf{Report})$.

    3. 3.

${\mathcal{R}}(\mathsf{DistProt}.\mathsf{Server})=\widetilde{\mathcal{O}}(k)+{\mathcal{R}}(\Phi_{n}(\bm{x}))$.

  * •

Assuming the polynomial hardness of LWE: :

    1. 1.

The total bits of communication between an arbitrary server and the
coordinator is $\widetilde{\mathcal{O}}(n^{w_{1}})$ \+
$size(\Phi_{n}(\bm{x}))$.

    2. 2.

${\mathcal{R}}(\mathsf{DistProt}.\mathsf{Coordinator})=\widetilde{\mathcal{O}}(k\cdot
n^{w_{2}})+{\mathcal{R}}(\mathsf{StreamAlg}_{0}.\mathsf{Report})$.

    3. 3.

${\mathcal{R}}(\mathsf{DistProt}.\mathsf{Server})=\widetilde{\mathcal{O}}(k\cdot
n^{w_{3}})+{\mathcal{R}}(\Phi_{n}(\bm{x}))$.

where $\bm{x}\in[-N,N]^{n}$ is arbitrary, and $w_{1},w_{2},$ and $w_{3}$ are
arbitrarily small positive constants.

###### Proof.

The communication complexity and the runtime of
$\mathsf{DistProt}.\mathsf{Coordinator}$ are the same as the bit complexity
and reporting time of $\mathsf{StreamAlg}$ in Construction 3.1 (except for
some negligible addition operations). The runtime of
$\mathsf{DistProt}.\mathsf{Server}$ is roughly
$n\cdot{\mathcal{R}}(\mathsf{StreamAlg}.\mathsf{Update})$, because every
server has to perform $n$ evaluations, one for each coordinate of its data
partition.

∎

#### Efficiency Based on Ring-LWE.

Before discussing the efficiency advantage, we briefly review some important
features of BV to show that it satisfies a variant of the $\mathsf{PFHE}$
definition. See [BV11] for details of the BV construction.

Consider a ring $R:=\frac{\mathbb{Z}[x]}{x^{g}+1}$ where $g$ is the degree
parameter. Let $R_{q}$ denote $R/qR$ for a prime modulus $q$, and let $R_{t}$
be the message space for some prime $t\in\mathbb{Z}_{q}^{*}$ and $t\ll q/g$:

  * •

The public keys of BV are two-dimensional vectors in $R^{2}_{q}$, which are
computationally indistinguishable from uniformly random samples from
$R^{2}_{q}$ under the Ring-LWE assumption.

The ciphertexts are also vectors over $R_{q}$ that are indistinguishable from
uniform random.

  * •

BV satisfies an analogy of $\mathbb{Z}$ Linear Homomorphism, with coefficients
of linear combinations ${\mathcal{M}}=\sum_{i\in[k]}x_{i}\cdot\mathsf{ct}_{i}$
being small norm ring elements $x_{i}\in R_{t}$ as opposed to integer scalars.
As long as the linear combination of corresponding messages
(${\mathcal{M}}_{msg}=\sum_{i\in[k]}x_{i}\cdot m_{i}$, where $m_{i}\in R_{t}$
is the message encrypted by $\mathsf{ct}_{i}$) still lies in $R_{t}$, running
the standard BV decoding algorithm on ${\mathcal{M}}$ output the correct
message.

  * •

$\mathsf{Eval}$ and $\mathsf{Dec}$ are deterministic by the construction of
BV.

We choose parameters for our Ring-LWE based construction as follows: Let
$\lambda=n^{w}$ for an arbitrarily small constant $w>0$. Let the dimension
$g=\lambda$, the modulus of the message space $t>n\cdot N$, where
$N\in\operatorname{\mathsf{poly}}(n)$ is the bound of the input data. The
modulus $q$ is chosen with subexponential modulus-to-noise ratio and $q\gg
g\cdot t$ the Ring-LWE assumption states that for any
$h\in\operatorname{\mathsf{poly}}(\lambda)$, it holds that

$\left\\{(a_{i},a_{i}\cdot
s+e_{i}):e_{i}\leftarrow\chi\right\\}_{i\in[h]}\approx_{c}\left\\{(a_{i},u_{i}):\begin{aligned}
u_{i}&\leftarrow R_{q}\\\ \end{aligned}\right\\}_{i\in[h]}$

where $s$ is sampled from the noise distribution $\chi$ and $a_{i}$ are
uniform in $R_{q}$.

We have the following complexity:

######  Proposition 5.2.

Let ${\mathcal{R}}(\mathcal{A})$ denote the runtime of an algorithm or an
evaluation $\mathcal{A}$. Assuming the polynomial hardness of Ring-LWE, a
variant of $\mathsf{DistProt}$ in Construction 5.1 has the following
complexity:

  1. 1.

The total bits of communication between an arbitrary server and the
coordinator is $\widetilde{\mathcal{O}}(n^{w_{1}})$ \+
$size(\Phi_{n}(\bm{x}))$.

  2. 2.

${\mathcal{R}}(\mathsf{DistProt}.\mathsf{Coordinator})=\widetilde{\mathcal{O}}(n)+{\mathcal{R}}(\mathsf{StreamAlg}_{0}.\mathsf{Report})$.

  3. 3.

${\mathcal{R}}(\mathsf{DistProt}.\mathsf{Server})=\widetilde{\mathcal{O}}(k\cdot
n^{w}_{2})+{\mathcal{R}}(\Phi_{n}(\bm{x}))$.

where $\bm{x}\in[-N,N]^{n}$ is arbitrary, and $w_{1},w_{2}$ are arbitrarily
small positive constants.

###### Proof.

In comparison to the complexity under polytime standard LWE, we save a
$n^{\Theta(1)}$ factor in the runtime of $\mathsf{DistProt}.\mathsf{Server}$.
This is due to speeding up the following two steps:

  1. 1.

Evaluate
$\widehat{\mathsf{ct}_{i}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\widetilde{\mathsf{pk}},C_{i},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}})$ for all $i\in[n]$

  2. 2.

Compute $\sum_{i\in[n]}\widehat{\mathsf{ct}_{i}}\cdot\bm{x}_{i}$

The idea is to represent the messages as ring elements over $R_{q}$ as opposed
to individual scalars, and apply fast Fourier transforms to efficiently
multiply them.

In a variant of Construction 5.1, instead of performing $n$ evaluations one
for each coordinate $i\in[n]$, we partition the dimension $n$ into $n^{1-w}$
chunks. Each chunk is of length $n^{w}$, where $g=n^{w}$ is the degree
parameter of the ring for an arbitrarily small constant $w>0$. Such that a
length-$n$ vector $\bm{x}$ is partitioned into $n^{1-w}$ consecutive segments,
each can be represented as a (small-normed in comparison to $q$) ring element
$x_{j}\in R_{q}$ for $j\in[n^{1-w}]$.

We also define a new set of functions $C_{j}^{\prime}$ as follows:

$C^{\prime}_{j}(\mu_{1},\cdots,\mu_{\lceil\log n\rceil})=$
$\begin{cases}1&\text{if $(\mu_{1},\cdots,\mu_{\lceil\log n\rceil})$
represents a value in $[jn^{w},(j+1)n^{w})$}\\\
0&\text{otherwise}.\end{cases}$

We evaluate
$\widehat{\mathsf{ct}_{j}^{\prime}}\leftarrow\mathsf{PFHE}.\mathsf{Eval}(\widetilde{\mathsf{pk}},C^{\prime}_{j},\widetilde{\mathsf{ct}_{1}},\cdots,\widetilde{\mathsf{ct}_{\lceil\log
n\rceil}})$ for all $j\in[n^{1-w}]$ to replace the above step 1. The total
evaluation time is ${\mathcal{O}}(n^{1-w}\cdot
n^{w}\operatorname{\mathsf{poly}}\log(n^{w}))=\widetilde{\mathcal{O}}(n)$,
since two ring elements can be multiplied in
${\mathcal{O}}(n^{w}\operatorname{\mathsf{poly}}\log(n^{w}))$ time using the
FFT. Then the linear combination in the above step 2 is replaced by
$\sum_{j\in[n^{1-w}]}\widehat{\mathsf{ct}^{\prime}_{j}}\cdot x_{j}$, which
similarly takes $\widetilde{\mathcal{O}}(n)$ time to compute.

Lastly, we check that given two vectors $\bm{x}$ and $\bm{x^{\prime}}$ differ
at a coordinate $m$, when $\mathsf{ct}_{1},\cdots,\mathsf{ct}_{\lceil\log
n\rceil}$ encrypt the bits of $m$, we still have

$sketch=\sum_{j\in[n^{1-w}]}\widehat{\mathsf{ct}^{\prime}_{j}}\cdot
x_{j}\neq\sum_{j\in[n^{1-w}]}\widehat{\mathsf{ct}^{\prime}_{j}}\cdot
x^{\prime}_{j}=hash.$

because they can be decrypted into distinct ring elements. This concludes that
the above variant of Construction 5.1 remains correct while achieving near-
linear runtime of $\mathsf{DistProt}.\mathsf{Coordinator}$ and
$\mathsf{DistProt}.\mathsf{Server}$.

∎

##  6 Low-Rank Matrix and Tensor Recovery

The low-rank matrix and tensor recovery problems are defined as follows:

######  Definition 6.1 (Rank-$k$ Matrix Recovery).

Given a rank parameter $k$ and an input matrix
$\mathbf{X}\in\mathbb{Z}^{n\times m}$, output $\mathbf{X}$ if
$rank(\mathbf{X})\leq k$ and report $\bot$ otherwise.

Let $\otimes$ denote the outer product of two vectors. We use the following
definition for tensor rank:

######  Definition 6.2 (CANDECOMP/PARAFAC (CP) rank).

For a tensor $X\in\mathbb{R}^{n^{d}}$, consider it to be the sum of $k$
rank-$1$ tensors: $X=\sum^{k}_{i=1}(x_{i1}\otimes x_{i2}\otimes\cdots\otimes
x_{id})$ where $x_{ij}\in\mathbb{R}^{n}$. The smallest number of rank-$1$
tensors that can be used to express a tensor $X$ is then defined to be the
rank of the tensor.

######  Definition 6.3 (Rank-$k$ Tensor Recovery).

Given a rank parameter $k$ and an input tensor
$\mathbf{X}\in\mathbb{Z}^{n^{d}}$, output $\mathbf{X}$ if $CP-
rank(\mathbf{X})\leq k$ and report $\bot$ otherwise.

The low-rank matrix and tensor recovery problems are natural generalizations
of the $k$-sparse vector recovery problems. Using the same framework as the
vector case, they can be solved by maintaining two hashes: one recovers the
matrix or tensor but potentially produces garbage output, and the other uses a
cryptographic tool to verify whether the output matches the input data. These
are natural generalizations of the $k$-sparse vector recovery problems.

In [FW23], the recovery hash is measured by a random Gaussian matrix, and the
verification hash is measured by an SIS matrix. Both measurements are assumed
to be heuristically compressed by an idealized hash function. We instead
replace the former with a deterministic measurement, which can be explicitly
constructed and decoded in polynomial time [FS12]. The latter is replaced by
the same FHE-based hashing as the one we used for the vector case in
Construction 3.1, which operates on the vectorization of the data matrix or
tensor. Similar to the vector case, our construction does not require using an
idealized hash function or storing a separate large state.

In the streaming model, the complexities of our matrix and tensor recovery
algorithms are as follows:

######  Proposition 6.1.

Let ${\mathcal{R}}(\mathcal{A})$ denote the runtime of an algorithm or an
evaluation $\mathcal{A}$. Assuming the polynomial hardness of LWE,

  * •

There exists a WAR streaming algorithm $\mathsf{StreamAlg}$ for the rank-$k$
matrix recovery problem using $\widetilde{\mathcal{O}}(nk)$ bits of space.

  * •

There exists a WAR streaming algorithm $\mathsf{StreamAlg}$ for the rank-$k$
tensor recovery problem using $\widetilde{\mathcal{O}}(nk^{\lceil\log
d\rceil})$ bits of space.

###### Proof.

The recovery scheme for matrices and tensors takes
$\widetilde{\mathcal{O}}(nk)$ and $\widetilde{\mathcal{O}}(nk^{\lceil\log
n\rceil})$ bits of space, respectively [FS12]. Under the polynomial hardness
assumption of LWE, we set $\lambda=n^{c}$ for an arbitrarily small positive
constant $c$. Taking the sum of the two terms produces the claimed
complexities. ∎

In addition, the above streaming algorithms can be converted into WAR
distributed protocols for matrix and vector recovery, following the same
roadmap as in Section 5.

######  Proposition 6.2.

Let ${\mathcal{R}}(\mathcal{A})$ denote the runtime of an algorithm or an
evaluation $\mathcal{A}$. Assuming the polynomial hardness of LWE: :

  * •

There exists a WAR distributed protocol $\mathsf{DistProt}$ for the rank-$k$
matrix recovery problem, using $\widetilde{\mathcal{O}}(nk)$ bits of
communication between each server and the coordinator, and
$\widetilde{\mathcal{O}}(n^{2}k)$ processing time at each server.

  * •

There exists a WAR streaming algorithm $\mathsf{StreamAlg}$ for the rank-$k$
tensor recovery problem, using $\widetilde{\mathcal{O}}(nk^{\lceil\log
d\rceil})$ bits of communication between each server and the coordinator.

###### Proof.

The total number of bits of communication between each server and the
coordinator equals the size of the state in the above streaming algorithms.
For low-rank matrix recovery, the deterministic scheme performs
$\widetilde{\mathcal{O}}(nk)$ measurements using $n$-sparse matrices, and the
runtime for computing the FHE-based hash is comparably small. This gives
$\widetilde{\mathcal{O}}(n^{2}k)$ processing time at each server. ∎

We remark that the rank-$k$ matrix recovery algorithm in the previous work
[FW23] requires $\widetilde{\mathcal{O}}(n^{3}k)$ processing time in the
distributed setting, which our construction improves upon.

## Acknowledgements

Aayush Jain was supported by a Google faculty research scholar award 2023.
David P. Woodruff was supported by a Simons Investigator Award and NSF Grant
No. CCF-2335412.

## References

  * [ABD+21] Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev.  Adversarial laws of large numbers and optimal regret in online classification.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 447–455, 2021.
  * [ABJ+22] Miklós Ajtai, Vladimir Braverman, T.S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou.  The white-box adversarial data stream model.  In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’22, pages 15–27, New York, NY, USA, 2022. Association for Computing Machinery.
  * [ABS23] A. Almeida, S. Brás, and et al. Sargento, S.  Time series big data: a survey on data stream frameworks, analysis and algorithms.  J Big Data, 2023.
  * [ACSS21] 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.
  * [AMS96] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 20–29, New York, NY, USA, 1996. Association for Computing Machinery.
  * [AR05] Dorit Aharonov and Oded Regev.  Lattice problems in np and conp.  J. ACM, 52:749–765, 2005.
  * [BEO22] Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak.  Adversarially robust streaming via dense-sparse trade-offs.  In 5th Symposium on Simplicity in Algorithms, SOSA, 2022.  (to appear).
  * [BGV12] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan.  (leveled) fully homomorphic encryption without bootstrapping.  In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 309–325, 2012.
  * [BHM+05] Paul Brown, Peter J. Haas, Jussi Myllymaki, Hamid Pirahesh, Berthold Reinwald, and Yannis Sismanis.  Toward automated large-scale information integration and discovery.  In Data Management in a Connected World, Essays Dedicated to Hartmut Wedekind on the Occasion of His 70th Birthday, pages 161–180, 2005.
  * [BHM+21] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou.  Adversarial robustness of streaming algorithms through importance sampling.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, 2021.  (to appear).
  * [BIR08] R. Berinde, P. Indyk, and M. Ruzic.  Practical near-optimal sparse recovery in the l1 norm.  In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pages 198–205, 2008.
  * [BJWY21] 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.
  * [BLV19] Elette Boyle, Rio LaVigne, and Vinod Vaikuntanathan.  Adversarially robust property-preserving hash functions.  In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 16:1–16:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [BV11] Zvika Brakerski and Vinod Vaikuntanathan.  Fully homomorphic encryption from ring-lwe and security for key dependent messages.  In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011, pages 505–524, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [BY20] Omri Ben-Eliezer and Eylon Yogev.  The adversarial robustness of sampling.  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 49–62, 2020.
  * [CCD+03] Sirish Chandrasekaran, Owen Cooper, Amol Deshpande, Michael J. Franklin, Joseph M. Hellerstein, Wei Hong, Sailesh Krishnamurthy, Samuel R. Madden, Fred Reiss, and Mehul A. Shah.  Telegraphcq: Continuous dataflow processing.  In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, SIGMOD ’03, page 668, New York, NY, USA, 2003. Association for Computing Machinery.
  * [CG08] Graham Cormode and Minos Garofalakis.  Streaming in a connected world: Querying and tracking distributed data streams.  In Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, EDBT ’08, page 745, New York, NY, USA, 2008. Association for Computing Machinery.
  * [CGS22] Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl.  Adversarially robust coloring for graph streams.  In 13th Innovations in Theoretical Computer Science Conference, ITCS, 2022.  (to appear).
  * [CH21] Timothy M. Chan and Qizheng He.  More dynamic data structures for geometric set cover with sublinear update time.  In 37th International Symposium on Computational Geometry, SoCG, pages 25:1–25:14, 2021.
  * [Cha10] Timothy M. Chan.  A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries.  J. ACM, 57(3):16:1–16:15, 2010.
  * [CJ19] Graham Cormode and Hossein Jowhari.  Lp samplers and their applications: A survey.  ACM Comput. Surv., 52(1), feb 2019.
  * [CM05] G. Cormode and S. Muthukrishnan.  What’s new: finding significant differences in network data streams.  IEEE/ACM Transactions on Networking, 13(6):1219–1232, 2005.
  * [CZM+18] Ekin Dogus Cubuk, Barret Zoph, Dandelion Mané, Vijay Vasudevan, and Quoc V. Le.  Autoaugment: Learning augmentation policies from data.  CoRR, abs/1805.09501, 2018.
  * [DJMS02] Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, and Vladislav Shkapenyuk.  Mining database structure; or, how to build a data quality browser.  In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pages 240–251, 2002.
  * [DSST89] James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan.  Making data structures persistent.  J. Comput. Syst. Sci., 38(1):86–124, 1989.
  * [FK03] Amos Fiat and Haim Kaplan.  Making data structures confluently persistent.  J. Algorithms, 48(1):16–58, 2003.
  * [FN85] Philippe Flajolet and G. Nigel Martin.  Probabilistic counting algorithms for data base applications.  Journal of Computer and System Sciences, 31(2):182–209, 1985.
  * [FS12] Michael A. Forbes and Amir Shpilka.  On identity testing of tensors, low-rank recovery and compressed sensing.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 163–172, New York, NY, USA, 2012. Association for Computing Machinery.
  * [FW23] Ying Feng and David P. Woodruff.  Improved algorithms for white-box adversarial streams.  In ICML, 2023.
  * [Gab07] Mohamed Medhat Gaber.  Data Stream Processing in Sensor Networks, pages 41–48.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2007.
  * [GG00] Oded Goldreich and Shafi Goldwasser.  On the limits of nonapproximability of lattice problems.  J. Comput. Syst. Sci., 60(3):540–563, 2000.
  * [GLPS17] Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss.  For-all sparse recovery in near-optimal time.  ACM Trans. Algorithms, 13(3), mar 2017.
  * [GSS14] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  CoRR, abs/1412.6572, 2014.
  * [GSW13] Craig Gentry, Amit Sahai, and Brent Waters.  Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based.  In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 75–92. Springer, Heidelberg, August 2013.
  * [HKM+20] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer.  Adversarially robust streaming algorithms via differential privacy.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
  * [HQWW22] Yue Hu, Ao Qu, Yanbing Wang, and Daniel B. Work.  Streaming data preprocessing via online tensor recovery for large environmental sensor networks.  ACM Trans. Knowl. Discov. Data, 16(6), jul 2022.
  * [HR07] Ishay Haviv and Oded Regev.  Tensor-based hardness of the shortest vector problem to within almost polynomial factors.  In David S. Johnson and Uriel Feige, editors, 39th ACM STOC, pages 469–477. ACM Press, June 2007.
  * [IEM18] Andrew Ilyas, Logan Engstrom, and Aleksander Madry.  Prior convictions: Black-box adversarial attacks with bandits and priors.  CoRR, abs/1807.07978, 2018.
  * [Ind06] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  J. ACM, 53(3):307–323, 2006.
  * [Jaf11] Sina Jafarpour.  Deterministic Compressed Sensing.  PhD thesis, Princeton University, 2011.
  * [Kap04] Haim Kaplan.  Persistent data structures.  In Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004.
  * [KGB17] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  In 5th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2017.
  * [Kho04] Subhash Khot.  Hardness of approximating the shortest vector problem in lattices.  In 45th FOCS, pages 126–135. IEEE Computer Society Press, October 2004.
  * [KMNS21] Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer.  Separating adaptive streaming from oblivious streaming using the bounded storage model.  In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO, Proceedings, Part III, pages 94–121, 2021.
  * [KNW10] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  On the exact space complexity of sketching and streaming small norms.  In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1161–1178. SIAM, 2010.
  * [KPTW23] Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, and David P. Woodruff.  Pseudorandom hashing for space-bounded computation with applications in streaming, 2023.
  * [LCLS17] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song.  Delving into transferable adversarial examples and black-box attacks.  In 5th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2017.
  * [Lig18] Sam Lightstone.  Physical database design for relational databases.  In Encyclopedia of Database Systems, Second Edition. Springer, 2018.
  * [LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.  On ideal lattices and learning with errors over rings.  In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1–23. Springer, Heidelberg, May / June 2010.
  * [LSO+06] Ashwin Lall, Vyas Sekar, Mitsunori Ogihara, Jun Xu, and Hui Zhang.  Data streaming algorithms for estimating entropy of network traffic.  SIGMETRICS Perform. Eval. Rev., 34(1):145–156, jun 2006.
  * [MMS+18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In 6th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2018.
  * [MN21] Boaz Menuhin and Moni Naor.  Keep that card in mind: Card guessing with limited memory.  CoRR, abs/2107.03885, 2021.
  * [Mut05] S. Muthukrishnan.  Data streams: Algorithms and applications.  Foundations and Trends® in Theoretical Computer Science, 1(2):117–236, 2005.
  * [Nis92] Noam Nisan.  Pseudorandom generators for space-bounded computation.  Comb., 12(4):449–461, 1992.
  * [PVZ15] Jeff M. Phillips, Elad Verbin, and Qin Zhang.  Lower bounds for number-in-hand multiparty communication complexity, made easy, 2015.
  * [RSW22] Mohammad Roghani, Amin Saberi, and David Wajc.  Beating the folklore algorithm for dynamic matching.  In 13th Innovations in Theoretical Computer Science Conference, ITCS, 2022.  (to appear).
  * [SAC+79] Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price.  Access path selection in a relational database management system.  In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pages 23–34. ACM, 1979.
  * [SDNR96] Amit Shukla, Prasad Deshpande, Jeffrey F. Naughton, and Karthikeyan Ramasamy.  Storage estimation for multidimensional aggregates in the presence of hierarchies.  In VLDB’96, Proceedings of 22th International Conference on Very Large Data Bases, pages 522–531, 1996.
  * [SGV02] Alexander Szalay, Jim Gray, and Jan VandenBerg.  Petabyte scale data mining: Dream or reality?  Proceedings of SPIE - The International Society for Optical Engineering, 08 2002.
  * [Sho94] Victor Shoup.  Fast construction of irreducible polynomials over finite fields.  Journal of Symbolic Computation, 17(5):371–391, 1994.
  * [SKL+06] Minho Sung, A. Kumar, Li Li, Jia Wang, and Jun Xu.  Scalable and efficient data streaming algorithms for detecting common content in internet traffic.  In 22nd International Conference on Data Engineering Workshops (ICDEW’06), pages 27–27, 2006.
  * [SST+18] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry.  Adversarially robust generalization requires more data.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS., pages 5019–5031, 2018.
  * [SV11] N.P. Smart and F. Vercauteren.  Fully homomorphic SIMD operations.  Cryptology ePrint Archive, Report 2011/133, 2011.  https://eprint.iacr.org/2011/133.
  * [SZS+14] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  International Conference on Learning Representations, 2014.
  * [TKP+18] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel.  Ensemble adversarial training: Attacks and defenses.  In 6th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2018.
  * [VSGB05] Shobha Venkataraman, Dawn Xiaodong Song, Phillip B. Gibbons, and Avrim Blum.  New streaming algorithms for fast detection of superspreaders.  In Network and Distributed System Security Symposium, 2005.
  * [vzGG13] Joachim von zur Gathen and Jürgen Gerhard.  Fast polynomial evaluation and interpolation.  Cambridge University Press, 3 edition, 2013.
  * [Waj20] David Wajc.  Rounding dynamic matchings against an adaptive adversary.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 194–207, 2020.
  * [WZ12] David P. Woodruff and Qin Zhang.  Tight bounds for distributed functional monitoring.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 941–960, New York, NY, USA, 2012. Association for Computing Machinery.
  * [WZ21] David P. Woodruff and Samson Zhou.  Tight bounds for adversarially robust streams and sliding windows via difference estimators.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1183–1196, 2021.
  * [ZKWX05] Qi (George) Zhao, Abhishek Kumar, Jia Wang, and Jun (Jim) Xu.  Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices.  SIGMETRICS Perform. Eval. Rev., 33(1):350–361, jun 2005.