papers/lux-corona-pq/sections/03-the-corona-scheme.tex

\section{The Corona Scheme}

\label{sec:scheme}

Corona is a two-round Module-LWE threshold signature over the module $R_q^{N'}$. The
public key is a matrix relation $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$ with
public matrix $\mathbf{A} \in R_q^{M \times N'}$, secret $\mathbf{s} \in R_q^{N'}$, and
error $\mathbf{e} \in R_q^{M}$. We first describe the leaderless distributed key
generation (no trusted dealer), then the two-round signing protocol, then the
non-interactive combine and verification. Throughout, $\mathcal{S}$ denotes a signing
set with $|\mathcal{S}| \ge t$, and $\lambda_i \in \mathbb{Z}_q$ are the Lagrange
coefficients of~\eqref{eq:lagrange} for the set $\mathcal{S}$.

\subsection{Distributed Key Generation (Leaderless, No Trusted Dealer)}

The public matrix $\mathbf{A} \in R_q^{M \times N'}$ is a fixed, publicly derivable
parameter (a nothing-up-my-sleeve hash output expanded from the ceremony root), so no
party controls it. The secret $\mathbf{s} \in R_q^{N'}$ is generated jointly: each party
contributes an additive summand and a verifiable Shamir sharing of that summand, so the
group secret is $\mathbf{s} = \sum_{i} \mathbf{s}^{(i)}$ and no party ever sees
$\mathbf{s}$.

\begin{algorithm}[H]
\caption{Corona Distributed Key Generation}
\label{alg:keygen}
\begin{algorithmic}[1]
\Require Threshold $t$, parties $n$, parameters $(N, q, M, N', \sigma_e)$, ceremony root $\rho$
\State $\mathbf{A} \gets \mathrm{Expand}_{R_q^{M \times N'}}(\rho)$ \Comment{public matrix, derived (no dealer)}
\For{each party $i \in \{1, \ldots, n\}$} \Comment{run in parallel; leaderless}
    \State $\mathbf{s}^{(i)} \stackrel{\$}{\leftarrow} D_{\sigma_e}^{N'}$, \quad $\mathbf{e}^{(i)} \stackrel{\$}{\leftarrow} D_{\sigma_e}^{M}$ \Comment{$i$'s short secret/error summands}
    \State $\mathbf{f}^{(i)}(X') \gets \mathbf{s}^{(i)} + \sum_{\ell=1}^{t-1} \mathbf{a}^{(i)}_\ell (X')^\ell$, \quad $\mathbf{a}^{(i)}_\ell \stackrel{\$}{\leftarrow} R_q^{N'}$ \Comment{Shamir polys over $R_q$}
    \State Broadcast Feldman/Pedersen commitments to $\mathbf{s}^{(i)}$ and $\{\mathbf{a}^{(i)}_\ell\}$
    \State Send share $\mathbf{s}^{(i)}_j \gets \mathbf{f}^{(i)}(\mathrm{id}_j)$ privately to each party $j$
\EndFor
\For{each party $j$} \Comment{verify and aggregate}
    \State \textbf{abort/identify} any party $i$ whose share $\mathbf{s}^{(i)}_j$ contradicts its commitments
    \State $\mathbf{s}_j \gets \sum_{i} \mathbf{s}^{(i)}_j$ \Comment{$j$'s aggregate share of $\mathbf{s} = \sum_i \mathbf{s}^{(i)}$}
\EndFor
\State $\mathbf{b} \gets \mathbf{A}\mathbf{s} + \mathbf{e}$, \quad $\mathbf{e} = \sum_i \mathbf{e}^{(i)}$ \Comment{public key, recombined from commitments}
\State $\tilde{\mathbf{b}} \gets \mathrm{Round}(\mathbf{b}, \xi)$ \Comment{rounded for verification}
\State \Return pk $= (\mathbf{A}, \tilde{\mathbf{b}})$, \; shares $\{\mathbf{s}_j\}_{j=1}^{n}$ \Comment{group secret $\mathbf{s}$ never reconstructed}
\end{algorithmic}
\end{algorithm}

\noindent The public key $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$ is a Module-LWE
sample (Definition~\ref{def:mlwe}): recovering $\mathbf{s}$ from $(\mathbf{A}, \mathbf{b})$
is the Module-LWE search problem. Because $\mathbf{A}$ is derived from the ceremony root
and every contribution is committed, the protocol is leaderless and robust against an
adversary controlling up to $t-1$ parties; corrupted shares are caught by commitment
verification (identifiable abort). Resharing for a changed validator set re-runs
Algorithm~\ref{alg:keygen} over the new set, with the group public key
$\tilde{\mathbf{b}}$ held fixed across generations (see~\S\ref{sec:integration}).

\subsection{Signing Protocol (2 Rounds)}

Round~1 is message-independent and can be precomputed. Each signer commits to a short
masking vector $\mathbf{y}_i \in R_q^{N'}$ via $\mathbf{w}_i = \mathbf{A}\mathbf{y}_i$;
correlated randomness with pairwise cancellation keeps the aggregate mask short, and
per-message MACs authenticate commitments against malicious injection.

\begin{algorithm}[H]
\caption{Corona Signing --- Round 1 (Message-Independent)}
\label{alg:sign-r1}
\begin{algorithmic}[1]
\Require Party $i$, signers set $\mathcal{S}$ with $|\mathcal{S}| \geq t$, session id $\mathsf{sid}$
\State $\mathbf{r}_i \gets \text{PRF}(\text{key}_i, \mathsf{sid} \| i) \bmod D_{\sigma^*}$ \Comment{$i$'s short mask $\in R_q^{N'}$}
\For{each party $j \in \mathcal{S} \setminus \{i\}$}
    \State $\mathbf{r}_{i,j} \gets \text{PRF}(\text{seed}_{i,j}, \mathsf{sid})$ \Comment{pairwise correlated randomness $\in R_q^{N'}$}
\EndFor
\State $\mathbf{y}_i \gets \mathbf{r}_i + \sum_{j : j > i} \mathbf{r}_{i,j} - \sum_{j : j < i} \mathbf{r}_{j,i}$ \Comment{masked randomness, pairwise cancellation}
\State $\mathbf{w}_i \gets \mathbf{A}\mathbf{y}_i$ \Comment{commitment (matrix-vector product)}
\For{each $j \in \mathcal{S} \setminus \{i\}$}
    \State $\text{mac}_{i \to j} \gets \text{HMAC}(\text{MACkey}_{i \to j}, \mathsf{sid} \| \mathbf{w}_i)$
\EndFor
\State \textbf{broadcast} $(\mathbf{w}_i, \{\text{mac}_{i \to j}\}_{j \in \mathcal{S}})$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{Corona Signing --- Round 2 (Message-Dependent)}
\label{alg:sign-r2}
\begin{algorithmic}[1]
\Require Party $i$, message $\mu$, Round 1 data $\{(\mathbf{w}_j, \text{mac}_j)\}_{j \in \mathcal{S}}$
\For{each $j \in \mathcal{S} \setminus \{i\}$}
    \State Verify $\text{mac}_{j \to i}$ using $\text{MACkey}_{j \to i}$; \textbf{abort} (identify $j$) if it fails
\EndFor
\State $\mathbf{w} \gets \sum_{j \in \mathcal{S}} \mathbf{w}_j$ \Comment{combined commitment $\in R_q^{M}$ (plain sum; Lagrange weight is carried in $\mathbf{z}_i$)}
\State $c \gets H(\mathbf{A}, \tilde{\mathbf{b}}, \mathbf{w}, \mu)$ \Comment{challenge: ternary polynomial in $R_q$, weight $\kappa$}
\State $\mathbf{z}_i \gets \mathbf{y}_i + c \cdot \lambda_i \cdot \mathbf{s}_i$ \Comment{partial response (ring multiplication)}
\If{$\|\mathbf{z}_i\|_\infty > B$} \Comment{Fiat--Shamir-with-aborts rejection sampling}
    \State \textbf{abort} and restart with a fresh session id
\EndIf
\State \textbf{broadcast} $\mathbf{z}_i$
\end{algorithmic}
\end{algorithm}

\subsection{Combine and Verification}

The combine is non-interactive: any party or external aggregator sums the partial
responses into a single response vector
\[
\mathbf{z} \;=\; \sum_{i \in \mathcal{S}} \mathbf{z}_i \;\in\; R_q^{N'} ,
\]
and outputs the signature $(c, \mathbf{z})$. Because each partial already carries its
Lagrange weight ($\mathbf{z}_i = \mathbf{y}_i + c \lambda_i \mathbf{s}_i$), by linearity
and the Lagrange reconstruction of~\eqref{eq:lagrange},
$\mathbf{z} = \mathbf{y} + c \cdot \mathbf{s}$ where
$\mathbf{y} = \sum_{i} \mathbf{y}_i$ masks the short secret $\mathbf{s}$
(the pairwise correlated randomness of Algorithm~\ref{alg:sign-r1} cancels under this
plain sum), so
$\mathbf{A}\mathbf{z} - c \cdot \mathbf{b} = \mathbf{A}\mathbf{y} - c \cdot \mathbf{e} \approx \mathbf{w}$.

Verification of $(c, \mathbf{z})$ against pk $= (\mathbf{A}, \tilde{\mathbf{b}})$ and
message $\mu$ checks:
\begin{enumerate}[nosep]
\item $\|\mathbf{z}\|_\infty \leq B'$ (the response is short, for the combined bound $B'$);
\item recompute $\mathbf{w}' \gets \mathbf{A}\mathbf{z} - c \cdot \tilde{\mathbf{b}} \in R_q^{M}$ and check $c = H(\mathbf{A}, \tilde{\mathbf{b}}, \mathrm{Round}(\mathbf{w}', \xi), \mu)$.
\end{enumerate}
Both checks are one matrix-vector product over $R_q$ plus one hash, giving the
$\sim$1.6\,ms verification of \S\ref{sec:evaluation}. A successful forgery on a fresh
message yields a short $\mathbf{z}^*$ with $\mathbf{A}\mathbf{z}^* \approx \mathbf{w}^* + c^* \cdot \tilde{\mathbf{b}}$,
i.e.\ a short Module-SIS solution relative to $\mathbf{A}$ (Definition~\ref{def:msis});
this is the basis of the reduction in~\S\ref{sec:security}.

%% -----------------------------------------------------------------------
%%  4. SECURITY ANALYSIS
%% -----------------------------------------------------------------------