# RLWE (Ring-LWE)
In the previous sections:
* **LWE** encrypted a *single value* using vectors.
* **GLWE** generalized that idea to encrypt a *polynomial* using polynomials.
Now we focus on **RLWE (Ring-LWE)**.
> **RLWE is a special case of GLWE**: when you instantiate GLWE with **k = 1** (one secret polynomial) and **N a power of 2**, you obtain **RLWE**.
So conceptually:
* **GLWE** = “polynomial ciphertext with k secret polynomials.”
* **RLWE** = “polynomial ciphertext with exactly 1 secret polynomial”
This makes RLWE simpler than general GLWE, while still keeping the powerful polynomial/ring structure.
***
***
## 1) What is RLWE used for?
RLWE ciphertexts are used when you want:
* the **efficiency** of ring/polynomial arithmetic (fast convolution-style ops)
* the ability to naturally work with **polynomial messages**
* a simpler structure than GLWE (`k=1`)
In TFHE-family explanations, RLWE shows up as one of the “main ciphertext types” alongside LWE and RGSW.
***
## 2) Minimal notation you need (RLWE edition)
* `q`: ciphertext modulus (coefficients are mod `q`)
* `N`: polynomial degree (commonly a power of 2 in this context)
* `R = Z[X] / (X^N + 1)` : polynomial ring
* `R_q = Z_q[X] / (X^N + 1)` : same ring, but coefficients reduced mod `q`
* `S ∈ R` : **secret key polynomial**
* `A ∈ R_q` : **mask polynomial**
* `B ∈ R_q` : **body polynomial**
* `E ∈ R_q` : **noise polynomial** (small coefficients)
* `Δ`: scaling factor for encoding plaintext into ciphertext space
* `M ∈ R_p` : plaintext polynomial (small coefficients, mod `p`)
***
## 3) The shape of an RLWE ciphertext
An RLWE ciphertext is just **two polynomials**:
$$\text{ct} = (A,; B) \in R\_q^2$$
Compare:
* LWE: `(a, b)` where `a` is a vector and `b` is a scalar
* RLWE: `(A, B)` where `A` and `B` are polynomials
***
## 4) The core RLWE equation
RLWE is GLWE with `k=1`, so the GLWE equation:
$$B = \sum\_{i=0}^{k-1} A\_i S\_i + \Delta M + E \pmod q$$
becomes simply:
$$B = A\cdot S + \Delta M + E \pmod q$$
That’s the entire idea:
* `A·S` hides the secret
* `ΔM` carries the message
* `E` is a small noise that provides security
And all of this happens inside the ring `R_q`.
***
## 5) RLWE encryption
To encrypt a plaintext polynomial `M`:
1. Sample random mask polynomial: $$A \leftarrow \text{Uniform}(R\_q)$$
2. Sample small noise polynomial: $$E \leftarrow \chi \quad (\text{small coefficients})$$
3. Compute body: $$B = A\cdot S + \Delta M + E \pmod q$$
4. Output ciphertext: $$\text{ct} = (A,B)$$
***
## 6) RLWE decryption
Given `(A, B)` and secret `S`:
1. Remove the secret term: $$T = B - A\cdot S \pmod q$$
2. Now: $$T \approx \Delta M + E \pmod q$$
3. Recover `M` by coefficient-wise rounding/decoding (same idea as LWE, but per coefficient).
Compute `B - A·S` in the ring, then rescale/round to get back the plaintext polynomial.
***
## 7) How RLWE connects to GLWE (why “k = 1” matters)
* **GLWE → RLWE** when:
* `k = 1`
* `N` is a power of 2
So RLWE is not a different “idea” than GLWE just a simpler parameter choice.
### Intuition for beginners
* GLWE with `k>1`: you have **multiple secret polynomials**, and the mask is a list of polynomials.
* RLWE (`k=1`): you have **one secret polynomial**, and the mask is just one polynomial.
That simplification often makes explanations and implementations easier, while keeping the ring benefits.
***
## 8) What operations are “easy” on RLWE?
Just like LWE and GLWE, RLWE is naturally good at **linear operations**:
### Add two RLWE ciphertexts
$$(A\_1,B\_1) + (A\_2,B\_2) = (A\_1 + A\_2,; B\_1 + B\_2)\pmod q$$
Decrypts to approximately: $$\Delta(M\_1 + M\_2) + (E\_1 + E\_2)$$
Noise grows additively.
### Multiply by a public constant (or public polynomial)
For a public value `c` (or polynomial `C(X)`): $$c\cdot(A,B) = (cA,; cB)\pmod q$$
Noise scales.
> Multiplying ciphertexts by ciphertexts is more complex and is handled by additional TFHE machinery (covered later).
***
## 9) ELI5 (Explain Like I’m 5)
* **LWE**: “a locked box holding one number.”
* **RLWE**: “a locked box holding a whole *row* of numbers at once.”
* Instead of listing the row as a normal vector, RLWE stores it as a **polynomial** because polynomial math is fast and convenient.
* RLWE is basically GLWE with “just one secret polynomial.”
***
## 10) Quick summary
* RLWE ciphertext: **two polynomials** `(A, B)`
* Encryption meaning: $$B = A\cdot S + \Delta M + E \pmod q$$
* Decrypt by computing `B - A·S`, then rounding
* RLWE is **GLWE with k = 1** (and `N` power of 2 in the series setting).
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://sabanaku77.gitbook.io/fhe-handbook-for-beginners/rlwe.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.