papers/lux-fhe-mpc-hybrid/sections/04-threshold-decryption-via-mpc.tex

\section{Threshold Decryption via MPC}


\subsection{Key Generation}

The FHE secret key $\mathbf{s} \in \{0,1\}^n$ is generated via distributed key generation (DKG). No single party ever holds the full key.

\begin{enumerate}[leftmargin=2em]
\item Each of $n$ MPC nodes generates a random key share $\mathbf{s}_i \in \{0,1\}^n$.
\item Shares are combined using Shamir secret sharing over $\mathbb{Z}_q$ such that $\mathbf{s} = \sum_{i=1}^{n} \lambda_i \cdot \mathbf{s}_i$ for Lagrange coefficients $\lambda_i$.
\item The public encryption parameters (bootstrapping key, key-switching key) are derived from commitments to $\mathbf{s}$ without revealing it.
\end{enumerate}

\subsection{Partial Decryption}

To decrypt a ciphertext $(\mathbf{a}, b)$, each of $t$ participating nodes computes a partial decryption:

$$d_i = \langle \mathbf{a}, \mathbf{s}_i \rangle \bmod q$$

The combiner reconstructs:

$$\langle \mathbf{a}, \mathbf{s} \rangle = \sum_{i \in S} \lambda_i \cdot d_i \bmod q$$

and recovers $m = \text{round}\left(\frac{b - \langle \mathbf{a}, \mathbf{s} \rangle}{q/2}\right)$.

\begin{theorem}[Threshold Security]
If the LWE problem with parameters $(n, q, \sigma)$ is hard, then no coalition of fewer than $t$ parties can distinguish a TFHE ciphertext from random, even given access to the partial decryption oracle for other ciphertexts.
\end{theorem}

\begin{proof}[Proof sketch]
Reduce to standard LWE. Given $t-1$ key shares, the adversary's view of the remaining share is uniformly random over $\mathbb{Z}_q^n$ (information-theoretic security of Shamir sharing). The ciphertext is therefore an LWE sample with unknown key, which is pseudorandom under LWE.
\end{proof}