papers/lux-corona-pq/sections/04-security-analysis.tex

\section{Security Analysis}

\label{sec:security}

\subsection{Unforgeability}

\begin{theorem}[EUF-CMA Security]
\label{thm:euf-cma}
Corona is existentially unforgeable under chosen-message attacks in the random oracle
model, assuming the hardness of Module-LWE$(N, q, M, N', \sigma_e)$
(Definition~\ref{def:mlwe}) and Module-SIS$(N, q, M, \beta)$ (Definition~\ref{def:msis}).
Concretely, any adversary making $Q_H$ hash queries and $Q_S$ signing queries has
advantage:
\[
\text{Adv}^{\text{EUF-CMA}} \leq \text{Adv}^{\text{MLWE}} + Q_H \cdot \text{Adv}^{\text{MSIS}} + \frac{Q_S}{2^{128}} .
\]
\end{theorem}

\begin{remark}[Proof-level assumptions]
The bound above states the two \emph{standard} lattice assumptions for readability.
Ringtail's full proof~\cite{ringtail} reduces unforgeability to \emph{self-target}
Module-SIS (equivalent to Module-SIS in the ROM via the forking lemma) and to
\emph{Hint}-Module-LWE~\cite{hintmlwe}---a leakage variant that models the offline
commitment matrices---both of which reduce to standard Module-LWE and Module-SIS for the
parameters of Table~\ref{tab:params}. Corona inherits these reductions verbatim from the
Raccoon/Ringtail line; its permissionless distributed key generation and resharing affect
only key generation, not the per-signature unforgeability argument.
\end{remark}

\begin{proof}
We proceed through a sequence of games.

\textbf{Game 0}: The real EUF-CMA game. The adversary controls $t-1$ parties and
interacts with the signing oracle.

\textbf{Game 1}: Replace the public key $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$
with a uniformly random $\mathbf{u} \stackrel{\$}{\leftarrow} R_q^{M}$. The distinguishing
advantage between Games 0 and 1 is $\text{Adv}^{\text{MLWE}}$ by
Definition~\ref{def:mlwe}: the pair $(\mathbf{A}, \mathbf{b})$ is exactly a Module-LWE
sample and $(\mathbf{A}, \mathbf{u})$ its uniform counterpart.

\textbf{Game 2}: In Game 1 the public key $\mathbf{b} = \mathbf{u}$ is independent of
$\mathbf{s}$. We reprogram the random oracle $H$ to extract the forgery. When the
adversary outputs a forgery $(c^*, \mathbf{z}^*)$ on a fresh $\mu^*$, validity requires
\[
\mathbf{A}\mathbf{z}^* - c^* \cdot \tilde{\mathbf{u}} \;\approx\; \mathbf{w}^*
\qquad\text{with } c^* = H(\mathbf{A}, \tilde{\mathbf{u}}, \mathbf{w}^*, \mu^*),
\]
i.e.\ a short $\mathbf{z}^*$ with $\mathbf{A}\mathbf{z}^* \approx \mathbf{w}^* + c^* \cdot \tilde{\mathbf{u}}$.
Since $\mathbf{u}$ is uniform and independent of $\mathbf{s}$, producing such a short
$\mathbf{z}^*$ is an instance of Module-SIS (Definition~\ref{def:msis}) relative to
$\mathbf{A}$: it yields a short nonzero vector annihilated by $\mathbf{A}$. Each of the
$Q_H$ oracle queries gives one such extraction opportunity, whence the
$Q_H \cdot \text{Adv}^{\text{MSIS}}$ term.

The probability of a challenge collision in $H$ (two queries yielding the same ternary
challenge for different messages) is $\leq Q_H^2 / |C|$, where the challenge space
$|C| = \binom{N}{\kappa} 2^\kappa$ is negligible for $\kappa = 23$ and $N = 256$.

Combining the transitions,
$\text{Adv}^{\text{Game 0}} \leq \text{Adv}^{\text{MLWE}} + Q_H \cdot \text{Adv}^{\text{MSIS}} + Q_H^2 / |C|$.
\end{proof}

\subsection{Threshold Security}

\begin{lemma}[Threshold Unforgeability]
\label{lem:threshold}
An adversary controlling $t-1$ parties and observing $Q_S$ signing sessions cannot
forge a signature on a new message. The adversary's view in each signing session
is statistically close to a simulation that does not use the honest parties' shares,
by the zero-knowledge property of the commitment scheme.
\end{lemma}

\begin{proof}
In each signing session, the adversary sees the honest parties' commitments
$\mathbf{w}_i = \mathbf{A}\mathbf{y}_i$ and responses
$\mathbf{z}_i = \mathbf{y}_i + c \lambda_i \mathbf{s}_i$. Given $\mathbf{w}_i$ and
$\mathbf{z}_i$, the adversary can compute $c \lambda_i \mathbf{s}_i = \mathbf{z}_i - \mathbf{y}_i$.
However, reconstructing $\mathbf{y}_i$ from $\mathbf{w}_i = \mathbf{A}\mathbf{y}_i$ is an
instance of Module-SIS (finding a short preimage of $\mathbf{w}_i$ under $\mathbf{A}$,
Definition~\ref{def:msis}).

The Fiat--Shamir-with-aborts rejection sampling ensures that $\mathbf{z}_i$ is
statistically independent of $\mathbf{s}_i$: the distribution of $\mathbf{z}_i$
conditioned on any $\mathbf{s}_i$ is within statistical distance $2^{-128}$ of the
distribution conditioned on any other $\mathbf{s}_i$, by the properties of discrete
Gaussian rejection sampling with width $\sigma^* \gg \|c \lambda_i \mathbf{s}_i\|_\infty$.

Therefore $t-1$ parties' shares reveal no information about the group secret $\mathbf{s}$
(by the Shamir sharing of Definition~\ref{def:shamir}), and the signing transcripts
reveal no additional information about $\mathbf{s}$ (by the zero-knowledge simulation).
The same argument applies to the distributed key generation: an adversary corrupting up
to $t-1$ parties learns nothing about $\mathbf{s} = \sum_i \mathbf{s}^{(i)}$ beyond what
the public key $\mathbf{b}$ already reveals, since the honest contributions
$\mathbf{s}^{(i)}$ remain hidden behind their commitments.
\end{proof}

\subsection{Concrete Security Estimates}
\label{sec:params}

\begin{proposition}[Security Level]
\label{prop:security-level}
With the Category~1 parameters $N = 256$, $q \approx 2^{48}$, $M = 8$, $N' = 7$,
$\sigma_e = 6.108$ (Table~\ref{tab:params}), the Module-LWE instance reaches NIST
security Category~1: $\sim$128-bit classical and $\sim$130-bit quantum security against
the best known lattice algorithms (BKZ with sieving, Grover-enhanced sieving).
\end{proposition}

\begin{proof}
The Module-LWE instance embeds into an LWE lattice of dimension $d = M \cdot N = 8 \times 256 = 2048$.
The noise ratio is $\alpha = \sigma_e \sqrt{2\pi} / q \approx 15.3 / 2^{48} \approx 2^{-44.1}$.
The primal lattice attack via BKZ with sieving has classical cost
\[
T_{\text{classical}} \approx 2^{0.292\,\beta + o(\beta)},
\]
where the blocksize $\beta$ is the smallest value at which BKZ recovers the secret for the
$(d, q, \sigma_e)$ instance; the geometric-series-assumption estimate
$\delta^{2\beta - d} \cdot q^{d/\beta} = \sigma_e$ gives $\beta \approx 430$ and
$T_{\text{classical}} \approx 2^{142}$. For quantum attacks (Grover-accelerated sieving)
the exponent constant drops to $0.265$, giving $T_{\text{quantum}} \approx 2^{130}$ at the
same blocksize. The Module-SIS commitments are parameterised over the same ring and
modulus and are no easier than the Module-LWE instance. Corona is therefore a Category~1
(Module-LWE) scheme. It is \emph{not} byte-equal to any FIPS standard---byte-equality with
FIPS~204 ML-DSA is a property of the sibling scheme Pulsar (LP-4450), not of Corona.
\end{proof}

%% -----------------------------------------------------------------------
%%  5. INTEGRATION WITH LUX CONSENSUS
%% -----------------------------------------------------------------------