papers/lux-mchain-mpc/sections/03-threshold-signature-schemes.tex

\section{Threshold Signature Schemes}


M-Chain supports multiple threshold signature protocols optimized for different blockchains:

\begin{table}[h]
\centering
\begin{tabular}{@{}llll@{}}
\toprule
\textbf{Protocol} & \textbf{Curve} & \textbf{Target Chain} & \textbf{Latency} \\
\midrule
CGG21 & secp256k1 & Ethereum, BSC & 80ms (15-of-15) \\
MuSig2 & secp256k1 & Bitcoin Taproot & 45ms (15-of-15) \\
FROST & Ed25519 & XRPL, Solana & 35ms (10-of-10) \\
Corona & Lattice (LWE) & Quantum-safe & 7ms (15-of-21) \\
\bottomrule
\end{tabular}

\label{tab:threshold-schemes}
\end{table}

\subsection{CGG21: ECDSA Threshold Signatures}

CGG21 \cite{cgg21} provides UC-secure threshold ECDSA without trusted dealers.

\textbf{Setup Phase (Distributed Key Generation):}


\begin{algorithmic}[1]
\State \textbf{function} \textsc{DistributedKeyGen}($n, t$)
    \For{each participant $i \in [n]$}
        \State $x_i \gets \text{Random}(\mathbb{Z}_q)$ \Comment{Secret share}
        \State $X_i \gets x_i \cdot G$ \Comment{Public commitment}
        \State Broadcast $X_i$ to all participants
    \EndFor
    \State $PK \gets \sum_{i=1}^{n} X_i$ \Comment{Aggregate public key}
    \State \Return $(PK, \{x_1, \ldots, x_n\})$
\State \textbf{end function}
\end{algorithmic}


\textbf{Signing Protocol:}


\begin{algorithmic}[1]
\State \textbf{function} \textsc{ThresholdSign}($message, \{x_i\}_{i \in S}, PK$) where $|S| \geq t$
    \State \textbf{Round 1:} Generate ephemeral shares
    \For{each signer $i \in S$}
        \State $k_i \gets \text{Random}(\mathbb{Z}_q)$
        \State $R_i \gets k_i \cdot G$
        \State Broadcast $R_i$
    \EndFor
    \State
    \State \textbf{Round 2:} Compute partial signatures
    \State $R \gets \sum_{i \in S} R_i$
    \State $r \gets R.x \mod q$ \Comment{x-coordinate}
    \State $e \gets \text{Hash}(message)$
    \For{each signer $i \in S$}
        \State $s_i \gets k_i^{-1}(e + r \cdot x_i) \mod q$
        \State Broadcast $s_i$
    \EndFor
    \State
    \State \textbf{Combine:} Aggregate signature
    \State $s \gets \sum_{i \in S} s_i \mod q$
    \State \Return $(r, s)$ \Comment{ECDSA signature}
\State \textbf{end function}
\end{algorithmic}


\textbf{Security Properties:}
\begin{itemize}
\item UC-secure against malicious adversaries
\item $t$-privacy: $< t$ shares reveal nothing about private key
\item Non-interactive with preprocessing
\end{itemize}

\subsection{MuSig2: Bitcoin Taproot Aggregation}

MuSig2 \cite{musig2} provides Schnorr signature aggregation for Bitcoin.



\begin{algorithmic}[1]
\State \textbf{function} \textsc{MuSig2Sign}($message, \{sk_i\}_{i \in S}$)
    \State \textbf{KeyGen:} Compute aggregate public key
    \State $L \gets \text{Hash}(\{pk_1, \ldots, pk_n\})$
    \For{each $i$}
        \State $a_i \gets \text{Hash}(L, pk_i)$
    \EndFor
    \State $PK \gets \sum_{i} a_i \cdot pk_i$
    \State
    \State \textbf{Nonce Exchange:}
    \For{each $i$}
        \State $(r_i^1, r_i^2) \gets (\text{Random}(), \text{Random}())$
        \State $(R_i^1, R_i^2) \gets (r_i^1 \cdot G, r_i^2 \cdot G)$
        \State Broadcast $(R_i^1, R_i^2)$
    \EndFor
    \State
    \State \textbf{Signing:}
    \State $R \gets \sum_{i} R_i^1 + b \sum_{i} R_i^2$ \Comment{$b = \text{Hash}(PK, R_i^*, m)$}
    \State $c \gets \text{Hash}(PK, R, message)$
    \For{each $i$}
        \State $s_i \gets r_i^1 + b \cdot r_i^2 + c \cdot a_i \cdot sk_i$
        \State Broadcast $s_i$
    \EndFor
    \State $s \gets \sum_i s_i$
    \State \Return $(R, s)$ \Comment{Schnorr signature}
\State \textbf{end function}
\end{algorithmic}


\subsection{FROST: Flexible EdDSA Threshold}

FROST \cite{frost} provides threshold EdDSA for XRPL and Solana.



\begin{algorithmic}[1]
\State \textbf{function} \textsc{FrostSign}($message, \{share_i\}_{i \in S}, threshold$)
    \State \textbf{Commitment Phase:}
    \For{each $i \in S$}
        \State $(d_i, e_i) \gets (\text{Random}(), \text{Random}())$
        \State $(D_i, E_i) \gets (d_i \cdot B, e_i \cdot B)$ \Comment{$B$ is EdDSA base}
        \State Broadcast $(D_i, E_i)$
    \EndFor
    \State
    \State \textbf{Signature Generation:}
    \State $\rho_i \gets \text{Hash}(i, m, \{D_j, E_j\}_{j \in S})$ for all $i$
    \State $R \gets \sum_{i \in S} (D_i + \rho_i \cdot E_i)$
    \State $c \gets \text{Hash}(R, PK, message)$
    \For{each $i \in S$}
        \State $\lambda_i \gets \text{LagrangeCoeff}(i, S)$
        \State $z_i \gets d_i + \rho_i \cdot e_i + \lambda_i \cdot share_i \cdot c$
        \State Broadcast $z_i$
    \EndFor
    \State $z \gets \sum_{i \in S} z_i$
    \State \Return $(R, z)$ \Comment{EdDSA signature}
\State \textbf{end function}
\end{algorithmic}


\subsection{Corona: Post-Quantum Threshold}

Corona \cite{corona} provides lattice-based threshold signatures.



\begin{algorithmic}[1]
\State \textbf{function} \textsc{CoronaSign}($message, \{share_i\}_{i \in S}$)
    \State \textbf{Lattice Setup:} $n = 1024, q = 2^{32} - 5$
    \State
    \State \textbf{Round 1: Share Generation}
    \For{each $i \in S$}
        \State $y_i \gets \text{SampleGaussian}(\sigma = 3.2)^n$
        \State $w_i \gets A \cdot y_i \mod q$ \Comment{$A$ is public matrix}
        \State Broadcast $w_i$
    \EndFor
    \State
    \State \textbf{Round 2: Challenge Computation}
    \State $w \gets \sum_{i \in S} w_i \mod q$
    \State $c \gets \text{Hash}(w, message)$ \Comment{Challenge}
    \State
    \State \textbf{Round 3: Response Generation}
    \For{each $i \in S$}
        \State $z_i \gets y_i + c \cdot share_i$
        \State Broadcast $z_i$
    \EndFor
    \State
    \State \textbf{Combine:}
    \State $z \gets \sum_{i \in S} z_i$
    \State \Return $(w, z, c)$ \Comment{Lattice signature}
\State \textbf{end function}
\end{algorithmic}


\textbf{Security:} Based on LWE (Learning With Errors) hardness, resistant to Shor's algorithm.