papers/threshold-fhe-compliance/sections/02-preliminaries.tex

\section{Preliminaries}

\label{sec:prelim}
%% =====================================================================

\subsection{TFHE: Torus Fully Homomorphic Encryption}

\begin{definition}[LWE over the Torus]
Let $n$ be the LWE dimension, $\mathbf{s} \in \{0,1\}^n$ the secret key,
and $\sigma > 0$ the noise parameter.  An LWE ciphertext encrypting
$\mu \in \{0, 1/2\} \subset \mathbb{T}$ is a pair
$(\mathbf{a}, b) \in \mathbb{T}^n \times \mathbb{T}$ where
$\mathbf{a} \leftarrow \mathbb{T}^n$ uniformly and
$b = \langle \mathbf{a}, \mathbf{s} \rangle + \mu + e$
with $e \leftarrow \mathcal{N}(0, \sigma^2)$.
\end{definition}

\begin{definition}[Decryption]
Given ciphertext $(\mathbf{a}, b)$ and secret key $\mathbf{s}$:
\[
  \mu' = b - \langle \mathbf{a}, \mathbf{s} \rangle = \mu + e.
\]
The plaintext bit is recovered by rounding: if $\mu'$ is closer to $0$
than to $1/2$, output $0$; otherwise output $1$.  Correctness holds when
$|e| < 1/4$.
\end{definition}

\begin{definition}[Programmable Bootstrapping]
Given a ciphertext $c$ encrypting bit $b$ and a lookup table $T$,
programmable bootstrapping produces a fresh ciphertext encrypting $T[b]$
with noise independent of the input noise.  This is the mechanism that
enables unlimited gate depth: after each gate, the noise is reset.
\end{definition}

\subsection{Shamir Secret Sharing}

\begin{definition}[$(t, n)$-Shamir Sharing]
\label{def:shamir}
To share a secret $s \in \mathbb{Z}_q$, choose random
$a_1, \ldots, a_{t-1} \leftarrow \mathbb{Z}_q$ and define the polynomial
$f(x) = s + a_1 x + \cdots + a_{t-1} x^{t-1}$.
Share $i$ is $s_i = f(i)$ for $i \in \{1, \ldots, n\}$.
Any $t$ shares determine $f$ (and thus $s$) via Lagrange interpolation.
Any $t-1$ shares are uniformly distributed, independent of $s$.
\end{definition}

\subsection{Threshold Decryption}

\begin{definition}[Threshold LWE Decryption]
\label{def:threshold-dec}
The secret key $\mathbf{s} \in \{0,1\}^n$ is shared coordinate-wise:
for each coordinate $j \in [n]$, the value $s_j$ is shared via
$(t, n)$-Shamir sharing.  To decrypt ciphertext $(\mathbf{a}, b)$:
\begin{enumerate}[nosep]
  \item Each party $i$ computes partial decryption
        $d_i = \langle \mathbf{a}, \mathbf{s}_i \rangle$ where
        $\mathbf{s}_i$ is their share vector.
  \item The combiner collects $t$ partial decryptions and reconstructs
        $\langle \mathbf{a}, \mathbf{s} \rangle$ via Lagrange
        interpolation on the partial decryptions.
  \item The plaintext is $\text{round}(b - \langle \mathbf{a},
        \mathbf{s} \rangle)$.
\end{enumerate}
\end{definition}

%% =====================================================================