Module LWE (degree 1) ⇔ LWE

Equivalence · fully-black-box reduction · standard model · LS15

Statement

Module LWE over the degree-1 ring $R=\mathbb{Z}$ at module rank $n$ is LWE in dimension $n$ with the same modulus, error distribution and number of samples, so each is hard if and only if the other is — LS15.

Sketch

With $R_q={\mathbb{Z}}_q$, the Module LWE sample $(\mathbf{A},\mathbf{As}+\mathbf{e})$ has $\mathbf{A}\in {\mathbb{Z}}_q^{m\times n}$ and $\mathbf{s}\in {\mathbb{Z}}_q^n$, so it is an LWE sample; the identity map is a reduction in both directions.

Notes

• Rank $n$ over a degree-$n$ ring does not recover LWE: the module has ${\mathbb{Z}}_q$-dimension $n^2$, and $\mathbf{A}$ has structured $n\times n$ blocks (negacyclic for $f=x^n+1$) — folklore.