Module LWE (rank 1) ⇔ Ring LWE

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

Statement

Module LWE at module rank $k=1$ over $R_q$ is Ring LWE over $R_q$ with the same error distribution and number of samples, so each is hard if and only if the other is — LS15.

Sketch

A rank-1 module over $R_q$ is $R_q$ itself: at $k=1$, $\mathbf{A}\in R_q^{m\times 1}$ is a column of ring elements $a_i$ and $\mathbf{s}=s\in R_q$, so $(\mathbf{A},\mathbf{As}+\mathbf{e})$ lists the Ring LWE samples $(a_i,a_{i}s+e_i)$. The identity map is a reduction in both directions.