  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.
