papers/lux-threshold-mpc/sections/07-security-analysis.tex

\section{Security Analysis}

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

\subsection{FROST Unforgeability}

\begin{theorem}[FROST Unforgeability~\cite{komlo2020frost}]
\label{thm:frost-uf}
FROST is unforgeable under $t{-}1$ static corruption in the random oracle model,
assuming the hardness of the Discrete Logarithm Problem (DLP) in $\mathbb{G}$.
\end{theorem}

\begin{proof}[Proof sketch]
The proof reduces to the unforgeability of standard Schnorr signatures via a
simulation argument. Given a forger $\mathcal{F}$ that breaks FROST with $t-1$
corrupt parties, we construct a reduction $\mathcal{R}$ that breaks the Schnorr
signature scheme:

\begin{enumerate}[nosep]
  \item $\mathcal{R}$ receives Schnorr public key $Y^*$ from the Schnorr challenger.
  \item $\mathcal{R}$ simulates DKG by embedding $Y^*$ as the aggregate key, using
    the simulator's ability to program random oracle $H_2$.
  \item $\mathcal{R}$ answers $\mathcal{F}$'s signing queries by querying its own
    Schnorr signing oracle: the $t-1$ corrupt shares plus the simulated honest
    party's response produce a valid threshold signature.
  \item When $\mathcal{F}$ outputs a forgery $(m^*, \sigma^*)$ on an unqueried
    message, $\mathcal{R}$ extracts a Schnorr forgery using the forking
    lemma~\cite{pointcheval1996} applied to the random oracle.
\end{enumerate}

The reduction is tight up to a factor of $q_H$ (number of random oracle queries) due
to the forking lemma.
\end{proof}

\subsection{CGGMP21 Security}

\begin{theorem}[CGGMP21 Unforgeability with Identifiable Abort~\cite{canetti2021cggmp}]
\label{thm:cggmp-uf}
CGGMP21 is unforgeable under $t{-}1$ static corruption in the UC framework,
assuming the hardness of ECDSA (equivalently, DLP on secp256k1), semantic security
of Paillier encryption, and soundness of the zero-knowledge proofs
$\Pi_{\mathsf{enc}}, \Pi_{\mathsf{log*}}, \Pi_{\mathsf{aff-g}}$.
\end{theorem}

\begin{proof}[Proof sketch]
The UC proof proceeds through a sequence of hybrid games:

\begin{enumerate}[nosep]
  \item \textbf{Game 0}: Real protocol execution.
  \item \textbf{Game 1}: Replace honest parties' Paillier encryptions with
    encryptions of zero. Indistinguishable by Paillier semantic security.
  \item \textbf{Game 2}: Simulate ZK proofs. Indistinguishable by zero-knowledge.
  \item \textbf{Game 3}: Extract adversary's inputs from ZK proofs. If extraction
    fails, identify the aborting party (identifiable abort).
  \item \textbf{Game 4}: Simulate honest parties' signing shares using knowledge of
    the adversary's inputs. Indistinguishable by Paillier security.
  \item \textbf{Game 5}: Ideal functionality. A forgery in this game implies breaking
    ECDSA.
\end{enumerate}

Identifiable abort follows from the soundness of $\Pi_{\mathsf{log*}}$: if a party's
partial signature is inconsistent with its presigning commitments, the ZK proof
identifies the deviation.
\end{proof}

\subsection{Composition Security}

Lux Teleport runs FROST and CGGMP21 within the same signer network, sharing
communication infrastructure and operator identities. We prove this composition is
safe.

\begin{theorem}[Protocol Composition]
\label{thm:composition}
Running FROST (over Ed25519) and CGGMP21 (over secp256k1) in parallel with the same
signer set does not degrade the security of either protocol, provided:
\begin{enumerate}[nosep]
  \item The DKG for each protocol uses independent randomness.
  \item The signing nonces for each protocol are independently sampled.
  \item The hash functions $H_{\text{FROST}}$ and $H_{\text{ECDSA}}$ use
    domain-separated prefixes.
\end{enumerate}
\end{theorem}

\begin{proof}
FROST operates over Ed25519 (a twisted Edwards curve over $\mathbb{F}_{2^{255}-19}$)
and CGGMP21 operates over secp256k1 (a Weierstrass curve over
$\mathbb{F}_{2^{256} - 2^{32} - 977}$). The group orders, generators, and hash
domains are distinct. Since the DKG and signing randomness are independent,
the protocols' random oracle queries are domain-separated, and the underlying hard
problems (DLP on Ed25519 vs.\ DLP on secp256k1) are independent, a compromise of one
protocol's secret key reveals no information about the other. Formally, the joint
simulation in the UC framework decomposes into independent simulations for each
protocol, and the overall advantage is bounded by the sum of individual advantages.
\end{proof}

\subsection{Failure Probability Analysis}

For production deployment with threshold $t$ of $n$ signers, the probability that
signing fails due to fewer than $t$ honest signers being available is:

\begin{equation}
\label{eq:failure}
P_{\text{fail}} = \sum_{k=0}^{t-1} \binom{n}{k} p^k (1-p)^{n-k}
\end{equation}

where $p$ is the per-signer availability probability. Table~\ref{tab:failure} shows
values for Lux Teleport's production configuration.

\begin{table}[H]
\centering
\small
\begin{tabular}{@{}cccc@{}}
\toprule
$(t, n)$ & $p = 0.95$ & $p = 0.99$ & $p = 0.999$ \\
\midrule
$(3, 5)$ & $2.3 \times 10^{-3}$ & $9.8 \times 10^{-6}$ & $1.0 \times 10^{-8}$ \\
$(5, 7)$ & $4.1 \times 10^{-4}$ & $2.0 \times 10^{-8}$ & $2.1 \times 10^{-12}$ \\
$(7, 10)$ & $1.5 \times 10^{-4}$ & $3.6 \times 10^{-10}$ & $3.6 \times 10^{-16}$ \\
$(67, 100)$ & $3.7 \times 10^{-8}$ & $<10^{-40}$ & $<10^{-100}$ \\
\bottomrule
\end{tabular}
\caption{Signing failure probability by threshold configuration and signer
availability.}
\label{tab:failure}
\end{table}

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