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$.

  • $\begingroup$ FYI, Chris Pikert, and Mark are answering such questions on Cryptography $\endgroup$
    – kelalaka
    Jul 31 at 23:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.