# LWE(Regev approach)
- Params:
- $n$ security parameter (dimension),
- $q$ a prime modulus,
- $m$ number of LWE samples (typically $m = O(n \log q)$),
- $\chi$ be an error distribution (e.g., a discrete Gaussian)
- $KeyGen(n,q,m,\chi)$:
- $\mathbf{s} \xleftarrow{rnd} \mathbb{Z}_q^n$
- $\mathbf{A} \xleftarrow{rnd} \mathbb{Z}_q^{m \times n}$
- $\mathbf{e} \sim (\chi)^m$
- $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \in \mathbb{Z}_q^m$
- $(sk, pk) = (\mathbf{s}, (\mathbf{A},\mathbf{b}))$
- $Enc(\mu)$ encrypt a bit $\mu \in \{0,1\}$:
- $\mathbf{r} \xleftarrow{rnd} \{0,1\}^m$
- Compute:
- $c_1 = \mathbf{r}^T \mathbf{A} \in \mathbb{Z}_q^n$
- $c_2 = \mathbf{r}^T \mathbf{b} + \left\lfloor \frac{q}{2} \right\rfloor \mu \in \mathbb{Z}_q$
- $Enc(\mu)=(c_1, c_2)$.
- $Dec_\mathbf{s}((c_1, c_2))$ ciphertext $(c_1, c_2)$, secret key $\mathbf{s}$:
- $v = c_2 - c_1 \cdot \mathbf{s} = \mathbf{r}^T\mathbf{b} + \left\lfloor \frac{q}{2} \right\rfloor \mu - \mathbf{r}^T\mathbf{A}\mathbf{s}
= \mathbf{r}^T \mathbf{e} + \left\lfloor \frac{q}{2} \right\rfloor \mu$
- $|\mathbf{r}^T \mathbf{e}| < \frac{q}{4} \quad \Longrightarrow \quad\mu =
\begin{cases}
0, & \text{if } v < \frac{q}{2},\\[3mm]
1, & \text{if } v \geq \frac{q}{2}.
\end{cases}$

## GSW

The GSW symmetric encryption scheme is an LWE-based FHE, uses natural matrix operations for both encryption and homomorphic evaluation.

- Parameters and Preliminaries
- **Modulus and Gadget setup:**
- Let $q$ be the modulus.
- Define
$$
\ell = \lceil \log_2 q \rceil.
$$
- The **gadget vector** is
$$
g = (1,2,4,\dots,2^{\ell-1}) \in \mathbb{Z}_q^\ell.
$$
Notably, the penultimate entry $2^{\ell-2}$ lies in $[q/4, q/2)$ modulo $q$.

- **Randomized decomposition:** There exists an efficiently computable randomized function
$$
g^{-1}: \mathbb{Z}_q \to \mathbb{Z}^\ell,
$$
such that for any $a \in \mathbb{Z}_q$, a sample $x \leftarrow g^{-1}(a)$ satisfies
$$
\langle g, x \rangle = a,
$$
and $x$ is subgaussian with constant parameter.
- Extend this operator entrywise to matrices: for any $A \in \mathbb{Z}_q^{n \times m}$, define
$$
G^{-1}(A)
$$
as the matrix obtained by applying $g^{-1}$ to each entry.
- Define the block gadget matrix
$$
G = g^T \otimes I_n \in \mathbb{Z}_q^{n \times n\ell},
$$
so that for any $X = G^{-1}(A)$ we have
$$
G \cdot X = A.
$$

- Other params:
- Dimension parameter $n$.
- Error distribution $\chi$ (assumed subgaussian).
- The message space is formally the ring of integers $\mathbb{Z}$, meaning any integer can be encrypted. However, in practical applications such as bootstrapping, messages are typically restricted to $\{0,1\} \subset \mathbb{Z}$.
- The ciphertext space is
$$
\mathcal{C} = \mathbb{Z}_q^{n \times n\ell}.
$$

- KeyGen
- Sample $\bar{s} \leftarrow \chi^{n-1}$ and set
$$
s = (\bar{s}, 1) \in \mathbb{Z}^n.
$$

- Enc
- To encrypt a message $\mu \in \mathbb{Z}$:
- Sample a random matrix $\bar{C} \in \mathbb{Z}_q^{(n-1) \times n\ell}$.
- Sample an error vector $e \leftarrow \chi^m$ (with appropriate dimensions).
- Compute $b^T = e^T - \bar{s}^T \bar{C}$ modulo $q$.
- Construct
$$
C = \begin{pmatrix} \bar{C} \\ b^T \end{pmatrix} + \mu\, G \in \mathbb{Z}_q^{n \times n\ell}.
$$
- Note that this ensures
$$
s^T C = e^T + \mu \cdot s^T G \pmod{q},
$$
so that the message $\mu$ is “embedded” via $G$ and masked by the error.

- Dec: Decrypt ciphertext $C$ and secret key $s$:
- Let $\mathbf{c}$ be the **penultimate column** of $C$.
- Compute the inner product:
$$
x = \langle s, \mathbf{c} \rangle \mod q.
$$
- Output $\mu = \lfloor x \rfloor_2$, where $\lfloor \cdot \rfloor_2: \mathbb{Z}_q \to \{0,1\}$
is a rounding function that decides whether $x$ is **closer to**:
- $0 \mod q$ (output $0$), or
- $2^{\ell-2} \mod q$ (output $1$), (the penultimate entry of $g$).

- **Add:**
- $C_{+} = C_1 + C_2$

- **Mul:**
- $C_{\times} = C_1 \cdot G^{-1}(C_2).$

-----------------

