A Systematic Study of Sparse LWE

In this work, we introduce the sparse LWE assumption, an assumption that draws inspiration from both Learning with Errors (Regev JACM 10) and Sparse Learning Parity with Noise (Alekhnovich FOCS 02). Exactly like LWE, this assumption posits indistinguishability of \((\textbf{A}, \textbf{s}\textbf{A}+\textbf{e} \mod p)\) from \((\textbf{A}, \textbf{u})\) for a random \(\textbf{u}\) where the secret \(\textbf{s}\) , and the error vector \(\textbf{e}\) is generated exactly as in LWE. However, the coefficient matrix \(\textbf{A}\) in sparse LPN is chosen randomly from \(\ensuremath {\mathbb {Z}}^{n\times m}_{p}\) so that each column has Hamming weight exactly k for some small k. We study the problem in the regime where k is a constant or polylogarithmic. The primary motivation for proposing this assumption is efficiency. Compared to LWE, the samples can be computed and stored with roughly O(n/k) factor improvement in efficiency. Our results can be summarized as: We stress that our results are preliminary. However, our results make a strong case for further investigation of sparse LWE.