papers/lux-corona-pq/sections/01-introduction.tex

\section{Introduction}

\label{sec:introduction}

Threshold signatures enable a group of $n$ parties to collaboratively sign messages
such that any subset of $t$ or more parties can produce a valid signature, but fewer
than $t$ parties cannot. In blockchain consensus, threshold signatures aggregate
validator votes into compact block certificates, reducing verification from $O(n)$
individual signature checks to a single aggregate verification.

Classical threshold schemes---BLS threshold~\cite{boldyreva2003threshold},
FROST~\cite{komlo2020frost}, and CGGMP21~\cite{canetti2021uc}---rely on discrete
logarithm or pairing assumptions vulnerable to Shor's algorithm~\cite{shor1997polynomial}.
Post-quantum threshold signatures based on lattice assumptions remain an active area
of research. Ringtail\footnote{``Ringtail'' is named for the ringtail, a small mammal of
the raccoon family---the scheme thresholdizes the \emph{Raccoon} signature
family~\cite{raccoon,traccoon}. The name is \emph{not} a reference to Ring-LWE: Ringtail,
and hence Corona, is instantiated over a module of rank $N' = 7$ (a genuine matrix
$\mathbf{A} \in R_q^{8 \times 7}$), so its hardness is Module-LWE. It coincides with
Ring-LWE only in the degenerate rank-1 case, which Corona does not use.} is a practical
two-round Module-LWE threshold construction; that construction, however, assumes a fixed,
known set of parties, which is precisely the assumption a public chain cannot make.

Corona is the first member of the Lux lattice threshold-signature family by development
age: a two-round Module-LWE threshold scheme, derived from Ringtail (\S\ref{sec:related}),
together with its native verifier. Corona works over the cyclotomic ring
$R_q = \mathbb{Z}_q[X]/(X^N + 1)$ with $N = 256$, instantiated as a module of dimension
$M = 8 \times N' = 7$: the public key is a matrix relation
$\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$ with $\mathbf{A} \in R_q^{M \times N'}$,
$\mathbf{s} \in R_q^{N'}$, and $\mathbf{e} \in R_q^{M}$. Corona and Pulsar~\cite{pulsar}
(LP-4450) are \emph{both} Module-LWE threshold schemes; they differ by parameter regime,
lifecycle, and codebase, not by module rank. The design prioritizes:
\begin{itemize}[nosep]
\item \textbf{Low round complexity}: 2 rounds (1 message-independent precomputation and commitment + 1 signing), then a non-interactive combine. Two rounds is optimal for any dealer-free threshold scheme.
\item \textbf{Compact signature}: $\sim$33--35\,KB, acceptable for block certificates.
\item \textbf{Fast verification}: $\sim$1.6\,ms (one matrix relation check and one hash evaluation).
\item \textbf{Standard assumptions}: Module-LWE with Module-SIS commitments, Category~1 parameters.
\item \textbf{Permissionless operation}: leaderless distributed key generation with no trusted dealer, and dynamic resharing across a validator set that changes over time.
\end{itemize}

Corona's distinguishing contribution is engineering, not a new hardness assumption: it
takes the academic two-round lattice threshold structure and makes it run on a
\emph{public, permissionless} validator set. Where the academic construction fixes the
participant set in advance, Corona supports validators joining and leaving
permissionlessly through leaderless distributed key generation (Feldman/Pedersen
commitments, no trusted dealer, no party ever holding the full key), dynamic resharing
across generations, and on-chain ceremony binding anchored to the Lux Q-Chain.

\paragraph{Contributions.}
\begin{enumerate}[nosep]
\item The Corona two-round threshold signature scheme over Module-LWE with Module-SIS commitments (\S\ref{sec:scheme}).
\item EUF-CMA security proof reducing to Module-LWE and Module-SIS hardness in the random oracle model (\S\ref{sec:security}).
\item Permissionless, leaderless distributed key generation and resharing for validator sets that change over time, anchored to an on-chain ceremony root (\S\ref{sec:scheme}, \S\ref{sec:integration}).
\item Concrete Category~1 parameters with security estimates (\S\ref{sec:security}).
\item Integration as the Aurora-profile intra-lattice diversity leg under Lux Quasar (\S\ref{sec:integration}).
\item Benchmarks: $\sim$33--35\,KB signatures, $\sim$1.6\,ms verification (\S\ref{sec:evaluation}).
\end{enumerate}

%% -----------------------------------------------------------------------
%%  2. PRELIMINARIES
%% -----------------------------------------------------------------------