# RLWE
We work in the ring $R = \mathbb{Z}[x]/\langle f(x) \rangle,$ where $f(x)$ is a monic irreducible polynomial. In many applications, $f(x)$ is chosen to be a cyclotomic polynomial. For example, if $f(x)=\Phi_m(x)$ is the $m$th cyclotomic polynomial, then its degree is $n=\varphi(m)$, where $\varphi$ is Euler's totient function. Reducing the coefficients modulo $q$ gives $R_q = \mathbb{Z}_q[x]/(f(x))$.
- Params:
- $n$: security parameter (degree of the polynomial ring),
- $q$: prime modulus,
- $f(x) \in \mathbb{Z}[x]$: monic irreducible polynomial of degree \(n\),
- $R_q = \mathbb{Z}_q[x]/(f(x))$
- $\chi$: error distribution (e.g., a discrete Gaussian).
- $KeyGen(n,q,f,\chi)$:
- $s \xleftarrow{rnd} R_q \quad$ (secret, typically with small coefficients)
- $a \xleftarrow{rnd} R_q$
- $e \sim \chi \in R_q$
- $b = a\cdot s + e \in R_q$
- $(sk, pk) = (s, (a,b))$
- $Enc(\mu)$ encrypt a bit $\mu \in \{0,1\}$:
- $r \xleftarrow{rnd} R_q$
- Compute:
- $c_1 = a\cdot r \in R_q$
- $c_2 = b\cdot r + \left\lfloor \frac{q}{2} \right\rfloor \mu \in R_q$
- $Enc(\mu) = (c_1, c_2)$.
- $Dec_s((c_1,c_2))$ with ciphertext $(c_1,c_2)$ and secret key $s$:
- Compute: $v = c_2 - s\cdot c_1 = b\cdot r + \left\lfloor \frac{q}{2} \right\rfloor \mu - s\cdot (a\cdot r)
= e\cdot r + \left\lfloor \frac{q}{2} \right\rfloor \mu$
- $|e\cdot r| < \frac{q}{4} \quad \Longrightarrow \quad \mu =
\begin{cases}
0, & \text{if } v < \frac{q}{2},\\[3mm]
1, & \text{if } v \geq \frac{q}{2}.
\end{cases}$

## Rotation
- Let
$$
C_m = (c_1, c_2) \in R_q^2
$$
be an encryption of $m(x)$ under key $s$. Also, let $p \in \mathbb{Z}$ (with $0 \leq p < n$) be a rotation offset and let $C_p$ be an encryption of $p$.
- Compute:
$$
C_{\text{rot}},
$$
which encrypts the rotated polynomial
$$
m'(x) = x^p \cdot m(x) \mod f(x),
$$

### BlindRotation
- **Input:**
- $C_m = (c_1, c_2) \in R_q^2$, an encryption of $m(x) \in R_q$.
- $C_p$, an encryption of the rotation offset $p$.
- **Output:**
- $C_{\text{rot}} \in R_q^2$, an encryption of
$$
m'(x) = x^p \cdot m(x) \mod f(x).
$$

- **Steps:**
- Define the function
$$
\Phi(p) = x^p \mod f(x).
$$
- Compute
$$
C_{x^p} \gets \text{EvalFunc}(C_p, \Phi),
$$
where $\text{EvalFunc}$ denotes a homomorphic evaluation (for example, via a lookup table or circuit) that, given an encryption of $p$, produces an encryption of the monomial $x^p$ in $R_q$.

- **Multiplication:**
- Compute
$$
C_{\text{temp}} \gets \text{EvalMult}(C_m, C_{x^p}),
$$
which yields a ciphertext encrypting
$$
x^p \cdot m(x) \mod f(x).
$$
- Here, $\text{EvalMult}$ denotes the standard homomorphic multiplication operation in $R_q$.

- **Key Switching:**
- To maintain the standard RLWE ciphertext format and control noise growth, apply key switching:
$$
C_{\text{rot}} \gets \text{KeySwitch}(C_{\text{temp}}).
$$

# GLWE
We work in the polynomial ring:
$$
R = \mathbb{Z}[x]/\langle f(x) \rangle,
$$
where $f(x)$ is a monic irreducible polynomial. In many applications, $f(x)$ is chosen to be a cyclotomic polynomial. For example, if $f(x) = \Phi_m(x)$ is the $m$th cyclotomic polynomial, then its degree is $n = \varphi(m)$, where $\varphi$ is Euler's totient function.

Reducing the coefficients modulo $q$ gives the ring:
$$
R_q = \mathbb{Z}_q[x]/(f(x)).
$$
GLWE generalizes RLWE by replacing the secret key and ciphertexts with vectors of polynomials.

- Params
- $n$: Security parameter (degree of the polynomial ring).
- $k$: Dimension (number of polynomials in the secret key).
- $q$: Prime modulus.
- $f(x) \in \mathbb{Z}[x]$: Monic irreducible polynomial of degree $n$.
- $R_q = \mathbb{Z}_q[x]/(f(x))$.
- $\chi$: Error distribution (e.g., a discrete Gaussian).

- $\text{KeyGen}(n,k,q,f,\chi)$**
- The secret key is a **vector of polynomials**:
$$
s = (s_1, s_2, ..., s_k) \xleftarrow{rnd} R_q^k \quad \text{(typically with small coefficients)}
$$
- A random **public key component**:
$$
A = (a_1, a_2, ..., a_k) \xleftarrow{rnd} R_q^k
$$
- A noise polynomial:
$$
e \sim \chi \in R_q
$$
- The second public key component:
$$
b = \sum_{i=1}^{k} a_i \cdot s_i + e \in R_q
$$
- The public-private key pair:
$$
(sk, pk) = (s, (A, b)).
$$

- $\text{Enc}(\mu)$**
- To encrypt a bit $\mu \in \{0,1\}$:
1. Sample a **random masking vector**:
$$
r = (r_1, r_2, ..., r_k) \xleftarrow{rnd} R_q^k
$$
2. Compute ciphertext components:
- $$
c_1 = \sum_{i=1}^{k} a_i \cdot r_i \in R_q
$$
- $$
c_2 = b \cdot r + \left\lfloor \frac{q}{2} \right\rfloor \mu \in R_q
$$

- The **ciphertext** is:
$$
\text{Enc}(\mu) = (c_1, c_2).
$$

- $\text{Dec}_s((c_1,c_2))$**
- Given ciphertext $(c_1, c_2)$ and secret key $s = (s_1, ..., s_k)$:
1. Compute:
$$
v = c_2 - \sum_{i=1}^{k} s_i \cdot c_1
$$

2. Expanding:
$$
v = b \cdot r + \left\lfloor \frac{q}{2} \right\rfloor \mu - \sum_{i=1}^{k} s_i \cdot \left( \sum_{j=1}^{k} a_j \cdot r_j \right)
$$

- Since $b = \sum_{j=1}^{k} a_j \cdot s_j + e$, we simplify:
$$
v = e \cdot r + \left\lfloor \frac{q}{2} \right\rfloor \mu.
$$

