papers/lux-corona-pq/sections/02-preliminaries.tex

\section{Preliminaries}

\label{sec:prelim}

\subsection{The Cyclotomic Ring}

Let $R = \mathbb{Z}[X]/(X^N + 1)$ and $R_q = \mathbb{Z}_q[X]/(X^N + 1)$ where $N$ is
a power of 2 and $q$ is a prime with $q \equiv 1 \pmod{2N}$ (enabling the number-theoretic
transform, NTT). Elements of $R_q$ are polynomials of degree $< N$ with coefficients in
$\mathbb{Z}_q$; the ring product is polynomial multiplication reduced modulo $X^N + 1$.
For $f \in R_q$ we write $\|f\|_\infty$ for the largest absolute value of its coefficients
(centred representatives in $(-q/2, q/2]$), extended entrywise to vectors and matrices over
$R_q$, and $D_\sigma$ for the discrete Gaussian over $R$ of width $\sigma$ applied
coefficient-wise. Corona operates over a \emph{module} $R_q^{N'}$: the public key, secret,
error and signing values are vectors or matrices over $R_q$, not single ring elements.

\begin{definition}[Module-LWE]
\label{def:mlwe}
The (decisional) Module-LWE problem with parameters $(N, q, M, N', \sigma)$ is: given a
uniformly random matrix $\mathbf{A} \stackrel{\$}{\leftarrow} R_q^{M \times N'}$ and
$\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$, where
$\mathbf{s} \stackrel{\$}{\leftarrow} D_\sigma^{N'}$ and
$\mathbf{e} \stackrel{\$}{\leftarrow} D_\sigma^{M}$ are short (discrete Gaussian of width
$\sigma$) and $\mathbf{A}\mathbf{s}$ uses ring multiplication in $R_q$, distinguish
$(\mathbf{A}, \mathbf{b})$ from $(\mathbf{A}, \mathbf{u})$ where
$\mathbf{u} \stackrel{\$}{\leftarrow} R_q^{M}$~\cite{langlois2015module}.
\end{definition}

\begin{remark}[Module rank]
\label{rem:rank}
Module-LWE at module rank one ($N' = 1$, $M = 1$) coincides with Ring-LWE over a single
ring element. Corona is \emph{not} instantiated at rank one: it uses a module of dimension
$M = 8 \times N' = 7$ (a genuine matrix $\mathbf{A} \in R_q^{8 \times 7}$). Pulsar
(LP-4450) is likewise a Module-LWE scheme; Corona and Pulsar differ by parameter regime
and lifecycle, not by module rank.
\end{remark}

\begin{definition}[Module-SIS]
\label{def:msis}
The Module-SIS problem with parameters $(N, q, M, \beta)$ is: given a uniformly random
matrix $\mathbf{A} \stackrel{\$}{\leftarrow} R_q^{M \times N'}$, find a nonzero
$\mathbf{z} \in R_q^{N'}$ with $\|\mathbf{z}\|_\infty \le \beta$ and
$\mathbf{A}\mathbf{z} = \mathbf{0}$ in $R_q^{M}$. Corona's commitments are binding under
Module-SIS, and a forgery yields a short Module-SIS solution relative to $\mathbf{A}$.
\end{definition}

\subsection{Shamir Secret Sharing over $R_q$}

The secret key is a short vector $\mathbf{s} \in R_q^{N'}$. Each component $s_j$ is shared
with one degree-$(t-1)$ polynomial over the ring.

\begin{definition}[Ring-Based Shamir Sharing]
\label{def:shamir}
Given a secret vector $\mathbf{s} = (s_1, \ldots, s_{N'}) \in R_q^{N'}$, share each
component $s_j$ via $f_j(X') = s_j + \sum_{i=1}^{t-1} a_{j,i} (X')^i \in R_q[X']$, with
$a_{j,i} \stackrel{\$}{\leftarrow} R_q$, evaluated at distinct public points
$X' = \mathrm{id}_i \in \mathbb{Z}_q$ (the sharing indeterminate $X'$ is distinct from the
ring indeterminate $X$). Party $i$ receives the share
$\mathbf{s}_i = (f_1(\mathrm{id}_i), \ldots, f_{N'}(\mathrm{id}_i)) \in R_q^{N'}$.
\end{definition}

Lagrange interpolation over $R_q$ reconstructs $\mathbf{s}$ from any $t$ shares:
\begin{equation}
\mathbf{s} = \sum_{i \in S} \lambda_i \cdot \mathbf{s}_i, \qquad
\lambda_i = \prod_{j \in S,\, j \neq i} \frac{\mathrm{id}_j}{\mathrm{id}_j - \mathrm{id}_i} \in \mathbb{Z}_q
\label{eq:lagrange}
\end{equation}
where the Lagrange coefficients $\lambda_i$ are scalars in $\mathbb{Z}_q$ (embedded in $R_q$).

\subsection{Corona Parameters}

\begin{table}[h]
\centering
\begin{tabular}{@{}lll@{}}
\toprule
\textbf{Parameter} & \textbf{Symbol} & \textbf{Value} \\
\midrule
Ring degree & $N$ & 256 \quad ($\log_2 N = 8$) \\
Modulus & $q$ & $\texttt{0x1000000004A01}$ \quad (48-bit, $q \equiv 1 \bmod 2N$) \\
Module rows & $M$ & 8 \\
Module columns & $N'$ & 7 \\
Gaussian width (key gen) & $\sigma_e$ & 6.108 \\
Gaussian width (signing) & $\sigma^*$ & $2^{37.33}$ \\
Rejection bound & $B$ & $2^{48.6}$ \\
Challenge ternary weight & $\kappa$ & 23 \\
Rounding parameter & $\xi$ & 30 \\
\bottomrule
\end{tabular}
\caption{Corona parameters (NIST Category~1, Module-LWE). The module dimension
$M = 8 \times N' = 7$ and the 48-bit prime are the canonical values of the reference
implementation~\cite{corona} (a fork of \texttt{luxfi/ringtail}); the detailed sampler
and rejection bounds are fixed by that code and its KAT vectors. These parameters are
\emph{not} byte-equal to any FIPS standard; FIPS~204 byte-equality is a property of the
sibling scheme Pulsar (LP-4450).}
\label{tab:params}
\end{table}

%% -----------------------------------------------------------------------
%%  3. THE MODULE-LWE THRESHOLD SCHEME
%% -----------------------------------------------------------------------