papers/lux-tfhe/sections/02-tfhe-preliminaries.tex

\section{TFHE Preliminaries}

\label{sec:prelim}

\subsection{Torus Arithmetic}

\begin{definition}[Torus]
The real torus $\mathbb{T} = \mathbb{R}/\mathbb{Z}$ is the group of real numbers modulo 1.
In practice, we discretize to $\mathbb{T}_q = \mathbb{Z}_q / q$ by mapping $x \in \mathbb{T}$
to $\lfloor x \cdot q \rceil \in \mathbb{Z}_q$.
\end{definition}

\begin{definition}[LWE Encryption]
An LWE ciphertext encrypting bit $m \in \{0, 1\}$ under secret key $\mathbf{s} \in \mathbb{Z}_q^n$ is:
\[
\text{ct} = (\mathbf{a}, b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q
\]
where $\mathbf{a} \stackrel{\$}{\leftarrow} \mathbb{Z}_q^n$ and $b = \langle \mathbf{a}, \mathbf{s} \rangle + m \cdot \lfloor q/2 \rfloor + e$
with noise $e \stackrel{\$}{\leftarrow} D_\sigma$.
\end{definition}

Decryption computes:
\begin{equation}
\hat{m} = \left\lfloor \frac{b - \langle \mathbf{a}, \mathbf{s} \rangle}{q/2} \right\rceil \mod 2
\label{eq:decrypt}
\end{equation}

This succeeds when $|e| < q/4$.

\subsection{RGSW Encryption}

\begin{definition}[RGSW Ciphertext]
An RGSW (Ring-GSW) ciphertext of $m \in \{0, 1\}$ under RLWE secret $s(X) \in R_q$
is a matrix $\mathbf{C} \in R_q^{2\ell \times 2}$ such that for any RLWE ciphertext
$(\mathbf{a}', b')$, the external product $\mathbf{C} \boxdot (\mathbf{a}', b')$
yields an RLWE encryption of $m \cdot \text{Dec}(\mathbf{a}', b')$ with controlled noise growth.
\end{definition}

RGSW ciphertexts of the secret key bits form the \emph{bootstrap key}:
$\text{BSK} = \{\text{RGSW}(s_i)\}_{i=1}^n$ where $s_i$ are the LWE secret key coefficients.

%% -----------------------------------------------------------------------
%%  3. BOOLEAN GATE EVALUATION
%% -----------------------------------------------------------------------