papers/threshold-fhe-compliance/sections/03-formal-construction.tex

\section{Formal Construction}

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

\subsection{System Model}

The system comprises four roles:

\begin{enumerate}[nosep]
  \item \textbf{Users.}  Submit encrypted inputs.  Each user encrypts
        their data under the system's public key before submission.
  \item \textbf{Operator.}  Evaluates homomorphic circuits on encrypted
        data.  The operator holds no key shares and cannot decrypt.
  \item \textbf{Decryption committee.}  A set of $n$ parties, each
        holding one share of the FHE secret key.  Any $t$ can
        cooperate to decrypt.
  \item \textbf{Regulator.}  Either a member of the committee with
        sufficient shares, or an entity that can compel $t$ committee
        members to participate in decryption.
\end{enumerate}

\subsection{Key Generation}

\begin{algorithm}[H]
\caption{Threshold FHE Key Generation}
\label{alg:keygen}
\begin{algorithmic}[1]
\Require Threshold $t$, committee size $n$, LWE dimension $N$,
         RLWE degree $\hat{N}$
\Ensure Public key $\mathsf{pk}$, bootstrapping key $\mathsf{bsk}$,
        key shares $\{\mathbf{s}_i\}_{i=1}^n$
\State $\mathbf{s} \leftarrow \{0,1\}^N$ \Comment{Sample LWE secret key}
\For{$j = 1, \ldots, N$}
  \State Share $s_j$ via $(t,n)$-Shamir: party $i$ receives $s_{j,i}$
\EndFor
\State $\mathbf{s}_i \leftarrow (s_{1,i}, \ldots, s_{N,i})$ for each $i$
\State $\mathsf{pk} \leftarrow \mathsf{LWE.PublicKey}(\mathbf{s})$
\State $\mathsf{bsk} \leftarrow \mathsf{BootstrapKey}(\mathbf{s})$
  \Comment{RGSW encryptions of key bits}
\State Erase $\mathbf{s}$ \Comment{Secret key exists only as shares}
\State \Return $(\mathsf{pk}, \mathsf{bsk}, \{\mathbf{s}_i\}_{i=1}^n)$
\end{algorithmic}
\end{algorithm}

After key generation, the plaintext secret key $\mathbf{s}$ is erased.
Only the shares $\mathbf{s}_1, \ldots, \mathbf{s}_n$ and the public
material $(\mathsf{pk}, \mathsf{bsk})$ persist.  The bootstrapping key
$\mathsf{bsk}$ is public---it consists of RGSW encryptions of the key
bits and is required for gate evaluation but does not reveal
$\mathbf{s}$.

\subsection{Homomorphic Evaluation}

The operator receives encrypted inputs and evaluates boolean circuits
using the TFHE gate-by-gate bootstrapping pipeline:

\begin{enumerate}[nosep]
  \item \textbf{Gate evaluation.}  For each gate $g \in \{\text{AND},
        \text{OR}, \text{NOT}, \text{NAND}, \text{NOR}, \text{XOR},
        \text{XNOR}, \text{MUX}, \text{MAJORITY}\}$, the operator
        computes $c_{\text{out}} = \mathsf{Gate}(c_{\text{in}_1},
        c_{\text{in}_2}, \mathsf{bsk})$.
  \item \textbf{Bootstrapping.}  Each gate application performs a
        programmable bootstrap that resets the noise, enabling
        unlimited circuit depth.
  \item \textbf{No decryption.}  The operator uses only
        $\mathsf{pk}$ and $\mathsf{bsk}$.  Without any share of
        $\mathbf{s}$, the operator cannot decrypt any intermediate
        or final ciphertext.
\end{enumerate}

\subsection{Threshold Decryption Protocol}

When decryption is authorized (either by the committee or compelled by
the regulator):

\begin{algorithm}[H]
\caption{Threshold Decryption}
\label{alg:decrypt}
\begin{algorithmic}[1]
\Require Ciphertext $c = (\mathbf{a}, b)$, threshold $t$, committee
         subset $S \subseteq [n]$ with $|S| \geq t$
\Ensure Plaintext bit $\mu$
\For{$i \in S$}
  \State Party $i$ computes $d_i = \langle \mathbf{a}, \mathbf{s}_i
         \rangle + e_i$ \Comment{Add smudging noise $e_i$}
  \State Party $i$ publishes $d_i$
\EndFor
\State Combiner computes Lagrange coefficients
       $\lambda_i = \prod_{j \in S \setminus \{i\}} \frac{j}{j - i}$
\State $D = \sum_{i \in S} \lambda_i \cdot d_i$
  \Comment{Reconstructs $\langle \mathbf{a}, \mathbf{s} \rangle + e'$}
\State $\mu = \text{round}(b - D)$
\State \Return $\mu$
\end{algorithmic}
\end{algorithm}

The smudging noise $e_i$ added by each party ensures that the partial
decryption $d_i$ does not leak information about $\mathbf{s}_i$ beyond
what is implied by the final plaintext.  The smudging noise is chosen
large enough to statistically mask the LWE error but small enough that
the total accumulated noise remains below the decryption threshold
$1/4$.

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