# IV. Learning With Error (LWE)

[TOC]

## Introduction
This is the fourth chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series.

### From SIS to LWE

In [preivous chapter](https://hackmd.io/@spockwall/rJgV4qFgZe), we have introduced the SIS problem. The main drawback of SIS-based cryptosystems is the impractical public key size and ciphertext size. Typically, the key size is $\tilde{O}(n^4)$ and the plaintext size is $\tilde{O}(n^2)$, where $n$ is a security parameter with typical values in the hundreds.

The **learning with error (LWE)** problem was introduced by Regev (2005) as another foundational assumption for building lattice-based cryptosystems with provable security but smaller key and ciphertext size. In particular, LWE-based cryptosystems’ public key size is $\tilde{O}(n^2)$, which is a considerable improvement from SIS-based ones, although still not practical for large $n$. In addition, the plaintext size is increased by only $\tilde{O}(1)$ times once encrypted.

Intuitively, the LWE problem tries to recover a secret key from a system of noisy linear equations. To draw an analogy, if the linear equations are not noisy, the problem can be solved efficiently using Gaussian elimination. See following example.

## Example of LWE

### Learning Without Error
Given three linear equations of the form $Ax = B$, where $A$ is a 3x3 matrix, $B$ is a 3x1 matrix and $x$ is a 1x3 matrix, we can use **Gaussian elimination** to turn $A$ into an upper triangular matrix, hence solving for the solution $x$.

$$
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9 \\
1 & 1 & -1 & 1 \\
3 & 10 & 5 & 35
\end{array}
\right]
\rightarrow
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9 \\
0 & -2 & -2 & -8 \\
0 & 1 & 2 & 8
\end{array}
\right]
\rightarrow
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9 \\
0 & -1 & 0 & 0 \\
0 & 1 & 2 & 8
\end{array}
\right]
\rightarrow
\left[
\begin{array}{ccc|c}
1 & 0 & 0 & 5 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 4
\end{array}
\right]
$$

The LWE problem, however, introduces noises (or errors) into the linear equations, making the above problem significantly harder. More precisely, Gaussian elimination involves linear combinations of rows. This process may amplify the noises so that the resulting rows are unable to maintain the original information that is embedded in the equations.

***

### Learning With Error

In **Learning With Error (LWE)**, we add a small, random error ($\epsilon$) to every equation. Let's see what happens to the math when we try to solve that noisy system using the same Gaussian elimination steps.

#### → Step 1. The Setup (With Noise)
We take the original numbers but add a small unknown error ($\epsilon$) to the answers. First, we sample small error: $(\epsilon_1, \epsilon_2, \epsilon_3) = (0.3, -0.2, 0.3)$

$$
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9 + \epsilon_1 \\
1 & 1 & -1 & 1 + \epsilon_2 \\
3 & 10 & 5 & 35 + \epsilon_3
\end{array}
\right]
\rightarrow
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9.3 \\
1 & 1 & -1 & 0.8 \\
3 & 10 & 5 & 35.3
\end{array}
\right]
$$

#### → Step 2: Eliminate the first column
$$
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9.3 \\
1 & 1 & -1 & 0.8 \\
3 & 10 & 5 & 35.3
\end{array}
\right]
\xrightarrow{}
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9.3 \\
0 & -2 & -2 & -8.5 \\
0 & 1 & 2 & 7.4
\end{array}
\right]
$$

#### → Step 3: Eliminate the second column
$$
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9.3 \\
0 & -2 & -2 & -8.5 \\
0 & 1 & 2 & 7.4
\end{array}
\right]
\xrightarrow{}
\left[
\begin{array}{ccc|c}
1 & 3 & 1 & 9.3 \\
0 & -2 & -2 & -8.5 \\
0 & 0 & 1 & {3.15}
\end{array}
\right]
$$

#### Why is this secure ?
In this toy example, the error $(\epsilon_1, \epsilon_2, \epsilon_3)$ is small enough that we might guess the "real" answer is 0. But in real cryptography, the dimension of the matrice are usauly more than 500. We use matrices with hundreds of rows. If hundreds of row reductions are performed, a small initial error could be multiplied by large coefficients. Eventually, the accumulated noise becomes too large to recover the valid answers.

