papers/lux-fhe-smart-contracts/sections/02-fhe-primer.tex

\section{FHE Primer}

\label{sec:fhe-primer}

\subsection{Ring Learning with Errors}

FHE security rests on the hardness of the Ring Learning with Errors
(Ring-LWE) problem~\cite{lyubashevsky2010ideal}.

\begin{definition}[Ring-LWE]
Let $R_q = \mathbb{Z}_q[X]/(X^N + 1)$ be a polynomial ring with $N$ a power of 2.
The Ring-LWE problem: given polynomials $(a_i, b_i = a_i \cdot s + e_i)$ where
$s \in R_q$ is a secret and $e_i$ are drawn from a discrete Gaussian distribution
$\chi$ with small standard deviation $\sigma$, distinguish $(a_i, b_i)$ from uniform
random pairs.
\end{definition}

No known quantum algorithm provides more than a polynomial speedup over classical
algorithms for Ring-LWE. NIST's post-quantum standards (ML-KEM, ML-DSA) are built
on the related Module-LWE assumption, providing strong evidence for the security of
Ring-LWE-based FHE.

\subsection{Encryption and Homomorphic Operations}

An FHE scheme encrypts a plaintext $m$ as a ciphertext $\textsf{ct} = (c_0, c_1)$
where $c_0 = a \cdot s + e + \Delta \cdot m$ and $c_1 = a$, with $\Delta = \lfloor
q/t \rfloor$ the scaling factor and $t$ the plaintext modulus.

Homomorphic addition is component-wise:
\[
  \textsf{ct}_{\text{add}} = \textsf{ct}_1 + \textsf{ct}_2 = (c_{0,1} + c_{0,2}, c_{1,1} + c_{1,2})
\]

Decrypting $\textsf{ct}_{\text{add}}$ yields $m_1 + m_2$ because the noise terms
add linearly: $e_{\text{add}} = e_1 + e_2$.

Homomorphic multiplication is a tensor product followed by relinearization:
\[
  \textsf{ct}_{\text{mul}} = \textsf{Relin}(\textsf{ct}_1 \otimes \textsf{ct}_2)
\]

Multiplication increases noise quadratically: $\|e_{\text{mul}}\| \approx \|e_1\|
\cdot \|e_2\|$. After sufficiently many multiplications, noise exceeds the decryption
threshold, and the ciphertext becomes unrecoverable.

\subsection{Bootstrapping}

Bootstrapping~\cite{gentry2009fhe} ``refreshes'' a ciphertext by homomorphically
evaluating the decryption function, producing a new ciphertext of the same plaintext
with reduced noise. This enables unlimited computation depth at the cost of
significant computational overhead.

\begin{definition}[Bootstrapping]
Given a ciphertext $\textsf{ct}$ with noise level $\|e\|$ near the threshold, and
a bootstrapping key $\textsf{bsk}$ (encrypted secret key), bootstrapping produces
$\textsf{ct}' = \textsf{Bootstrap}(\textsf{ct}, \textsf{bsk})$ such that
$\textsf{Dec}(\textsf{ct}') = \textsf{Dec}(\textsf{ct})$ and $\|e'\| \ll \|e\|$.
\end{definition}

Our implementation uses the CGGI bootstrapping technique~\cite{cggi2020tfhe}
(programmable bootstrapping via blind rotation), which simultaneously refreshes
noise and evaluates a lookup table, enabling gate-level computation in a single
bootstrapping pass.

\subsection{Noise Management}

The central challenge of practical FHE is noise management. Each operation increases
noise; bootstrapping resets noise but is expensive. The FHE VM must track noise
budgets for every ciphertext and bootstrap before decryption fails.

\begin{table}[ht]
\centering
\caption{Noise growth by operation type.}
\label{tab:noise-growth}
\begin{tabular}{lll}
\toprule
\textbf{Operation} & \textbf{Noise Growth} & \textbf{Depth Cost} \\
\midrule
Addition & $\|e_1\| + \|e_2\|$ (linear) & $+0$ \\
Plaintext multiplication & $c \cdot \|e_1\|$ (linear) & $+0$ \\
Ciphertext multiplication & $\|e_1\| \cdot \|e_2\|$ (quadratic) & $+1$ \\
Bootstrapping & $\to e_{\text{fresh}}$ (reset) & $0$ (reset) \\
\bottomrule
\end{tabular}
\end{table}

%% ========================================================================
%%  3. LUX FHE IMPLEMENTATION
%% ========================================================================