Memory-Sample Lower Bounds for LWE

In this work, we show memory-sample lower bounds for the fundamental problem of learning with error (LWE). In this problem, a learner tries to learn a uniformly sampled \(x \sim \mathbb {Z}_q^n\) from a stream of inner products plus errors sampled from discrete Gaussians of scale \(\sigma \) . Any learning algorithm requires either at least \(\varOmega (k^2 / \log (q / \sigma ))\) bits of memory, or at least \(2^{\varOmega (k)}\) many samples, where \(k = \varOmega (n \log (1 / (1 - \phi (q)/q)))\) . This matches with the information-theoretic upper bound when q is prime. In addition to LWE, our bounds apply to a wide range of learning problems. Following the work of Garg, Raz, Tal [STOC 2018], we describe a learning problem by a learning matrix \(M :A \times X \rightarrow \{0, 1, \cdots , q-1\}\) together with an error matrix \(E\) . The learner tries to learn \(x \sim X\) from a stream of samples, \((a_1, b_1), \cdots , (a_m, b_m)\) , where for every i, \(a_i \sim A\) , and \(b_i \leftarrow t\) with probability \(E_{M(a,x),t}\) . We characterize the learning problems that can have memory-sample lower bounds as “q-balanced”, which is a generalization of the L2-extractor in [GRT18]. We also show a reduction from q-balanced to L2-extractor, which provides a general way to prove q-balanced and thus apply our bounds. Our proof builds on [GRT18] and the work of Garg, Kothari, Liu, Raz [APPROX/RANDOM 2021].