papers/lux-fhe-mpc-hybrid/sections/05-frost-fhe-key-shares.tex

\section{FROST + FHE Key Shares}


We use FROST (Flexible Round-Optimized Schnorr Threshold signatures)~\cite{frost2020} for MPC coordination, adapted to manage FHE key shares rather than signing keys.

\subsection{Why FROST}

FROST provides:
\begin{itemize}[leftmargin=2em]
\item Two-round threshold signing (commitment + response).
\item Robustness: if a participant fails, the protocol completes without them (as long as $\geq t$ participate).
\item No trusted dealer: DKG produces shares without any party seeing the full secret.
\end{itemize}

In our construction, the FROST DKG protocol generates both:
\begin{enumerate}[leftmargin=2em]
\item The FHE secret key shares $\{\mathbf{s}_i\}_{i=1}^n$ for threshold decryption.
\item A Schnorr signing key for threshold attestation (proving that a legitimate decryption occurred).
\end{enumerate}

\subsection{Decryption Protocol}

\begin{algorithm}[H]
\caption{Threshold FHE Decryption with FROST Attestation}
\begin{algorithmic}[1]
\Require Ciphertext $(\mathbf{a}, b)$, threshold $t$, participants $S \subseteq [n]$ with $|S| \geq t$
\Ensure Plaintext $m$ and threshold attestation $\sigma$
\State \textbf{Round 1 (Commitment):}
\ForAll{$i \in S$}
    \State Compute partial decryption $d_i = \langle \mathbf{a}, \mathbf{s}_i \rangle \bmod q$
    \State Compute commitment $C_i = \text{Hash}(d_i \| \text{nonce}_i)$
    \State Broadcast $C_i$
\EndFor
\State \textbf{Round 2 (Reveal + Combine):}
\ForAll{$i \in S$}
    \State Reveal $d_i$ and $\text{nonce}_i$
    \State Verify $C_i = \text{Hash}(d_i \| \text{nonce}_i)$
\EndFor
\State Compute $\langle \mathbf{a}, \mathbf{s} \rangle = \sum_{i \in S} \lambda_i \cdot d_i \bmod q$
\State Recover $m = \text{round}\left(\frac{b - \langle \mathbf{a}, \mathbf{s} \rangle}{q/2}\right)$
\State Produce FROST threshold signature $\sigma$ over $(m, \text{ct\_hash})$
\State \Return $(m, \sigma)$
\end{algorithmic}
\end{algorithm}

The FROST attestation $\sigma$ proves to any verifier that a legitimate $t$-of-$n$ decryption occurred, without revealing which $t$ nodes participated.