----
| Component | LWE | RLWE | GLWE |
|------------------------|----|------|------|
| **Secret key $S$** | Vector $S \in \mathbb{Z}_q^n$ | Polynomial $S(X) \in \mathbb{Z}_q[X] / (X^N + 1)$ | Vector of polynomials $S = (S_1(X), ..., S_k(X)) \in (\mathbb{Z}_q[X] / (X^N + 1))^k$ |
| **Ciphertext $A$** | Vector $A \in \mathbb{Z}_q^n$ | Polynomial $A(X) \in \mathbb{Z}_q[X] / (X^N + 1)$ | Vector of polynomials $A = (A_1(X), ..., A_k(X)) \in (\mathbb{Z}_q[X] / (X^N + 1))^k$ |
| **Ciphertext $B$** | Scalar $B \in \mathbb{Z}_q$ | Polynomial $B(X) \in \mathbb{Z}_q[X] / (X^N + 1)$ | Polynomial $B(X) \in \mathbb{Z}_q[X] / (X^N + 1)$ |
| **Message $m$** | Scalar $m \in \mathbb{Z}_p$, where $p$ is small (often $\{0,1\}$ for binary encryption) | Polynomial $m(X) \in \mathbb{Z}_p[X] / (X^N + 1)$ | Polynomial $m(X) \in \mathbb{Z}_p[X] / (X^N + 1)$ |
| **Error $e$** | Small integer $e \in \mathbb{Z}$ sampled from a Gaussian or uniform distribution | Small polynomial $E(X) \in \mathbb{Z}[X] / (X^N + 1)$ sampled from a Gaussian or uniform distribution | Small polynomial $E(X) \in \mathbb{Z}[X] / (X^N + 1)$ sampled from a Gaussian or uniform distribution |

----

## BGV
We work in the rings $R_q=\mathbb{Z}_q[x]/(f(x))$ for ciphertexts, and $R_t=\mathbb{Z}_t[x]/(f(x))$ for plaintexts.

- Params:
- **$n$**: Ring degree.
- **$q$**: Ciphertext modulus (large).
- **$t$**: Plaintext modulus (small).
- **$f(x)$**: Polynomial of degree $n$.
- **$\Delta$**$=\left\lfloor\frac{q}{t}\right\rfloor$: Scaling factor.
- **$\chi$**: Error distribution.

- $KeyGen()$:
- Sample $s$ as a polynomial in $R_q$, with coefficients drawn from a small-coefficient distribution $\chi_s$: $s \xleftarrow{rnd} \chi_s \in R_q,$ where each coefficient $s_i$ is chosen from:
- Ternary distribution: $s_i \in \{-1,0,1\}$
- Gaussian distribution: $s_i \sim \mathcal{N}(0, \sigma^2)$ (rounded to integers)
- **Sample:**
$a\xleftarrow{rnd}R_q$
- $e\sim\chi$
- $b=a\cdot s+t\cdot e\in R_q.$
- $(sk, pk) = (s, (b,-a))$

- $Enc(m)$ $m\in R_t$:
- $r \xleftarrow{rnd} \chi_s \in R_q,$
- $e_0,e_1\sim\chi$.
- $c=(c_0,c_1)\in\bigl(R_q\times R_q\bigr)$:
- $c_0=b\cdot r+ t\cdot e_0 + m$,
- $c_1=-a\cdot r+t\cdot e_1$.
- $Dec(c)$
- $m=c_0+s\cdot c_1 \mod q \mod t.$

- $Add(c_a,c_b)$: $c_a=(c_{a_0},c_{a_1}),\;c_b=(c_{b_0},c_{b_1})$
- $c_{+}=(c_{a_0}+c_{b_0},\;c_{a_1}+c_{b_1})$
- $Mul(c_a,c_b)$:
- $c_{\times 0} = c_{a_0} \cdot c_{b_0}$
- $c_{\times 1} = c_{a_0} \cdot c_{b_1} + c_{a_1} \cdot c_{b_0}$
- $c_{\times 2} = c_{a_1} \cdot c_{b_1}$
- Return $c_{\times} = (c_{\times 0}, c_{\times 1}, c_{\times 2})$
- **Relinearization** via Key switching:
- Decomposition: Write the high-degree component $c_{\times 2}$ in base $T$:
- $c_{\times 2} \;=\;\sum_{i=0}^{\lfloor \log_T q \rfloor} T^i \cdot c_{\times 2}^{(i)} \mod q,$ where $c_{\times 2}^{(i)}$ denotes the $i$th digit of $c_{\times 2}$ in base $T$ (not exponentiation).
- For each digit $c_{\times 2}^{(i)}$, compute the hint:
- $(ek_0^{(i)},\,ek_1^{(i)}) \;=\;\Bigl(a^{(i)}\,s \;+\; t\,e^{(i)} \;+\; T^i\,s,\; -a^{(i)}\Bigr),$ with $a^{(i)} \xleftarrow{rnd} R_q$ and $e^{(i)}\sim\chi$.
- Key switching: Form the new ciphertext by combining the hints:
- $c_{\times 0}' \;=\; c_{\times 0} \;+\; \sum_{i=0}^{\lfloor \log_T q \rfloor} ek_0^{(i)} \cdot c_{\times 2}^{(i)},$
- $c_{\times 1}' \;=\; c_{\times 1} \;+\; \sum_{i=0}^{\lfloor \log_T q \rfloor} ek_1^{(i)} \cdot c_{\times 2}^{(i)}.$
- Using the above relations, we obtain the linear equation:
- $c_{\times 0}' + s\,c_{\times 1}' \;=\; c_{\times 0} + s\,c_{\times 1} + c_{\times 2}\,s^2 + t \sum_{i=0}^{\lfloor \log_T q \rfloor} e^{(i)} c_{\times 2}^{(i)}.$
- Return $c_{\times}' = (c_{\times 0}', c_{\times 1}')$
- **Modulus switching**:
- **Params**: Let $Q$ be the initial (large) modulus and $q$ the target (smaller) modulus, with $q < Q$. The goal is to move from modulus $Q$ to $q$ to reduce the noise of a ciphertext $(c_0, c_1)$ while preserving decryption modulo $t$.
- Scale down each ciphertext component:
- $c'_i = c_i \cdot \frac{q}{Q}, \quad i \in \{0,1\}.$
- To ensure correctness, we introduce a correction term $\delta_i$ that satisfies:
- $\delta_i \equiv 0 \mod t, \quad c_i + \delta_i \equiv 0 \mod \frac{Q}{q}.$
- A suitable choice is: $\delta_i = t \cdot \bigl[-c_i \cdot t^{-1}\bigr]_{Q/q},$ where $t^{-1}$ is the modular inverse of $t$ modulo $Q/q$.
- The final components are: $\tilde{c}_i = \frac{q}{Q} (c_i + \delta_i), \quad i \in \{0,1\}.$

