Skip to main content
1 of 2
LeoDucas
  • 1.4k
  • 6
  • 12

This is equivalent to an LWE language.

More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A$. Then $C^{-1} u = A' x = B x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.

LeoDucas
  • 1.4k
  • 6
  • 12