# LWE with a low rank matrix

Consider the decision LWE setting, where we have to distinguish between $$(A, As + e)$$ and $$(A, u)$$, for a randomly chosen $$m \times n$$ matrix $$A$$, an $$n \times 1$$ secret vector $$s$$, an $$m \times 1$$ Gaussian secret vector $$e$$, and a randomly chosen $$m \times 1$$ vector $$u$$.

In many places, a "lossy version" of the setting is considered, where $$A$$ is replaced with a randomly sampled low rank matrix. How low can the rank of the matrix be for the setting to still be secure? I did not find any explicit calculations that talk about how the runtime of the distinguisher scales with the rank of $$A$$.

• FYI, Chris Pikert, and Mark are answering such questions on Cryptography Jul 31 at 23:19