papers/lux-lattice-cryptography-primer/sections/02-learning-with-errors-lwe.tex

\section{Learning With Errors (LWE)}


\subsection{The Problem}

\begin{definition}[Learning With Errors]
Given $m$ samples of the form $(\mathbf{a}_i, b_i)$ where:
\begin{itemize}[nosep]
  \item $\mathbf{a}_i \in \mathbb{Z}_q^n$ is uniformly random,
  \item $b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod{q}$,
  \item $\mathbf{s} \in \mathbb{Z}_q^n$ is a secret vector,
  \item $e_i$ is a small ``error'' sampled from a discrete Gaussian,
\end{itemize}
recover $\mathbf{s}$.
\end{definition}

Without the error $e_i$, this is a system of linear equations---solvable by Gaussian
elimination. The error makes the problem hard: it turns an easy linear algebra problem
into a problem equivalent to finding short vectors in a lattice.

\subsection{Why LWE Is Hard}

Regev (2005) proved that solving LWE is at least as hard as solving worst-case lattice
problems (approximate SVP and approximate SIVP) in dimension $n$. This is a
\emph{worst-case to average-case} reduction: even random LWE instances are as hard as
the hardest lattice instances. No other family of cryptographic assumptions has this
property.

\subsection{LWE as Encryption}

LWE directly yields a public-key encryption scheme:

\begin{itemize}[nosep]
  \item \textbf{Key generation}: Choose secret $\mathbf{s}$. Publish samples
    $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e})$.
  \item \textbf{Encryption of bit $m$}: Choose random $\mathbf{r}$. Compute
    $\mathbf{u} = \mathbf{A}^T \mathbf{r}$ and $v = \mathbf{b}^T \mathbf{r} + m \cdot \lfloor q/2 \rfloor$.
  \item \textbf{Decryption}: Compute $v - \mathbf{u}^T \mathbf{s} = m \cdot \lfloor q/2 \rfloor + \text{small noise}$.
    Round to recover $m$.
\end{itemize}

The decryption works because the noise terms are small relative to $q/2$. The scheme is
secure because distinguishing $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e})$ from
uniform random is the LWE problem.

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