- **Relinearization** via Modulus switching:
- **Goal**: Convert a ciphertext $c_{\times} = (c_{\times 0}, c_{\times 1}, c_{\times 2})$ from a higher-degree form (after multiplication) into a two-component ciphertext $c_{\times} = (c_{\times 0}, c_{\times 1})$ in a smaller modulus $q$, reducing its size while preserving decryption.
- Generate the hint: $(ek_0, ek_1) = \bigl(a \cdot s + t e + \frac{Q}{q} s^2, -a\bigr) \mod Q,$ where $a \xleftarrow{rnd} R_Q$ and $e \sim \chi$.
- Relinearization:
- $\hat{c}_0 = \frac{Q}{q} c_{\times 0} + ek_0 \cdot c_{\times 2} \mod Q,$
- $\hat{c}_1 = \frac{Q}{q} c_{\times 1} + ek_1 \cdot c_{\times 2} \mod Q,.$
- Scale the ciphertext $(\hat{c}_0, \hat{c}_1)$ from modulus $Q$ to $q$:
$$
c_i' = \frac{q}{Q} \bigl( \hat{c}_i + \delta_i \bigr), \quad i \in \{0,1\},
$$
where $\delta_i = t \cdot \bigl[-c_i \cdot t^{-1}\bigr]_{Q/q},$

- After key switching, the new ciphertext $c_{\times}' = (c_{\times 0}', c_{\times 1}')$ satisfies:
$$
c_{\times 0}' + s c_{\times 1}' = c_{\times 0} + s c_{\times 1} + c_{\times 2} s^2 + \frac{q}{Q} \bigl( t c_{\times 2} \cdot e + \delta_0 + \delta_1 s).
$$
## BFV
We work in the rings $R_q = \mathbb{Z}_q[x]/(f(x))$ for ciphertexts and $R_t = \mathbb{Z}_t[x]/(f(x))$ for plaintexts, typically with $n = \deg(f(x))$ being a power of 2. We define $\Delta = \left\lfloor \tfrac{q}{t} \right\rfloor$ as the scaling factor.

- **Params**:
- $n$: Ring dimension.
- $q$: Ciphertext modulus (large).
- $t$: Plaintext modulus (small).
- $f(x)$: A polynomial of degree $n$ (e.g., $x^n + 1$).
- $\Delta = \left\lfloor \tfrac{q}{t} \right\rfloor$: Scaling factor.
- $\chi$: Error distribution (e.g., discrete Gaussian).

- **KeyGen()**:
1. Sample $s \xleftarrow{rnd} \chi_s \in R_2$ or a small-coefficient distribution in $R_q$ (e.g., ternary or Gaussian).
2. Sample $a \xleftarrow{rnd} R_q$ uniformly.
3. Sample error $e \sim \chi$.
4. Compute
$$
b \;=\; \bigl(-\,a \cdot s \;-\; e \bigr) \;\bmod q,\quad
$$
5. Return $(sk, pk) = (s, (b, a))$

- **Enc($m$)** for $m \in R_t$:
1. Sample small polynomials $u \xleftarrow{rnd}\,\chi_s$, $e_1,e_2 \sim \chi$.
2. Form the ciphertext $(c_1, c_2) \in R_q \times R_q$:
$$
c_1 \;=\; b \cdot u \;+\; e_1 \;+\; \Delta \,m,
$$
$$
c_2 \;=\; a \cdot u \;+\; e_2.
$$

- **Dec($c$)** for $c=(c_1,c_2)$:
1. Compute
$$
\tilde{m}
\;=\; c_1 \;+\; s \, c_2
\;\bmod q.
$$
2. Recover the plaintext:
$$
m
\;=\;
\left\lfloor \frac{t}{q} \,\tilde{m} \right\rceil
\;\bmod t,
$$

- $Add(c_a, c_b)$:
- For $c_a=(c_{a_0},c_{a_1})$ and $c_b=(c_{b_0},c_{b_1})$, compute:
- $c_{+} = (c_{a_0} + c_{b_0},\; c_{a_1} + c_{b_1}) \mod q.$
- $Mul(c_a,c_b)$:
- Let $c_a=(c_{a_0},c_{a_1})$ and $c_b=(c_{b_0},c_{b_1})$.
- Compute the tensor product and scale by $\frac{t}{q}$ with rounding:
$$c_{\times 0} = \left\lfloor \frac{t\cdot (c_{a_0}\cdot c_{b_0})}{q} \right\rceil \mod q,$$
$$c_{\times 1} = \left\lfloor \frac{t\cdot (c_{a_0}\cdot c_{b_1}+ c_{a_1}\cdot c_{b_0})}{q} \right\rceil \mod q,$$
$$c_{\times 2} = \left\lfloor \frac{t\cdot (c_{a_1}\cdot c_{b_1})}{q} \right\rceil \mod q.$$
- Return the ciphertext $c_\times = (c_{\times 0}, c_{\times 1}, c_{\times 2})$.

- **Relinearization**:
- **Goal**: Reduce a three-component ciphertext $c_{\times} = (c_{\times 0},\,c_{\times 1},\,c_{\times 2})$ (resulting from $Mul$) back to two components $(c_0',\,c_1')$. We want:
$$
\bigl[c_{\times 0} + s\,c_{\times 1} + s^2\,c_{\times 2}\bigr]_q
\;\approx\;
\bigl[c_0' + s\,c_1' + r\bigr]_q.
$$
- **Evaluation key**:
- To handle $s^2$, generate $(ek_0,\,ek_1)$ such that
$(ek_0,\,ek_1)\;=\;\Bigl(\,-\bigl(a\,s + e\bigr) \;+\; s^2,\;a\Bigr) \;\bmod q.$
- Observe that $ek_0 + s\,ek_1\;=\;\bigl(-a\,s - e + s^2\bigr) + a\,s\;=\;s^2 - e.$
- **Relinearize**:
- Compute new ciphertext components:
$$
c_0'
\;=\;
\bigl(c_{\times 0} + ek_0 \,\cdot\, c_{\times 2}\bigr) \;\bmod q,
$$
$$
c_1'
\;=\;
\bigl(c_{\times 1} + ek_1 \,\cdot\, c_{\times 2}\bigr) \;\bmod q.
$$
- $c_{\times}' = (c_0',\,c_1')$
- **Problem**: Since $c_{\times 2}$ is a random element in $R_q$, the noise $e_0$ will be magnified too much, resulting in a bad approximation of $c_{\times 2} \cdot s^2$ and causing a huge error $r$.
- **Relinearize** via Key switching:
- Choose a base $T$ and re-write $c_{\times 2}$ as $c_{\times 2} = \sum_{i=0}^{\ell} T^i\,c_{\times 2}^{(i)} \mod q, \quad \ell = \lfloor \log_T(q) \rfloor,$ where $c_{\times 2}^{(i)}$ denotes the $i$th digit of $c_{\times 2}$ in base $T$ (not exponentiation).
- Generate evaluation keys:
$$
rlk[i] = \Bigl( \bigl[ - (a_i\,s + e_i) + T^i\,s^2 \bigr]_q,\, a_i \Bigr).
$$
- Compute:
$$
c_0' = \Bigl[ c_{\times 0} + \sum_{i=0}^{\ell} rlk[i]_0 \cdot c_2^{(i)} \Bigr]_q,
$$
$$
c_1' = \Bigl[ c_{\times 1} + \sum_{i=0}^{\ell} rlk[i]_1 \cdot c_2^{(i)} \Bigr]_q.
$$
- **Relinearize** via Modulus switching:
- Work modulo $p\cdot q$ instead of $q$:
$$
rlk = \Bigl( \bigl[ - (a\,s + e) + p\,s^2 \bigr]_{p\cdot q},\, a \Bigr).
$$
- Compute:
$$
c_{2,0}' = \Bigl[ \left\lfloor \frac{c_{\times 2} \cdot rlk_0}{p} \right\rceil \Bigr]_q, \quad
c_{2,1}' = \Bigl[ \left\lfloor \frac{c_{\times 2} \cdot rlk_1}{p} \right\rceil \Bigr]_q.
$$
- Final ciphertext:
$$
c_0' = c_{\times 0} + c_{2,0}', \quad c_1' = c_{\times 1} + c_{2,1}'.
$$

