papers/lp-305-quantum-secure-assets/sections/02-lattice-based-threshold-cryptography.tex

\section{Lattice-Based Threshold Cryptography}


\subsection{Mathematical Foundation}

Security rests on the hardness of lattice problems. We define the
foundational problems before specializing to RLWE.

\begin{definition}[Lattice]
A lattice $L$ is the set of all integral combinations of $n$ linearly
independent vectors $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_n
\in \mathbb{R}^n$:
\[
L = \left\{ \sum_{i=1}^{n} x_i \mathbf{b}_i : x_i \in \mathbb{Z}
\right\}
\]
The matrix $B = [\mathbf{b}_1 | \cdots | \mathbf{b}_n]$ is a basis
of $L$.
\end{definition}

\begin{definition}[Shortest Vector Problem (SVP)]
Given a lattice $L$ and a norm $\|\cdot\|$, find a non-zero vector
$\mathbf{v} \in L$ that minimizes the norm:
\[
\mathbf{v} \in L \setminus \{\mathbf{0}\} \quad\text{such that}\quad
\|\mathbf{v}\| = \lambda_1(L) \triangleq
\min_{\mathbf{0} \neq \mathbf{u} \in L} \|\mathbf{u}\|
\]
The $\gamma$-approximate SVP ($\gamma$-SVP) relaxes this to finding
$\mathbf{v}$ with $\|\mathbf{v}\| \leq \gamma \cdot \lambda_1(L)$.
\end{definition}

\begin{definition}[Closest Vector Problem (CVP)]
Given a lattice $L$, a norm $\|\cdot\|$, and a target
$\mathbf{t} \in \mathbb{R}^n$, find a lattice vector closest
to $\mathbf{t}$:
\[
\mathbf{v} \in L \quad\text{such that}\quad
\|\mathbf{v} - \mathbf{t}\| =
\min_{\mathbf{u} \in L} \|\mathbf{u} - \mathbf{t}\|
\]
\end{definition}

Both SVP and CVP are NP-hard under randomized
reductions~\cite{ajtai1996}. No polynomial-time quantum algorithm is
known for either problem, even approximately with sub-exponential
approximation factors.

\begin{definition}[Learning With Errors (LWE)~\cite{regev2005}]
For dimension $n$, modulus $q$, and error distribution $\chi$ over
$\mathbb{Z}_q$, the LWE problem is: given a secret
$\mathbf{s} \in \mathbb{Z}_q^n$ and samples
$(\mathbf{a}_i, b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle
+ e_i \bmod q)$ where $\mathbf{a}_i \xleftarrow{\$} \mathbb{Z}_q^n$
and $e_i \leftarrow \chi$, recover $\mathbf{s}$.

Equivalently, given matrix $A \in \mathbb{Z}_q^{m \times n}$ and
vector $\mathbf{b} \in \mathbb{Z}_q^m$:
\[
\text{Find } \mathbf{s} \in \mathbb{Z}_q^n
\text{ such that }
\|\mathbf{b} - A\mathbf{s}\| < \epsilon
\]
where $\epsilon$ bounds the error norm. Regev~\cite{regev2005} showed
that solving LWE is as hard as solving worst-case lattice problems
($\widetilde{O}(n/\alpha)$-approximate SVP) with quantum reductions.
\end{definition}

\subsubsection{Ring LWE}

The Ring LWE (RLWE) variant provides efficiency by working over
polynomial rings. Let $R_q = \mathbb{Z}_q[X]/(X^n + 1)$ be a
cyclotomic polynomial ring. The decisional RLWE problem asks to
distinguish $(a_i, a_i \cdot s + e_i)$ from uniform, where
$s \in R_q$ is secret and $e_i$ are drawn from a discrete Gaussian
$\chi_\sigma$.

\begin{definition}[RLWE Hardness Assumption]
For security parameter $\lambda$, ring dimension $n$, modulus $q$,
and error distribution $\chi_\sigma$, no probabilistic
polynomial-time (or bounded quantum polynomial-time) algorithm can
distinguish RLWE samples from uniform with advantage better than
$\mathrm{negl}(\lambda)$.
\end{definition}

RLWE reduces to ideal lattice problems in $R_q$, inheriting the
worst-case hardness of SVP over ideal lattices~\cite{lpr2013}.

\subsection{Implementation: \texttt{luxfi/fhe}}

Lux's TFHE library (\texttt{github.com/luxfi/fhe}) implements:

\begin{itemize}[nosep]
  \item \textbf{Parameter sets}: PN10QP27 ($N{=}1024$, $Q{=}134215681$,
        $\sim$128-bit classical), PN11QP54 ($N{=}2048$, higher precision),
        and OpenFHE-compatible STD128Q (post-quantum 128-bit).
  \item \textbf{Boolean gates}: AND, OR, XOR, NOT, NAND, NOR, XNOR,
        MUX, MAJORITY---each with programmable bootstrapping.
  \item \textbf{Integer arithmetic}: FheUint8/16/32/64 with
        Add, Sub, Mul (schoolbook), comparison chains (Lt, Gt, Eq).
  \item \textbf{Threshold key management}: Shamir secret sharing over
        the 2048-bit RFC~3526 Group~14 safe prime, with Feldman VSS
        commitments in the order-$q$ subgroup ($g = 2^2 \bmod p$).
  \item \textbf{Proactive reshare}: additive sub-sharing via Lagrange
        coefficients---no party materializes the full secret during
        reshare.
\end{itemize}

\subsection{Threshold FHE Protocol}

Key generation follows a $t$-of-$n$ Shamir scheme. Each party $i$
receives a share $s_i = f(i)$ where $f$ is a random degree-$(t{-}1)$
polynomial with $f(0) = \mathit{sk}$. Reconstruction uses Lagrange
interpolation:

\[
\mathit{sk} = \sum_{i \in S} s_i \cdot \lambda_i(0),
\qquad
\lambda_i(x) = \prod_{j \in S \setminus \{i\}} \frac{x - j}{i - j}
\]

Reshare without secret materialization: each old party $i$ picks a
random polynomial $g_i$ of degree $(t'{-}1)$ with constant term
$\lambda_i \cdot s_i$. New share $s'_j = \sum_i g_i(j)$. Since
$\sum_i g_i(0) = \sum_i \lambda_i \cdot s_i = \mathit{sk}$, the new
shares reconstruct the same secret. No single party ever holds
$\mathit{sk}$ in cleartext.

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