papers/lux-tfhe/sections/04-threshold-decryption.tex

\section{Threshold Decryption}

\label{sec:threshold}

\subsection{Key Distribution}

The LWE secret key $\mathbf{s} \in \mathbb{Z}_q^n$ is shared via Shamir secret sharing:
party $i$ holds $\mathbf{s}_i$ such that $\mathbf{s} = \sum_{i \in S} \lambda_i \mathbf{s}_i$
for any $t$-subset $S$.

\subsection{Partial Decryption Protocol}

\begin{algorithm}[H]
\caption{Threshold TFHE Decryption}
\label{alg:threshold-decrypt}
\begin{algorithmic}[1]
\Require Ciphertext $(\mathbf{a}, b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$
\Require Party $i$'s share $\mathbf{s}_i$, signers $S$ with $|S| \geq t$
\State \Comment{Phase 1: Each party computes partial decryption}
\State $d_i \gets \langle \mathbf{a}, \mathbf{s}_i \rangle + e_i$ \Comment{$e_i$: smudging noise for privacy}
\State \textbf{send} $d_i$ to combiner
\State \Comment{Phase 2: Combiner reconstructs plaintext}
\State $d \gets \sum_{i \in S} \lambda_i \cdot d_i$ \Comment{$\approx \langle \mathbf{a}, \mathbf{s} \rangle + \text{smudge}$}
\State $\hat{m} \gets \lfloor (b - d) / (q/2) \rceil \mod 2$
\State \Return $\hat{m}$
\end{algorithmic}
\end{algorithm}

\subsection{Security of Threshold Decryption}

\begin{theorem}[Threshold IND-CPA Security]
\label{thm:threshold-security}
The threshold TFHE scheme achieves IND-CPA security under the LWE assumption: an
adversary controlling $t-1$ parties learns nothing about the encrypted plaintext
beyond what is revealed by the decryption output.
\end{theorem}

\begin{proof}
The adversary observes $t-1$ partial decryptions $\{d_i\}_{i \in C}$ where $C$ is the
corrupted set with $|C| = t - 1$. Each $d_i = \langle \mathbf{a}, \mathbf{s}_i \rangle + e_i$.

By the Shamir sharing property, the $t-1$ shares $\{\mathbf{s}_i\}_{i \in C}$ reveal no
information about $\mathbf{s}$ (the secret requires $t$ shares for reconstruction).
The smudging noise $e_i$ with $\sigma_{\text{smudge}} \gg \sigma$ ensures that the
partial decryptions are statistically independent of the missing share.

Formally, for any two messages $m_0, m_1$ and the corresponding ciphertexts:
\[
\{\text{ct}, \{d_i\}_{i \in C}\} \overset{s}{\approx} \{\text{ct}, \{u_i\}_{i \in C}\}
\]
where $u_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ are uniform, with statistical
distance $\leq n \cdot t \cdot \sigma / \sigma_{\text{smudge}} < 2^{-128}$ for appropriate
$\sigma_{\text{smudge}} = 2^{40} \cdot \sigma$.
\end{proof}

\begin{lemma}[Decryption Correctness Under Threshold]
\label{lem:threshold-correctness}
Threshold decryption succeeds (correct plaintext recovery) when the total noise
(original LWE noise + smudging noise from all parties) satisfies:
\[
|e| + t \cdot |\sigma_{\text{smudge}}| < q/4
\]
For parameters $\sigma = 3.2$, $\sigma_{\text{smudge}} = 2^{10}$, $t = 3$, and
$q = 2^{27}$: the noise budget is $3 \times 2^{10} \approx 2^{12} \ll 2^{25} = q/4$.
\end{lemma}

%% -----------------------------------------------------------------------
%%  5. PARAMETERS AND SECURITY
%% -----------------------------------------------------------------------