papers/lux-universal-threshold-signatures/sections/02-background.tex

\section{Background}


\subsection{Threshold Cryptography}

A $(t,n)$-threshold signature scheme distributes signing authority among $n$ parties such that any subset of size $t+1$ can collaboratively generate valid signatures, while no coalition of $t$ or fewer parties can forge signatures or reconstruct the private key.

\begin{definition}[Threshold Signature Scheme]
A $(t,n)$-threshold signature scheme consists of:
\begin{itemize}
\item \textbf{KeyGen}$(1^\lambda, t, n) \to (\textsf{pk}, \{\textsf{sk}_i\}_{i=1}^n)$: Distributed key generation producing public key $\textsf{pk}$ and private shares $\textsf{sk}_i$
\item \textbf{Sign}$(m, S, \{\textsf{sk}_i\}_{i \in S}) \to \sigma$: Collaborative signing where $|S| \geq t+1$
\item \textbf{Verify}$(m, \sigma, \textsf{pk}) \to \{0,1\}$: Standard signature verification
\end{itemize}
\end{definition}

\subsection{Digital Signature Schemes}

\paragraph{ECDSA} The Elliptic Curve Digital Signature Algorithm is used by Bitcoin, Ethereum, and XRPL. Signatures are $(r,s)$ pairs where:
\begin{align*}
r &= (k \cdot G)_x \bmod q \\
s &= k^{-1}(H(m) + r \cdot x) \bmod q
\end{align*}

\paragraph{EdDSA} Edwards-curve Digital Signature Algorithm (Ed25519) is used by Solana, Cardano, TON, and NEAR. Signatures are $(R, s)$ where:
\begin{align*}
R &= r \cdot B \\
s &= r + H(R, A, m) \cdot a
\end{align*}

\paragraph{Schnorr} Bitcoin Taproot (BIP-340) uses Schnorr signatures $(R, s)$ with:
\begin{align*}
s = k + H(R, P, m) \cdot x
\end{align*}

\subsection{Post-Quantum Cryptography}

Quantum computers threaten all elliptic curve and factoring-based schemes via Shor's algorithm \cite{shor1997}. NIST's post-quantum standardization selected lattice-based schemes (ML-DSA, ML-KEM) for quantum resistance. Module-LWE hardness provides security assumptions for lattice cryptography.

\subsection{Related Work}

\paragraph{GG18/GG20} Gennaro-Goldfeder protocols \cite{gennaro2018,gennaro2020} introduced MPC-based ECDSA threshold signatures but lacked identifiable abort.

\paragraph{CGGMP21} Canetti et al. \cite{canetti2021} (CMP protocol) added identifiable aborts, 4-round online signing, and proactive refresh.

\paragraph{FROST} Komlo-Goldberg \cite{komlo2020} developed efficient 2-round threshold Schnorr signatures with pre-processing.

\paragraph{Two-Party ECDSA} Doerner et al. \cite{doerner2018} optimized 2-of-2 ECDSA for constant-time performance.