## Definitions
- $n$: the security parameter (usually $n = 2^k$ for an integer $k \geq 0$).
- $q$: an integer (not necessarily prime) that is a function of $n$, i.e., $q = q(n)$.
- $\vec{s} \in \mathbb{Z}_q^n$: a fixed secret .
- $\chi$ over $\mathbb{Z}_q$: an error distribution.
- An **LWE distribution** $A_{s, \chi}$ over $\mathbb{Z}_q^n \times \mathbb{Z}_q$ is obtained by these steps:
1. Sample a vector $\vec{a} \leftarrow \mathbb{Z}_q^n$,
2. Sample a noise element $\epsilon \leftarrow \chi$ over $\mathbb{Z}_q$,
3. Compute $b = \vec{s} \cdot \vec{a} + \epsilon \mod q$,
4. Output $(\vec{a}, b)$.

Note:
- The integer $q$ which controls the size of the ring $\mathbb{Z}_q$ is often a large integer and a function of $n$, but it does not need to be a prime number for the hardness proof of the LWE search problem.
- It is only required to be a prime when reducing the search to decision LWE, in which the ring $\mathbb{Z}_q$ needs to be a field to build the connection between the two problems.
- It has been demonstrated that solving a system of exact linear equations can be done efficiently with Gaussian elimination, but solving a system of *noisy* linear equations is conjectured to be hard. This motivates the search version of the LWE problem (we ignore the decision version here).
- The form of an LWE sample can be in vector or matrix.
- Vector form: $(\vec{a}, b) \subseteq \mathbb{Z}_q^{N} \times \mathbb{Z}_q$
- Matrix form: $(A, \vec{b}) \subseteq \mathbb{Z}_q^{n \times N} \times \mathbb{Z}_q^N$

## LWE-based Encryption Scheme
The scheme below is the original LWE-based encryption scheme proposed by Regev. It operates on bits ($m \in \{0, 1\}$) and consists of three main phases: **Key Generation**, **Encryption**, and **Decryption**. In other LWE-based encryption schemes, the plaintext message can take values beyond just 0 or 1.

- #### 1. Key Generation
- **Private Key:** Choose a private key vector $\vec{s} \leftarrow \mathbb{Z}_q^n$.
- **Public Key:** Choose a random matrix $A = [\vec{a}_1, \dots, \vec{a}_N] \leftarrow \mathbb{Z}_q^{n \times N}$ and an error vector $\vec{e} \leftarrow \chi^N$.
- Compute the public vector $\vec{b}$:
$$\vec{b} = \vec{s} \cdot A + \vec{e}$$
- The public key is the pair $(A, \vec{b})$.

- #### 2. Encryption
- To encrypt a message bit $m \in \{0, 1\}$, first choose a random subset $S$: $$S \subseteq \{x \,|\, 1 \le x\le N \land x\in \mathbb{Z}\}$$

- To encrypt m, compute the pair $(\vec{c}_1, c_2)$ by summing the public key components corresponding to the subset $S$. If $m==1$, add a scaling fact $\lfloor\frac{q}{2}\rfloor$ to the second component,
$$Enc(m) = (\vec{c}_1, c_2) = \left(\sum_{i \in S} \vec{a}_i, \lfloor \frac{q}{2} \rfloor \cdot m+ \sum_{i \in S} b_i\right)$$

- #### 3. Decryption
- Given a ciphertext $(\vec{c}_1, c_2)$, the decryption logic relies on determining the closeness of the result.
- Compute the value $v = c_2 - \vec{s} \cdot \vec{c}_1$. If $v$ is close to $0$, output 0. If $v$ is close to $\lfloor \frac{q}{2} \rfloor$, output $1$.

- #### Verify the correctness of decryption
- Why does decryption work? When decrypting the ciphertext of m, we get:

$$c_2 - \vec{s} \cdot \vec{c}_1 = \sum_{i \in S} \epsilon_i+\lfloor \frac{q}{2} \rfloor \cdot m$$

- With proper parameters, the accumulated error remains below $\lfloor \frac{q}{2} \rfloor \times \frac{1}{2}$ with high probability. This ensures the noise is too small to shift a 0 towards $\lfloor \frac{q}{2} \rfloor$ (or vice versa), allowing the algorithm to correctly distinguish between the two messages.

## Reference
- [A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption](https://arxiv.org/abs/2208.08125)