- Trade-offs:
- A larger $T$ reduces key size but increases noise.
- $p$ controls extra noise; larger $p$ minimizes error growth.

## CLPX

The scheme is built on top of the Fan–Vercauteren (FV) homomorphic encryption approach but modifies how the plaintext is represented.
<!--
Instead of using a small integer modulus $t$, it replaces $t$ with the polynomial $x - b$. Doing so gives a plaintext space isomorphic t o
$$
\mathbb{Z}/(b^n + 1)\mathbb{Z},
$$
which helps achieve very large effective plaintext moduli and thus supports high-precision (large or fractional) data without wrap-around in the coefficients
-->

### 1. Params

- Ciphertext:
$$
R_q \;=\; \mathbb{Z}_q[x]\;/\;(x^n + 1),\quad \text{where $n$ is a power of 2.}
$$
Here, $q$ is a large integer modulus.

- Plaintext:
$$
\mathcal{M} \;=\; \mathbb{Z}\bigl/\!\bigl(b^n + 1\bigr)\mathbb{Z}.
$$
The parameter $b$ is a small positive integer (e.g., 2, 3, 4, …).

- $\chi$: A discrete Gaussian (or sometimes a ternary distribution) used for sampling noise and secret-key elements.

- $\sigma$: Standard deviation for the Gaussian error.
- $w$: A base for “digit” or “key” decomposition (used in relinearization).
- $\ell = \lfloor \log_w(q) \rfloor$: Number of decomposition levels.

### 2. KeyGen

Same key-generation approach as FV/BFV:

1. $(sk)$:
- Sample $s \in R_q$ with small coefficients (e.g., ternary or Gaussian).
2. $(pk)$:
- Choose a “random-looking” $a \in R_q$ uniformly at random.
- Sample error $e \sim \chi$.
- Compute $p_0 \equiv -\,\bigl(a\cdot s + e\bigr)\pmod{q}.$
- Set $pk = (p_0,\;a) \in R_q \times R_q.$
3. $(evk)$:
- For each index $i$ (with $i = 0, \dots, \ell$, where $\ell = \lfloor \log_w(q) \rfloor$ for a chosen base $w$):
- Sample $a_i$ uniformly from $R_q$.
- Sample an error $e_i$ from the error distribution $\chi$.
- Compute
$$
\text{evk}[i] \;=\; \Bigl( \bigl[-\bigl(a_i\,s + e_i\bigr) + w^i\,s^2 \bigr]_q,\; a_i \Bigr) \in R_q \times R_q.
$$
- The complete evaluation key is the collection
$$
\text{evk} = \{ \text{evk}[0],\, \text{evk}[1],\, \dots,\, \text{evk}[\ell] \}.
$$

### 3. Encoding

- Hat encoding** ($\hat{m}$):
A message integer $m$ (or fractional number, after a separate “fractional encoder”) is turned into a polynomial $\hat{m}(x)$ so that
$$
\hat{m}(b) \;\equiv\; m \quad\bigl(\text{mod }\,b^n+1\bigr).
$$
- Polynomial degrees range at most up to $n-1$.
- Coefficients remain small (usually no bigger than $\frac{b+1}{2}$ in absolute value).

- Plaintext “Evaluation”:
Decryption ultimately evaluates the polynomial $\hat{m}(x)$ at $x = b$.

### 4. Encryption

Given a message $m \in \mathcal{M}$ (which is “encoded” as $\hat{m}$):

1. Sample small polynomials:
- $u \in R_q$ (ternary or small Gaussian).
- $e_0, e_1 \sim \chi$.
2. Compute ciphertext $\mathbf{ct} = (c_0, c_1)$:
$$
c_0 \;\equiv\; \Delta_b \,\hat{m}(x)\;+\; p_0 \cdot u \;+\; e_0 \quad \bmod{\,q},
$$
$$
c_1 \;\equiv\; p_1 \cdot u \;+\; e_1 \quad \bmod{\,q},
$$
where
$$
\Delta_b \;\approx\; -\,\frac{q}{\,b^n+1\,}\,(x^{n-1} + b\,x^{n-2} + \dots + b^{n-1}).
$$
(This $\Delta_b$ ensures that evaluation at $x=b$ after decryption isolates $m$.)

### 5. Decryption

Given $\mathbf{ct} = (c_0,c_1)$ and secret key $s$:

1. Compute
$$
\tilde{m}(x)
\;\equiv\;
c_0 \;+\; s \,\cdot\, c_1
\quad \bmod{\,q}.
$$

2. Evaluate
$$
\hat{M} \;=\; \left\lfloor \frac{x - b}{q}\,\tilde{m}(x)\right\rceil
\quad (\text{coefficient-wise rounding}).
$$

3. The decoded integer (or fraction) is
$$
\hat{M}(b) \;\equiv\; m
\quad \bigl(\text{mod } b^n + 1\bigr).
$$

Invariant noise in $\hat{M}$ must stays below 1/2 in a chosen norm, so that rounding recovers the correct message.

### 6. Homomorphic Operations

1. Add $\bigl((c_0,c_1), (d_0,d_1)\bigr)$:
$$
c_{\text{add}}
\;=\;
(\,c_0 + d_0,\; c_1 + d_1\,) \quad \bmod{\,q}.
$$
- Decodes to $\hat{m}_1 + \hat{m}_2$.

