papers/lux-lattice-cryptography-primer/sections/03-ring-lwe-and-module-lwe.tex

\section{Ring-LWE and Module-LWE}


\subsection{The Efficiency Problem}

Plain LWE has a fundamental efficiency issue: the public key is a matrix $\mathbf{A} \in
\mathbb{Z}_q^{m \times n}$, which has size $O(n^2)$. For 128-bit security, $n \approx 512$,
so keys are hundreds of kilobytes. This is impractical for blockchain use.

\subsection{Ring-LWE}

Ring-LWE replaces vectors over $\mathbb{Z}_q$ with elements of a polynomial ring:

\[
R_q = \mathbb{Z}_q[X] / (X^n + 1)
\]

where $n$ is a power of 2 and $q$ is prime. An element of $R_q$ is a polynomial of
degree $< n$ with coefficients in $\mathbb{Z}_q$.

\begin{definition}[Ring-LWE]
Given samples $(a_i, b_i = a_i \cdot s + e_i) \in R_q \times R_q$, recover $s \in R_q$.
\end{definition}

The key advantage: a single ring element replaces an entire vector, reducing key sizes
from $O(n^2)$ to $O(n)$. Polynomial multiplication in $R_q$ replaces matrix-vector
multiplication, and NTT makes it $O(n \log n)$ instead of $O(n^2)$.

\subsection{Module-LWE}

Module-LWE (M-LWE) is a middle ground: it uses \emph{small matrices of ring elements}
rather than single ring elements or large integer matrices.

\begin{definition}[Module-LWE]
Let $k$ be a small integer (2, 3, or 4). Given
$(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e})$ where
$\mathbf{A} \in R_q^{k \times k}$, $\mathbf{s}, \mathbf{e} \in R_q^k$,
recover $\mathbf{s}$.
\end{definition}

M-LWE is the basis for ML-KEM and ML-DSA. The module dimension $k$
parameterizes the security level:

\begin{table}[H]
\centering
\small
\begin{tabular}{@{}lcccc@{}}
\toprule
\textbf{Scheme} & $n$ & $k$ & $q$ & \textbf{Security} \\
\midrule
ML-KEM-512 (Kyber-512) & 256 & 2 & 3329 & 128-bit \\
ML-KEM-768 (Kyber-768) & 256 & 3 & 3329 & 192-bit \\
ML-KEM-1024 (Kyber-1024) & 256 & 4 & 3329 & 256-bit \\
ML-DSA-44 (Dilithium2) & 256 & 4/4 & 8380417 & 128-bit \\
ML-DSA-65 (Dilithium3) & 256 & 6/5 & 8380417 & 192-bit \\
ML-DSA-87 (Dilithium5) & 256 & 8/7 & 8380417 & 256-bit \\
\bottomrule
\end{tabular}
\caption{NIST post-quantum standard parameters. All use $n = 256$.}
\end{table}

%% ============================================================