# V. Ring Learning With Error (RLWE)

[TOC]

## Introduction
This is our fifth chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. While Standard LWE establishes a robust security foundation, it suffers from significant computational inefficiency (key-size: $\tilde{O}(n^2)$). Ring-LWE (RLWE) addresses this problem, making lattice-based cryptography viable for practical (key-size: $\tilde{O}(n)$). Furthermore, Module-LWE, the foundation of the ML-KEM standard, offers a modern middle ground. It balances the high efficiency of rings with the robust security of modules, effectively mitigating the risk of 'Algebraic Attacks' while maintaining practical performance.

🚪 Recall of Polynomial Ring: [I. The Mathematical Foundations of Cryptography: Abstract Algebra](https://hackmd.io/TDwmj5IlRxiDeEpwdngUEQ)

## Polynomial ? lattice ?
In standard geometry, a lattice is a grid of dots. In algebra, a polynomial is an equation. The connection between them is called **Coefficient Embedding**.

Essentially, we treat the **coefficients** of a polynomial as the **coordinates** of a vector in a lattice.

Below, we briefly talk about coefficient embedding.

### Coefficients to Coordinates

- Let a polynomial $a(x)$
$$a(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1} \in \mathbb{Z}[x] / (x^n + 1)$$
- We can map this directly to a vector in an $n$-dimensional lattice ($\mathbb{Z}^n$) by simply taking the coefficients:
$$\mathbf{v} = (a_0, a_1, a_2, \dots, a_{n-1})$$
- Properties:
- **The Algebra:** We add and multiply polynomials.
- **The Geometry:** We add and rotate vectors in the lattice.

### Example of Embedding into $\mathbb{Z}^4$
- Take a polynomial $a(x)$ for example:
$$a(x) = 3 + 5x - 2x^2 + 1x^3 \in \mathbb{Z}[x] / (x^4 + 1)$$
- Turn $a(x)$ into a lattice point, we havea a lattice point $\mathbf{v}_0 = (3, 5, -2, 1)$
- A lattice is an infinite grid generated by a basis. In **Ideal Lattices**, the basis is formed by multiplying the polynomial $a(x)$ by $x, x^2, x^3...$ (The Rotations)
1. Multiply $a(x)$ by $x$:
$$a(x) \cdot x = 3x + 5x^2 - 2x^3 + 1x^4= -1 + 3x + 5x^2 - 2x^3$$
We get a new lattice point: $\mathbf{v}_1 = (-1, 3, 5, -2)$
2. Multiply $a(x)$ by $x^2$, we shift $\mathbf{v}_1$ again, and get new vector: $\mathbf{v}_2 = (2, -1, 3, 5)$
3. Multiply $a(x)$ by $x^3$, We shift $\mathbf{v}_1$ again, and get new vector: $\mathbf{v}_3 = (-5, 2, -1, 3)$
- We can now stack these vectors to form the **Basis Matrix** of the lattice generated by the polynomial $a(x)$.

$$
\mathbf{L} =
\begin{bmatrix}
3 & 5 & -2 & 1 \\
-1 & 3 & 5 & -2 \\
2 & -1 & 3 & 5 \\
-5 & 2 & -1 & 3
\end{bmatrix}
$$

### The advantage of coefficient embeddin
- **Compression:** In standard LWE, we have to send this entire random $4 \times 4$ matrix as your public key. In Ring-LWE, only the first row is needed (the polynomial $a(x)$). The receiver constructs the lattice by rotating the first row.
- **Structure:** This creates a "Structured Lattice" (specifically an Ideal Lattice). It allows us to use fast polynomial math (FFT/NTT) to process the data, rather than slow matrix multiplication.

## Definitions of RLWE
- $R_q$: a polynomial ring with modulus $q$.
- $n$: the security parameter that satisfies $n = 2^k$ for an integer $k \ge 0$,
- $q$: a large prime modulus that is polynomial in $n$ and satisfies $q \equiv 1$ mod $2n$
- $s$: secret $s \in R_q$ and is fixed
- $\chi$: an error distribution $\chi$ over $R$, that is concentrated on "small integer" coefficients,
- The **RLWE distribution** over $R_q \times R_q$, denoted by
$$RLWE(n, q, \chi) := \{(\mathbf{a}, \mathbf{b})\}$$
is obtained by repeating these steps:
1. sample an polynomial $\mathbf{a} \leftarrow R_q$
2. sample a noise polynomial $\epsilon \leftarrow \chi$ over $R$
3. compute the polynomial $\mathbf{b} = \mathbf{s} \cdot \mathbf{a} + \epsilon \mod R_q$,
4. output $(\mathbf{a}, \mathbf{b})$.

In LWE-based cryptosystems, the public key is $(A, \vec{b})$ where $A \in \mathbb{Z}_q^{n \times m}$ is a matrix that needs $O(mn)$ storage. For an RLWE-based cryptosystem, the public key size can be reduced to $O(n)$, which is a significant saving. The reason is because each sample from an RLWE distribution is a pair of $n$-degree polynomials that can replace $n$ samples from the standard LWE distribution.

## RLWE-based encryption scheme

To end this chapter, we state a simple RLWE-based public-key encryption scheme presented by Lyubashevsky et al. (2010).

- Let $R = \mathbb{Z}[x]/(x^n + 1)$, where $n$ is taken to be a power of 2 to make the modulo polynomial cyclotomic, hence $R$ is a cyclotomic field. This is the domain for the secret key and noise vectors that are sampled according to a specific distribution $\chi$.
- Restrict the public key and ciphertexts to be in the domain $$R_q = \mathbb{Z}_q[x]/(x^n + 1)$$

### Private Key Encryption Scheme
- #### 1. Key Generation
- **Private key:** Sample a private key $\mathbf{s} \leftarrow \chi$
- #### 2. Encryption
- Encrypt an $n$ bits message $\mathbf{m} \in \{0, 1\}^n$ by computing
$$\mathbf{b} = \mathbf{-a} \cdot \mathbf{s} + \mathbf{e} + \lfloor q/2 \rfloor \cdot \mathbf{m} \mod q$$
where $\mathbf{e}=e_0+e_1x+e_2x^2+...+e_{n-1}e^{n-1} \leftarrow \chi$ is random samples.
- Then output the ciphertext $\mathbf{c} = (\mathbf{a}, \mathbf{b})$
- #### 3. Decryption
- Decrypt the ciphertext $\mathbf{c}$ using the secret key by computing
$$\mathbf{m} = \left[ \left\lfloor \frac{2}{q} [\mathbf{b} + \mathbf{a} \cdot \mathbf{s}]_q \right\rceil \right]_2$$
- The decryption works correcly if $\frac{2}{q}\cdot e_i<\frac{1}{2}$, because $\lfloor\frac{2}{q}\cdot e_i\rceil=0$ that leaves no error on the message $\mathbf{m}$.

### Public Key Encryption Scheme
- #### 1. Key Generation
- **Private key:** Sample a private key $\mathbf{s} \leftarrow \chi$
- **Public key:** Sample random polynomials $\mathbf{a} \leftarrow R_q$ and $\mathbf{e} \leftarrow \chi$ and output the public key
$$(\mathbf{a}, \mathbf{b} = -[\mathbf{a} \cdot \mathbf{s} + \mathbf{e}]_q)$$
- #### 2. Encryption
- Encrypt an $n$ bits message $\mathbf{m} \in \{0, 1\}^n$ by computing
\begin{cases}
\mathbf{u} = \mathbf{b} \cdot \mathbf{r} + \mathbf{e}_1 + \lfloor q/2 \rfloor \cdot \mathbf{m} \mod q \\
\mathbf{v} = \mathbf{a} \cdot \mathbf{r} + \mathbf{e}_2 \mod q
\end{cases}
where $\mathbf{r}, \mathbf{e}_1, \mathbf{e}_2 \leftarrow \chi$ are random samples. Then output the ciphertext $\mathbf{c} = (\mathbf{u}, \mathbf{v})$.
- #### 3. Decryption
- Decrypt the ciphertext $\mathbf{c}$ using the secret key by computing
$$m = \left[ \left\lfloor \frac{2}{q} [\mathbf{u} + \mathbf{v} \cdot \mathbf{s}]_q \right\rceil \right]_2$$
- Decryption works if the parameters are properly set and polynomials sampled from $R$ have small coefficients (according to the distribution $\chi$). Because
$$\mathbf{u} + \mathbf{v} \cdot \mathbf{s} = \lfloor q/2 \rfloor \cdot \mathbf{m} + (\mathbf{e} \cdot \mathbf{r} + \mathbf{e}_1 + \mathbf{e}_2 \cdot \mathbf{s}) \mod q$$
If those polynomials are taken with large coefficients, after multiplications they will neither stay within modulo $q$, nor be rounded to 0.

## Discussion
Note that we have omitted the formal security proofs for both LWE and RLWE, as understanding their core ideas does not require full exposure to the underlying reductions. However, a rigorous treatment of their security and the rationale behind parameter selection rely heavily on algebraic number theory. Readers interested in these foundations are encouraged to consult Chapter 8 in the reference below.

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