2. Multiply:
$$
(c_0,c_1),\,(d_0,d_1)
\;\mapsto\;
(c_0d_0, \;c_0d_1 + c_1d_0,\; c_1d_1),
$$
but scaled by $\frac{x-b}{q}$. Specifically,
$$
c_0' = \Bigl\lfloor\tfrac{x-b}{q}\bigl(c_0 \cdot d_0\bigr)\Bigr\rceil,\;
c_1' = \Bigl\lfloor\tfrac{x-b}{q}\bigl(c_0 \cdot d_1 + c_1 \cdot d_0\bigr)\Bigr\rceil,\;
c_2' = \Bigl\lfloor\tfrac{x-b}{q}\bigl(c_1 \cdot d_1\bigr)\Bigr\rceil.
$$
$\mathbf{ct}' = (c_0', c_1', c_2')$.

3. Relinearization $\mathbf{ct}' \to \mathbf{ct}_{\text{mult}}$:
- Use the evaluation key to map the extra component $c_2'$ back into a two-component ciphertext:
$$
(c_0',\, c_1')\;\mapsto\;
\begin{cases}
c_0'' = c_0' \;+\;\sum_{i=0}^{\ell}\bigl(\text{evk}[i][0]\bigr)\,c_2'^{(i)},\\
c_1'' = c_1' \;+\;\sum_{i=0}^{\ell}\bigl(\text{evk}[i][1]\bigr)\,c_2'^{(i)},
\end{cases}
$$
where $c_2'^{(i)}$ are the base-$w$ “digits” of $c_2'$ in $R_q$.

Hence, $\mathbf{ct}_{\text{mult}} = (c_0'',\,c_1'')$ decrypts to $\hat{m}_1 \cdot \hat{m}_2 \bigr(\bmod\,b^n+1\bigl)$, i.e., the product of the messages.

### 7. Fractional / High-Precision Encoding

