papers/lux-validator-mpc/sections/03-distributed-key-generation.tex

\section{Distributed Key Generation}

\label{sec:dkg}

\subsection{Dealerless Pedersen DKG}

We use Pedersen's dealerless DKG~\cite{pedersen1991threshold} with Feldman's
verifiable secret sharing (VSS)~\cite{feldman1987practical}.

\begin{algorithm}[ht]
\caption{Dealerless DKG for $(t, n)$ threshold.}
\label{alg:dkg}
\begin{algorithmic}[1]
\Require $n$ parties $P_1, \ldots, P_n$; threshold $t$
\Ensure Each $P_i$ holds share $sk_i$; public key $pk = sk \cdot G$
\ForAll{$P_i$, $i = 1, \ldots, n$}
  \State Sample random polynomial $f_i(x) = a_{i,0} + a_{i,1}x + \cdots + a_{i,t-1}x^{t-1}$
  \State Broadcast commitments $C_{i,j} = a_{i,j} \cdot G$ for $j = 0, \ldots, t-1$
  \State Send share $s_{i \to j} = f_i(j)$ to each $P_j$ via encrypted channel
\EndFor
\ForAll{$P_j$, $j = 1, \ldots, n$}
  \ForAll{received shares $s_{i \to j}$}
    \State Verify: $s_{i \to j} \cdot G \stackrel{?}{=} \sum_{k=0}^{t-1} j^k \cdot C_{i,k}$
    \State If verification fails, broadcast complaint against $P_i$
  \EndFor
  \State $sk_j \leftarrow \sum_{i=1}^{n} s_{i \to j}$ \Comment{Aggregate shares}
\EndFor
\State $pk \leftarrow \sum_{i=1}^{n} C_{i,0}$ \Comment{Public key from commitments}
\end{algorithmic}
\end{algorithm}

\begin{theorem}[DKG security]
\label{thm:dkg}
If $< t$ parties are corrupted, the Pedersen DKG protocol produces shares of a
uniformly random key $sk$ such that no coalition of $< t$ corrupted parties can
distinguish $sk$ from a random element of $\mathbb{Z}_q$.
\end{theorem}

\begin{proof}[Proof sketch]
Each honest party contributes a uniformly random $a_{i,0}$. The master key
$sk = \sum_i a_{i,0}$ is uniformly random as long as at least one honest party's
$a_{i,0}$ is unknown to the adversary. With $< t$ corruptions and $n \geq 2t - 1$,
at least $t$ parties are honest, and the sum of their contributions masks the
corrupted parties' contributions.
\end{proof}

\subsection{Verifiable Share Distribution}

Feldman VSS commitments $C_{i,j} = a_{i,j} \cdot G$ are binding under the discrete
logarithm assumption and enable public verification of shares without revealing the
polynomial coefficients. Any observer can verify the commitment consistency:
\[
  s_{i \to j} \cdot G = \sum_{k=0}^{t-1} j^k \cdot C_{i,k}
\]

This ensures that a malicious party cannot distribute inconsistent shares (equivocation).

%% ========================================================================
%%  4. CGGMP21: THRESHOLD ECDSA
%% ========================================================================