papers/threshold-fhe-compliance/sections/04-security-proofs.tex

\section{Security Proofs}

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

\subsection{Operator Blindness}

\begin{theorem}[Operator Blindness]
\label{thm:operator-blind}
Let $\Pi$ be the threshold TFHE scheme described in
Section~\ref{sec:construction}.  An operator that holds only the public
key $\mathsf{pk}$ and bootstrapping key $\mathsf{bsk}$ (but no shares
of $\mathbf{s}$) cannot distinguish encryptions of $0$ from encryptions
of $1$ with advantage better than $\mathsf{negl}(\lambda)$, assuming
the LWE$_{n,q,\sigma}$ problem is hard.
\end{theorem}

\begin{proof}[Proof sketch]
The bootstrapping key $\mathsf{bsk}$ consists of RGSW encryptions of
the secret key bits under the RLWE key.  Under the RLWE assumption
(which reduces to LWE), these encryptions are computationally
indistinguishable from encryptions of zero.  Therefore the operator's
view---consisting of $\mathsf{pk}$, $\mathsf{bsk}$, and a collection
of LWE ciphertexts---is computationally indistinguishable between the
case where all ciphertexts encrypt $0$ and the case where they encrypt
$1$.  This is a standard IND-CPA argument for LWE-based encryption,
extended to the bootstrapping key via the RLWE hardness assumption.
\end{proof}

\subsection{Threshold Decryptability}

\begin{theorem}[Threshold Decryptability]
\label{thm:threshold-decrypt}
For any ciphertext $c$ produced by the system (either a fresh encryption
or the output of homomorphic evaluation), any subset $S$ of at least $t$
share-holders can correctly decrypt $c$ with probability
$1 - \mathsf{negl}(\lambda)$.
\end{theorem}

\begin{proof}[Proof sketch]
By the correctness of Shamir's secret sharing
(Definition~\ref{def:shamir}), any $t$ shares uniquely determine the
polynomial $f$ and thus the secret $s_j$ for each coordinate $j$.
Lagrange interpolation on the partial decryptions $\{d_i\}_{i \in S}$
reconstructs $\langle \mathbf{a}, \mathbf{s} \rangle$ plus accumulated
smudging noise.  The total noise is bounded by $|e| + \sum_{i \in S}
|\lambda_i| \cdot |e_i|$.  By choosing the smudging parameter
$\sigma_{\text{smudge}} = 2^{-\lambda} \cdot \sigma$ and observing that
the Lagrange coefficients satisfy $\sum |\lambda_i| \leq \binom{n}{t}
\cdot t^t$ (which is polynomial in $n$), the total noise remains below
$1/4$ with overwhelming probability for standard parameter choices
($N = 1024$, $q \approx 2^{27}$).  Rounding then recovers the correct
plaintext bit.
\end{proof}

\subsection{Privacy Below Threshold}

\begin{theorem}[Privacy Below Threshold]
\label{thm:privacy}
Any coalition of fewer than $t$ share-holders, even in cooperation with
the operator, learns no information about any plaintext encrypted under
the system beyond what is implied by the public parameters.
\end{theorem}

\begin{proof}[Proof sketch]
This follows from two independent arguments:
\begin{enumerate}[nosep]
  \item \textbf{Information-theoretic secret sharing.}  By the privacy
        property of Shamir's scheme, any $t-1$ shares are uniformly
        distributed over $\mathbb{Z}_q^{t-1}$, independent of the secret.
        Therefore $t-1$ share-holders learn nothing about $\mathbf{s}$.
  \item \textbf{Computational LWE hardness.}  Even with $t-1$ shares,
        reconstructing the remaining share would require solving an LWE
        instance.  The operator contributes only public material
        ($\mathsf{pk}$, $\mathsf{bsk}$, ciphertexts), which is
        computationally indistinguishable from random under LWE.
\end{enumerate}
The composition of information-theoretic and computational security
holds because the information-theoretic argument applies to the secret
sharing layer independently of the computational argument for the
encryption layer.
\end{proof}

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