1. Reserves some polynomial “digits” (in base $b$) for the integer part and some for the fractional part.
2. Ensures:
$$
\hat{m}(b)
\;\;\approx\;\;
\text{(integer part)} \;+\; \frac{\text{(fractional part)}}{b^{(\text{# fractional digits})}}.
$$
3. This prevents any loss in precision in the polynomial coefficients (up to a configured limit) and allows deeper homomorphic computations on rational data without wrap-around.

### 8. Noise Analysis & Advantages

- **Noise growth:**
Each homomorphic operation (especially multiplication) increases the “invariant noise.”
- **Better precision:**
By using $x-b$ in place of a small integer modulus $t$, the maximum coefficient size (plaintext modulus) is effectively $b^n + 1$, which can be huge for large $n$. This allows for deeper computations without forcing big primes $q$.

---

## GBFV - Generalized BFV
- We work in the polynomial ring:
$$
R = \mathbb{Z}[x]/\langle f(x) \rangle,
$$
where $f(x)$ is a monic irreducible polynomial. In many applications, $f(x)$ is chosen to be a cyclotomic polynomial. For example, if $f(x) = \Phi_m(x)$ is the $m$th cyclotomic polynomial, then its degree is $n = \varphi(m)$, where $\varphi$ is Euler's totient function.

- Reducing the coefficients modulo $q$ gives the ring:
$$
R_q = \mathbb{Z}_q[x]/(f(x)).
$$
Unlike standard BFV, which operates over a fixed integer plaintext modulus $p$, GBFV generalizes BFV by replacing $p$ with an arbitrary polynomial modulus $t(x)$. This allows for better noise control and enables bootstrappable homomorphic operations.

- Params
- $n$: Security parameter (degree of the polynomial ring).
- $q$: Prime modulus.
- $f(x) \in \mathbb{Z}[x]$: Monic irreducible polynomial of degree $n$.
- $R_q = \mathbb{Z}_q[x]/(f(x))$.
- $t(x) \in \mathbb{Z}[x]$: Plaintext modulus, an arbitrary polynomial.
- $R_t = \mathbb{Z}[x]/(f(x), t(x))$ (plaintext space).
- $\chi$: Error distribution (e.g., a discrete Gaussian).

- $\text{KeyGen}(n,q,f,t,\chi)$
- The secret key is a random polynomial:
$$
s \xleftarrow{rnd} R_q \quad \text{(typically with small coefficients)}
$$
- A random public key component:
$$
a \xleftarrow{rnd} R_q
$$
- A noise polynomial:
$$
e \sim \chi \in R_q
$$
- The second public key component:
$$
b = a \cdot s + e \in R_q
$$
- The public-private key pair:
$$
(sk, pk) = (s, (a, b)).
$$

- $\text{Enc}(\mu)$
- To encrypt a plaintext $\mu(x) \in R_t$:

1. Sample a random masking polynomial:
$$
r \xleftarrow{rnd} R_q
$$
2. Compute ciphertext components:
- $$
c_1 = a \cdot r \in R_q
$$
- $$
c_2 = b \cdot r + \Delta \cdot \mu(x) + e' \in R_q
$$
where $\Delta = \lfloor q / t(x) \rfloor$ is a scaling factor, and $e'$ is an additional noise term.

- The ciphertext is:
$$
\text{Enc}(\mu) = (c_1, c_2).
$$

- $\text{Dec}_s((c_1,c_2))$
- Given ciphertext $(c_1, c_2)$ and secret key $s$:

1. Compute:
$$
v = c_2 - s \cdot c_1
$$

2. Expanding:
$$
v = (b \cdot r + \Delta \cdot \mu + e') - s \cdot (a \cdot r)
$$
Since $b = a \cdot s + e$, we substitute:
$$
v = e \cdot r + \Delta \cdot \mu + e'.
$$

3. Recover plaintext:
- Since $|e \cdot r + e'| \ll \Delta$, we can correctly decode:
$$
\mu = \left\lfloor \frac{v}{\Delta} \right\rfloor.
$$

### How GBFV Generalizes BFV
| Component | BFV | GBFV |
|---------------------|----------------------------------|----------------------------------|
| Plaintext space | $R_t = \mathbb{Z}[x]/(\Phi_m(x), p)$ | $R_t = \mathbb{Z}[x]/(\Phi_m(x), t(x))$ |
| Ciphertext modulus | $R_q = \mathbb{Z}[x]/(\Phi_m(x), q)$ | $R_q = \mathbb{Z}[x]/(\Phi_m(x), q)$ |
| Encryption | $c_0 + c_1 s = \Delta \cdot m + e$ | $c_0 + c_1 s = \Delta \cdot m + e$ |
| Decryption | $m = \lfloor (c_0 + c_1 s) / \Delta \rfloor$ | $m = \lfloor (c_0 + c_1 s) / \Delta \rfloor$ |

## HEAAN

- Params
- $n$: Ring degree (typically a power of 2).
- $q$: Ciphertext modulus (decreases during rescaling).
- $\Delta$: Scaling factor for encoding, typically $\Delta = 2^d$ for some $d$.
- $f(x)$: Polynomial of degree $n$, defining the ring $R_q = \mathbb{Z}_q[x]/(f(x))$.
- $\chi$: Error distribution (e.g., discrete Gaussian).

- KeyGen
- Sample $s \xleftarrow{rnd} \chi_s \in R_2$ or a small-coefficient distribution in $R_q$ (e.g., ternary or Gaussian).
- **Sample** $a \xleftarrow{\text{rnd}} R_q$ (uniformly).
- **Sample noise** $e \sim \chi$.
- **Compute the public key**:
$$
b = - (a \cdot s + e) \in R_q.
$$
- **Output**:
- Public key: $\text{PK} = (a, b)$.
- Secret key: $\text{SK} = s$.

### Encoding and Decoding

#### Canonical embedding
- The canonical embedding maps elements of the polynomial ring $R_q$ into a structured space $\mathbb{C}^{n/2}$, allowing CKKS to perform arithmetic on real and complex numbers efficiently.
- Given a polynomial $m(x) \in R_q$, the embedding $\sigma: R_q \to \mathbb{C}^{n/2}$ is defined using the **roots of unity**:
$$
\sigma(m) = (m(\zeta_1), m(\zeta_2), \dots, m(\zeta_{n/2})),
$$
where $\zeta_i$ are the **primitive $n$-th roots of unity** in $\mathbb{C}$.
- CKKS encodes complex numbers into polynomials over $R_q$, enabling arithmetic on encrypted floating-point values.

#### Encoding
- Given a complex vector $\mathbf{z} \in \mathbb{C}^{n/2}$:
1. Apply the inverse canonical embedding:
$$
\mathbf{z}_\mathbb{H} = \pi^{-1}(\mathbf{z}).
$$
2. Scale: Multiply by a scaling factor $\Delta$ to maintain precision:
$$
\mathbf{z}' = \Delta \cdot \mathbf{z}_\mathbb{H}.
$$
3. Project onto the polynomial space:
- Compute coordinates in the canonical embedding basis:
$$
z_i = \frac{\langle \mathbf{z}', \beta_i \rangle}{\|\beta_i\|^2}, \quad \text{where } \beta_i = \sigma(X^i).
$$
- Round each coordinate **randomly** to the nearest integer:
$$
\tilde{z}_i = \lfloor z_i \rceil_{\mathbb{Z}}.
$$
- Reconstruct the integer polynomial:
$$
m(X) = \sum_{i=0}^{n-1} \tilde{z}_i X^i \in \mathbb{Z}[X]/(X^n+1).
$$

#### Decoding
- Given a polynomial $m(X) \in R_q$:
1. Scale back:
$$
m'(X) = \Delta^{-1} \cdot m(X).
$$
2. Apply canonical embedding:
$$
\mathbf{z}' = \sigma(m'(X)).
$$
3. Project back onto $\mathbb{C}^{n/2}$:
$$
\mathbf{z} = \pi(\mathbf{z}').
$$

---

### Encryption and Decryption
#### Encryption
To encrypt a message polynomial $m(X) \in R_q$:
- $r \in R_q$ and error terms $e_1, e_2 \sim \chi$.
- Compute:
$$
\begin{aligned}
c_0 &= b \cdot r + e_1 + m \in R_q, \\
c_1 &= a \cdot r + e_2 \in R_q.
\end{aligned}
$$
- Output:
$$
c = (c_0, c_1).
$$

#### Decryption
Given ciphertext $c = (c_0, c_1)$:
- Compute:
$$
v = c_0 + s \cdot c_1 \in R_q.
$$
- Recover the plaintext:
$$
m \approx v \mod q.
$$

### Multiplication and Relinearization
- Multiplication
- Compute:
$$
d_0 = c_0 \cdot c'_0, \quad d_1 = c_0 \cdot c'_1 + c_1 \cdot c'_0, \quad d_2 = c_1 \cdot c'_1.
$$
- The ciphertext $d = (d_0, d_1, d_2)$ encrypts $m \cdot m'$.

- Relinearization
- Expand $d_2$ in base-$B$:
$$
d_2 = \sum_{i=0}^{\ell} d_{2,i} \cdot B^i.
$$
- Compute:
$$
d'_0 = d_0 + \sum_{i=0}^{\ell} d_{2,i} \cdot \text{evk}_{0,i}, \quad d'_1 = d_1 + \sum_{i=0}^{\ell} d_{2,i} \cdot \text{evk}_{1,i}.
$$

- Rescaling
- Compute:
$$
c' = \left\lfloor \frac{q_{l-1}}{q_l} c \right\rceil \mod q_{l-1}.
$$
- Equivalent to:
$$
c' = \left\lfloor \Delta^{-1} c \right\rceil \mod q_{l-1}.
$$
- This reduces the modulus from $q_l$ to $q_{l-1}$.

--------------------------------

# TLWE
We work in the discretized torus $T_q = \frac{1}{q}\mathbb{Z}/\mathbb{Z},$
and define the plaintext space as the subgroup $P = T_p = \left\{0, \frac{1}{p}, \frac{2}{p}, \dots, \frac{p-1}{p}\right\} \subset T_q,$
with $p$ a divisor of $q$.

- Params:
- $n$: security parameter (dimension of the torus vector),
- $q$: modulus defining the discretization of the torus,
- $p$: plaintext modulus, with $P = \{0, \frac{1}{p}, \dots, \frac{p-1}{p}\}$,
- $\chi$: error distribution (e.g., induced by a discrete Gaussian).

- $KeyGen$:
- Choose parameters $n$, $p$, $q$, and an error distribution $\chi$.
- Sample the secret key $s \xleftarrow{rnd} \{0,1\}^n$.
- Public parameters are $pp = \{n,\sigma,p,q\}$ and the private key is $sk = s$.

- $Enc_s(\mu)$ for plaintext $\mu \in P$:
- Sample a random vector $(a_1, \dots, a_n) \xleftarrow{rnd} T_q^n$.
- Sample error $e \leftarrow \chi$ (with the discretized error $e$ taken from $\frac{1}{q}\mathbb{Z}$).
- Compute the body:
$$
b = \sum_{j=1}^n s_j\, a_j + \mu + e \in T_q.
$$
- Output the ciphertext:
$$
c = (a_1, \dots, a_n, b).
$$

- $Dec_s(c)$ for ciphertext $c = (a_1, \dots, a_n, b)$:
- Compute
$$
\mu^* = b - \sum_{j=1}^n s_j\, a_j \in T_q.
$$
- Recover the plaintext by decoding:
$$
\mu = \left\lfloor p\,\mu^* \right\rceil \mod p,
$$
which is correct provided that the error satisfies $|e| < \frac{1}{2p}$.

## TFHE
### Encryption

- **TLWE** (Torus Learning With Errors): Encrypts a **single bit**.
- **TRLWE** (Torus Ring LWE): Encrypts a **vector** (batch of bits).
- **TRGSW** (Torus Ring GSW): Used for **bootstrapping**.

#### **TLWE Encryption**
A TLWE ciphertext encrypts a bit $m \in \{0,1\}$:
- Sample randomness $\mathbf{a} \xleftarrow{\text{rnd}} \mathbb{T}^N$ and noise $e \sim \mathcal{N}(0, \sigma^2)$.
- Compute ciphertext:
$$
c = (\mathbf{a}, b), \quad b = \langle \mathbf{a}, \mathbf{s} \rangle + e + \frac{m}{2} \mod 1.
$$

#### **TRLWE Encryption**
A TRLWE ciphertext encrypts a vector plaintext $m(X) \in R_t$:
- Sample:
- $a(X) \xleftarrow{\text{rnd}} R_q$.
- $e(X) \sim \mathcal{N}(0, \sigma^2)$.
- Compute:
$$
c = (a(X), b(X)), \quad b(X) = s(X) \cdot a(X) + e(X) + m(X) \mod q.
$$

#### **TRGSW Encryption**
A TRGSW ciphertext encrypts a polynomial plaintext $m(X) \in R_t$:
$$
C_{\text{TRGSW}} = Z + m(X) \cdot G \in \mathbb{T}[X]^{2\ell \times 2}.
$$
where:
- $G$ is a gadget matrix for key decomposition.
- $Z$ is a list of RLWE encryptions of $0$.

### Homomorphic operations

#### XOR (Addition)
Given ciphertexts $c, c'$ encrypting $m, m'$:
$$
c_{\text{add}} = c + c' \mod 1.
$$

#### AND (Multiplication)
Multiplication is performed using TRGSW-based programmable bootstrapping:
$$
c_{\text{mult}} = \text{BlindRotate}(c, C_{\text{TRGSW}}).
$$

### Bootstrapping
#### Look-Up Tables (LUTs)
TFHE supports programmable bootstrapping, allowing functions to be evaluated using LUTs.

- Encrypt a function $F(x)$ as a look-up table.
- Apply bootstrapping to evaluate $F(m)$ homomorphically.

#### BlindRotation

##### TLWE
- **TLWE ciphertext**:
- Given an encrypted bit $\mu$, the TLWE encryption is:
$$
C_m = (a, b) \in T_q^{n+1}
$$
- The phase is:
$$
\phi = b - \langle a, s \rangle = \mu + e.
$$
- The goal is to extract $\mu$ without decrypting $\phi$.

- **Transition to RLWE**:
- Define the ring $R_q = \mathbb{Z}_q[X] / \langle X^N + 1 \rangle$.
- The TLWE ciphertext is mapped to an RLWE ciphertext in this ring to enable polynomial operations.

##### BlindRotate in detail
- Input
- **Encrypted message (TLWE form)**
$$
C_m = (a, b) \in T_q^{n+1}
$$
- **Test polynomial**
$$
F(X) = \sum_{i=0}^{N-1} f_i X^i \in R_q.
$$
- Constructed so that after shifting by $X^p$, $f_0$ contains $\mu$.

- **Rotation offset**
$$
p = \phi = b - \langle a, s \rangle.
$$
- The shift amount is hidden in encryption.

- Compute:
1. Compute an encrypted monomial $X^p$
- Since $p$ is unknown, evaluate $X^p$ homomorphically:
$$
C_{X^p} \gets \text{EvalFunc}(C_p, \Phi),
$$
where $\Phi(p) = X^p \mod f(X)$.

2. Apply homomorphic rotation
- Multiply the test polynomial by $X^p$:
$$
C_{\text{temp}} = C_m \cdot C_{X^p}.
$$
- This shifts $F(X)$, aligning $f_p$ into position $f_0'$.

3. Key switching
- To control noise, apply key switching:
$$
C_{\text{rot}} \gets \text{KeySwitch}(C_{\text{temp}}).
$$

- Output
- The rotated polynomial $F'(X)$ has the refreshed message in $f_0'$.
- Extract $f_0'$ and encode it into a fresh TLWE ciphertext.

### Bootstrapping mode
TFHE supports two bootstrapping modes:

#### Gate Bootstrapping
- Gate bootstrapping resets the noise of a TLWE ciphertext after each logic gate operation.

- Given a TLWE ciphertext $c = (\mathbf{a}, b)$ encrypting $m \in \{0,1\}$:
1. Compute the phase:
$$
\varphi = b - \langle \mathbf{a}, \mathbf{s} \rangle \mod 1.
$$

2. Encode the function $F(x)$ corresponding to the gate.

3. Evaluate $F(\varphi)$ using a Look-Up Table (LUT) in a TRGSW ciphertext:
$$
c' = \text{BlindRotate}(c, C_{\text{TRGSW}}).
$$

4. Extract a fresh TLWE ciphertext encrypting $F(m)$:
$$
c_{\text{out}} = (\mathbf{a}', b').
$$

#### Circuit Bootstrapping
- Circuit bootstrapping resets noise after an entire circuit evaluation instead of after each gate.

- Given a TLWE ciphertext $c = (\mathbf{a}, b)$ encrypting $m \in \{0,1\}$:
1. Compute the phase:
$$
\varphi = b - \langle \mathbf{a}, \mathbf{s} \rangle \mod 1.
$$

2. Encode the function $F(x)$ representing the entire circuit.

3. Evaluate $F(\varphi)$ using programmable bootstrapping:
$$
c' = \text{BlindRotate}(c, C_{\text{TRGSW}}).
$$

4. Extract a fresh TLWE ciphertext encrypting $F(m)$:
$$
c_{\text{out}} = (\mathbf{a}', b').
$$

-------

# Leveled FHE

------------

# Example
## SHA256

I used TFHErs to compute a hash over the encrypted value of "1234", entirely within the FHE domain.
1. System info:
- CPU(s): 44 (22 cores, 44 threads) (Xeon E5-2696v4)
- Architecture: x86_64; OS Linux kernel 6.8.0-55-generic
- RAM: 64GB
2. Setup & build
1. Clone repo

    2. Install cmake & rust
    3. Run example:

4. Result:
- Processed in: 19551.38250654s
- Total time: 19551.382852143s

Args: Args { device: Cpu, parallel: true, trivial: false, multibit: None }
key gen start
key gen end
1234
Starting main loop
Start chunk: 1 / 1
Processed in: 19551.38250654s
Total time: 19551.382852143s
03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4