# LWE (Learning With Errors)
This section focuses **only on LWE (Learning With Errors)** ciphertexts. In TFHE-style schemes, LWE is the standard “small scalar ciphertext” used to encrypt a single value (often a bit or a small integer).
***
***
## 1) What problem does an LWE ciphertext solve?
An LWE ciphertext lets you:
* **hide** a message `m` so it looks random to everyone else
* still allow certain computations **directly on ciphertexts**
* rely on security that comes from the hardness of the **LWE problem** (recovering secret/noise from noisy linear equations)
The important intuition:
> An LWE ciphertext is a *noisy linear equation* that only the secret key holder can “unmix.”
***
## 2) Minimal notation you need
* `q` : ciphertext modulus (we work modulo `q`)
* `n` : LWE dimension (size of vectors)
* `s ∈ Z_q^n` : secret key vector
* `a ∈ Z_q^n` : random mask vector
* `b ∈ Z_q` : body term (a scalar)
* `e` : small noise/error (sampled from a small distribution)
* `Δ` : scaling factor to embed plaintext into `Z_q`
* `m` : plaintext message (often a bit)
An **LWE ciphertext** is the pair: $$\text{ct} = (\mathbf{a}, b)$$
***
## 3) The core LWE equation
Encryption is designed so that:
$$b = \langle \mathbf{a}, \mathbf{s}\rangle + \Delta\cdot m + e \pmod q$$
Read it like this:
* `⟨a, s⟩` = a dot product that “mixes” the secret into the ciphertext
* `Δ·m` = the message, scaled so it can be recovered by rounding
* `e` = small noise that makes the system hard to solve without the secret key
***
## 4) Key generation
**Secret key generation:** choose a secret vector `s`.
In practice, the distribution for `s` is chosen carefully (often small/binary-ish in implementations), but for understanding:
* it’s just a vector only the decryptor knows
***
## 5) Encryption
To encrypt a message `m`:
1. Sample a random mask: $$\mathbf{a} \leftarrow \text{Uniform}(\mathbb{Z}\_q^n)$$
2. Sample small noise: $$e \leftarrow \chi \quad (\text{small})$$
3. Compute: $$b = \langle \mathbf{a}, \mathbf{s}\rangle + \Delta\cdot m + e \pmod q$$
4. Output ciphertext: $$\text{ct} = (\mathbf{a}, b)$$
That’s it: **mask + body**.
***
## 6) Decryption
Given ciphertext `(a, b)` and secret key `s`:
1. Remove the secret-key mix: $$t = b - \langle \mathbf{a}, \mathbf{s}\rangle \pmod q$$
2. Now: $$t \approx \Delta\cdot m + e \quad (\text{mod } q)$$
3. Recover `m` by **rounding/thresholding**.
***
## 7) Toy example
Choose small numbers just to see the mechanics:
* `q = 97`
* `n = 2`
* `s = (5, 9)`
* bit scaling `Δ = 48` (≈ q/2)
* message `m = 1`
* noise `e = 2`
* random mask `a = (12, 7)`
Compute dot product: $$\langle a,s\rangle = 12\cdot5 + 7\cdot9 = 60 + 63 = 123 \equiv 26 \pmod{97}$$
Compute `b`: $$b = 26 + 48\cdot1 + 2 = 76 \pmod{97}$$
Ciphertext: $$(a,b) = ((12,7), 76)$$
Decrypt: $$t = 76 - 26 = 50 \pmod{97}$$
Since `50` is close to `Δ = 48`, we decode `m = 1`.
***
## 8) Homomorphic operations on LWE
### Addition of ciphertexts
If:
* `ct1 = (a1, b1)` encrypts `m1`
* `ct2 = (a2, b2)` encrypts `m2`
Then define: $$ct\_{\text{sum}} = (a1+a2,; b1+b2)\pmod q$$
Decrypting `ct_sum` gives approximately: $$\Delta(m\_1+m\_2) + (e\_1+e\_2)$$
**Key takeaway:** addition is simple, but **noise adds up**.
***
### Multiply by a known (public) constant
For public integer `k`: $$k\cdot(a,b) = (k a,; k b)\pmod q$$
Decrypts to: $$\Delta(km) + k e$$
**Key takeaway:** scaling is easy, but **noise scales too**.
***
## 9) Noise: why it exists and why it matters
* **Why noise exists:** without noise, attackers could solve linear equations to recover secrets/messages.
* **Why it matters:** every operation increases noise.
* **What it limits:** too much noise makes rounding ambiguous → decryption fails.
A good beginner rule:
> LWE is powerful, but you must manage noise or refresh ciphertexts using other TFHE machinery (covered later).
***
## 10) Summary
* An LWE ciphertext is `(a, b)`
* It’s built so: $$b = \langle a, s\rangle + \Delta m + e \pmod q$$
* Decrypt by subtracting `⟨a,s⟩` then rounding
* Homomorphic **add** and **public scalar multiply** are easy
* Noise is essential for security and the main constraint on computation
---
# 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/lwe.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.