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

\section{Preliminaries}
\label{sec:preliminaries}

\subsection{Notation}
\label{sec:prelim:notation}

\begin{itemize}[nosep,leftmargin=2em]
  \item $\lambda$ --- security parameter (set to $192$ for SHAKE-192s,
        $256$ for SHAKE-256s).
  \item $N$ --- validator-set size at the consensus layer (the
        primary primitive of this paper is $N$-of-$N$ collection;
        a quorum policy of size $K \le N$ filters the count at the
        consumer).
  \item $P_i$ --- validator $i$, $1 \le i \le N$. Each validator is
        identified by a 32-byte $\mathsf{NodeID}$.
  \item $(sk_i, pk_i)$ --- validator $i$'s FIPS 205 SLH-DSA keypair.
        Each validator's keypair is independent of every other
        validator's; there is no shared seed, no DKG, and no
        dealer.
  \item $\sigma_i$ --- validator $i$'s FIPS 205 SLH-DSA signature
        (the wire bytes) on the consensus message.
  \item $\mu$ --- the message being signed; $\mathit{ctx}$ --- the
        FIPS 205 context string ($0$--$255$ bytes).
  \item $\mathit{registry}: \mathsf{NodeID} \to \{0,1\}^{|pk|}$ ---
        the consensus layer's authoritative validator-set
        registry, binding $\mathsf{NodeID}_i$ to $pk_i$.
  \item $\textsc{cSHAKE256}$ --- the cSHAKE256 customisable hash
        from NIST SP 800-185 \cite{sp800185}, with function-name
        string ``Magnetar'' and per-context customisation tags.
  \item $\Vert$ --- byte concatenation; $\oplus$ --- bitwise XOR.
\end{itemize}

\paragraph{Appendix notation.} The appendices on threshold forms
introduce additional symbols: $n$ for committee size, $t$ for
reconstruction threshold, $\mathrm{GF}(p)$ for the Shamir field with
$p = 257$, $S$ for the shared SLH-DSA scheme seed, and
$\mathit{share}_i$ for party $i$'s share. Those symbols are local to
the appendices and do not appear in the main per-validator
standalone construction.

\subsection{FIPS 205 SLH-DSA review}
\label{sec:prelim:slhdsa}

FIPS 205 \cite{fips205} (formerly SPHINCS+ \cite{sphincs}) is the NIST
stateless hash-based signature standard. The Magnetar reference
implementation targets the FIPS 205 SHAKE parameter sets:
\begin{table}[H]
\centering
\caption{FIPS 205 SHAKE parameter sets exposed by Magnetar v1.0.
Values from FIPS 205 \cite{fips205} \S10.1 Table~2.}
\label{tab:fips205-params}
\begin{tabular}{lrrrrrr}
\toprule
Parameter set & NIST PQ Cat. & $n$ (WOTS+) & $h$ & $d$ & $|pk|$ & $|\sigma|$ \\
\midrule
SLH-DSA-SHAKE-192s & 3 & 24 B & 63 & 7 & 48 B & 16\,224 B \\
SLH-DSA-SHAKE-192f & 3 & 24 B & 66 & 22 & 48 B & 35\,664 B \\
SLH-DSA-SHAKE-256s & 5 & 32 B & 64 & 8 & 64 B & 29\,792 B \\
\bottomrule
\end{tabular}
\end{table}

The FIPS 205 construction is built from the following layered
components, top to bottom:
\begin{itemize}[leftmargin=2em,nosep]
  \item \textbf{XMSS-HT (hypertree)}: a tree of $d$ XMSS layers. The
        leaves of the root layer are XMSS public keys; the leaves of
        the bottom layer are FORS public keys. Every layer has height
        $h/d$.
  \item \textbf{XMSS (eXtended Merkle Signature Scheme)}: a binary
        Merkle tree where each leaf is a WOTS+ public key.
  \item \textbf{WOTS+ (Winternitz One-Time Signature)}: a one-time
        signature whose security reduces to hash function preimage
        and second-preimage resistance.
  \item \textbf{FORS (Forest of Random Subsets)}: the few-time
        signature scheme used at the bottom of the hypertree.
  \item \textbf{Tweakable hash $\mathbf{F}, \mathbf{H}, \mathbf{T}_\ell$}:
        the cryptographic primitives, instantiated as SHAKE256 for the
        SHAKE-family Magnetar targets.
\end{itemize}

\paragraph{Key generation.} $\textsc{KeyGen}$ \cite{fips205}~\S9.1
samples a $3n$-byte secret triple $(\mathit{SK.seed},
\mathit{SK.prf}, \mathit{PK.seed})$ and computes
$\mathit{PK.root} = \mathbf{T}_h(\mathit{SK.seed}, \mathit{PK.seed},
\textsc{ADRS})$ as the XMSS-HT root. The public key is
$pk = (\mathit{PK.seed}, \mathit{PK.root})$; the secret key is
$sk = (\mathit{SK.seed}, \mathit{SK.prf}, \mathit{PK.seed},
\mathit{PK.root})$. The total scheme-seed size (the input to
$\textsc{DeriveKey}$) is $4n$ bytes: $96$ for $n=24$ (192s/192f) and
$128$ for $n=32$ (256s).

\paragraph{Deterministic signing.} $\textsc{Sign}_{\mathrm{det}}(sk, \mu,
\mathit{ctx})$ \cite{fips205}~\S9.2 computes a randomiser
$R \gets \mathrm{PRF}_{\mathit{SK.prf}}(\mathit{ctx} \Vert \mu)$ and
proceeds deterministically. The output is byte-identical across calls
with the same $(sk, \mu, \mathit{ctx})$. The Magnetar per-validator
standalone primitive uses this variant; the byte-identity claim
against \texttt{cloudflare/circl/sign/slhdsa.Verify} pins to this
determinism.

\paragraph{Randomised signing.} $\textsc{Sign}_{\mathrm{rand}}(sk,
\mathit{rng}, \mu, \mathit{ctx})$ \cite{fips205}~\S9.2 samples a fresh
$n$-byte randomiser from $\mathit{rng}$. The Magnetar
\texttt{ValidatorSign} entry point routes to the deterministic
variant by default (\texttt{rng=nil}); passing a non-nil reader
selects the randomised variant for callers who specifically want
hedging against fault injection on the $\mathit{PRF}$ derivation.

\paragraph{Verification.} $\textsc{Verify}(pk, \mu, \sigma,
\mathit{ctx})$ \cite{fips205}~\S9.3 walks the XMSS-HT root, recomputes
$\mathit{PK.root}$ from the FORS and XMSS authentication paths in
$\sigma$, and accepts iff it matches the $\mathit{PK.root}$ embedded
in $pk$. The verifier consumes no secret material; \emph{any
unmodified FIPS 205 verifier accepts a Magnetar signature with no
code change}.

\subsection{Per-validator standalone signature syntax}
\label{sec:prelim:standalone-syntax}

The primary primitive of this paper is a per-validator standalone
SLH-DSA construction. The syntax is the single-party FIPS 205 syntax,
replicated independently $N$ times, plus an aggregate-certificate
shape at the consensus layer.

\begin{definition}[Per-validator standalone signature scheme]
\label{def:standalone-syntax}
$\Pi_{\mathrm{Magnetar}}^{\mathrm{std}}$ is a tuple of probabilistic
polynomial-time algorithms
$(\textsc{KeyGen}, \textsc{Sign}, \textsc{BatchVerify},
\textsc{BuildCert}, \textsc{VerifyCert})$:
\begin{itemize}[nosep,leftmargin=2em]
  \item $\textsc{KeyGen}(1^\lambda)$: each validator $i$ runs this
        independently on its own host. Outputs an SLH-DSA keypair
        $(sk_i, pk_i)$. No interaction.
  \item $\textsc{Sign}(sk_i, \mu, \mathit{ctx})$: validator $i$'s
        signing primitive. Returns
        $\sigma_i = \textsc{slhdsa.SignDeterministic}(sk_i, \mu,
        \mathit{ctx})$. Deterministic.
  \item $\textsc{BatchVerify}(\{pk_i\}, \mu, \{\sigma_i\}) \to
        \mathit{bitmap}$: returns a Boolean bitmap indicating
        per-signer FIPS 205 verifier acceptance. Pure function of
        public inputs.
  \item $\textsc{BuildCert}(\mathit{Mode},
        \{\mathsf{NodeID}_i, pk_i, \sigma_i\}_{i \in S})$: assembles
        the on-wire $\mathit{ValidatorAggregateCert}$ carrying the
        parallel-slices triple $(\mathit{Signers},
        \mathit{PubKeys}, \mathit{Sigs})$ for the contributing
        set $S$.
  \item $\textsc{VerifyCert}(\mathit{cert}, \mu, \mathit{registry})
        \to \mathit{count}$: enforces registry binding (drops
        unknown signers and pubkey mismatches), dedupes
        repeated signers, calls
        $\textsc{BatchVerify}$ on the verifiable subset, and
        returns the count of valid signers. The quorum decision
        ``$\mathit{count} \ge K$?'' lives at the consumer.
\end{itemize}
\end{definition}

The deliberate choice that $\textsc{Sign}$ is the unmodified FIPS 205
$\textsc{SignDeterministic}$ --- not a Magnetar-specific envelope ---
is the load-bearing operational property: any deployment shipping a
Magnetar signer needs to add no new verification code on the
consuming side. Every SLH-DSA verifier in the wild
(\texttt{cloudflare/circl/sign/slhdsa} \cite{circl}, the FIPS 205
reference, openssl-pq, libsignal-pq) accepts Magnetar signatures
unmodified after the wire envelope is stripped.

\subsection{Threshold signature syntax (appendix forms)}
\label{sec:prelim:thresh-syntax}

The threshold forms documented in the appendices use the standard
threshold-signature syntax of Canetti \cite{canetti2001uc} and
Boneh--Shoup \cite{boneh-shoup-textbook} as specialised to SLH-DSA.

\begin{definition}[Threshold SLH-DSA scheme (THBS-SE)]
\label{def:thresh-syntax}
$\Pi_{\mathrm{Magnetar}}^{\mathrm{thr}}$ is a tuple
$(\textsc{Setup}, \textsc{SignShare}, \textsc{Combine},
\textsc{Verify})$:
\begin{itemize}[nosep,leftmargin=2em]
  \item $\textsc{Setup}$: produces the joint group public key $pk$
        and per-party secret shares. For THBS-SE
        (\S\ref{sec:thbsse:setup}) this is \texttt{NewThbsSeKey}
        (deterministic dealer reference; production routes
        through the sibling leaderless PVSS-DKG in
        \texttt{luxfi/threshold}).
  \item $\textsc{SignShare}$: per-party contribution. For THBS-SE
        (\S\ref{sec:thbsse:round1}--\ref{sec:thbsse:round2}) this
        is the two-round commit-and-reveal of the per-party mask
        and masked Shamir share.
  \item $\textsc{Combine}$: PUBLIC, deterministic combiner
        function (\S\ref{sec:thbsse:combine}). For THBS-SE this
        Lagrange-reconstructs the scheme seed over
        $\mathrm{GF}(257)$ in the public combiner's transient
        memory, dispatches to FIPS 205
        $\textsc{SignDeterministic}$, and zeroizes.
  \item $\textsc{Verify}$: \emph{the unmodified FIPS 205
        verifier} of \cite{fips205}~\S9.3.
\end{itemize}
\end{definition}

THBS-SE preserves the FIPS 205 output shape: $\textsc{Combine}$
output is byte-identical to single-party
$\textsc{SignDeterministic}$ on the implicit
$(\mathit{seed}, \mu, \mathit{ctx})$ tuple
(Theorem~\ref{thm:thbsse-byte-identity}). A relying party sees no
difference between a standalone $\sigma_i$ and a THBS-SE $\sigma$
once both are unwrapped from the canonical MAGS envelope.

\subsection{Shamir secret sharing over $\mathrm{GF}(257)$ (THBS-SE)}
\label{sec:prelim:shamir}

We instantiate Shamir secret sharing \cite{shamir1979} byte-wise
over $\mathrm{GF}(p)$ with $p = 257$ for THBS-SE
(\S\ref{sec:thbsse:setup}). The choice of $p = 257$ is
dictated by two constraints:
\begin{enumerate}[leftmargin=2em,nosep]
  \item $p > 255$, so every byte value $0,\ldots,255$ is a distinct
        field element.
  \item $p < 2^9$, so each share value fits in a $9$-bit lane, packed
        as one $\mathtt{uint16}$ per byte position on the wire.
\end{enumerate}
The trade-off: $p = 257$ admits at most $p - 1 = 256$ distinct non-zero
evaluation points, capping the committee size at $256$ (constant
\texttt{MaxCommittee257} in \texttt{params.go}). For the Lux
validator committees this is comfortably above the production
thresholds (Quasar operates at $K \le 21$ \cite{lp020}).

\paragraph{Sharing.} To share a $\textsc{seed\_size}$-byte secret
$\mathbf{s} \in [0,256]^{\textsc{seed\_size}}$ across $n$ parties at
threshold $t$:
\begin{enumerate}[leftmargin=2em,nosep]
  \item For each byte position $b \in [0, \textsc{seed\_size})$, sample
        $t-1$ random coefficients
        $a_{b,1}, \ldots, a_{b,t-1} \in \mathrm{GF}(257)$
        and define
        $f_b(x) = \mathbf{s}[b] + \sum_{j=1}^{t-1} a_{b,j} x^j
          \pmod{257}$.
  \item For each recipient $P_i$ at evaluation point $x_i = i$ (one-
        indexed), compute $\mathit{share}_i[b] = f_b(x_i) \bmod 257$
        for all $b$.
  \item Wire-form: pack each $\mathit{share}_i$ as a sequence of
        $\textsc{seed\_size}$ big-endian $\mathtt{uint16}$ values
        ($2 \cdot \textsc{seed\_size}$ bytes total).
\end{enumerate}

\paragraph{Reconstruction.} Given any $t$ shares
$\{(x_i, \mathit{share}_i)\}_{i \in Q}$ with $|Q| \ge t$, the
constant term of each $f_b$ is recovered by Lagrange interpolation at
$x = 0$:
\begin{equation}
  \mathbf{s}[b] \;=\; \sum_{i \in Q} \lambda_i^Q(0) \cdot \mathit{share}_i[b]
  \pmod{257},
  \quad
  \lambda_i^Q(0) = \prod_{j \in Q, j \neq i}
    \frac{-x_j}{x_i - x_j} \bmod 257.
  \label{eq:shamir-lagrange}
\end{equation}
The Lagrange coefficients $\lambda_i^Q(0)$ are computed once per quorum
using Fermat's little theorem for modular inversion
($a^{-1} \equiv a^{p-2} \pmod p$); see \texttt{shamir.go} lines 148--164.

\paragraph{Information-theoretic privacy.} For any $|Q| < t$, the joint
distribution of $\{\mathit{share}_i\}_{i \in Q}$ is uniformly distributed
over $[0,257)^{|Q| \cdot \textsc{seed\_size}}$ \emph{independent} of
$\mathbf{s}$. This is the standard Shamir privacy property
\cite{shamir1979,katzlindell}: every $t-1$-subset of shares reveals
zero information about the secret, as a matter of information theory
(not computational complexity). This is the load-bearing secrecy
guarantee of the appendix threshold forms against a coalition of
$t-1$ or fewer committee members.

\paragraph{The $\mathrm{GF}(257)$/byte-domain mismatch.} The Lagrange
reconstruction \eqref{eq:shamir-lagrange} produces a value in
$[0, 257)$; the SLH-DSA scheme seed is byte-valued in $[0, 256)$. The
single value $256$ has no byte representation. The appendix forms
handle this \emph{constructively}: the Shamir reconstruction is fed
into a cSHAKE256 mix
\begin{equation}
  S = \textsc{cSHAKE256}\bigl(
    \mathrm{byteSum}_\mathit{BE} \,\Vert\, \mathit{committee\_root},
    \mathrm{N}=\text{``Magnetar''},
    \mathrm{S}=\text{``MAGNETAR-SEED-SHARE-V1''},
    8 \cdot \textsc{seed\_size}\,\mathrm{bits}\bigr),
  \label{eq:seed-mix}
\end{equation}
which absorbs the $\mathrm{GF}(257)$-valued $\mathrm{byteSum}$ as a
$2 \cdot \textsc{seed\_size}$-byte big-endian buffer and emits a
$\textsc{seed\_size}$-byte $S$. The cSHAKE256 mix domain-separates
the seed from raw Shamir output and gives a constant-length seed
regardless of the value distribution of $\mathrm{byteSum}$.

\subsection{Security games}
\label{sec:prelim:games}

The per-validator standalone primitive's security game is the
single-party SLH-DSA UF-CMA game replicated $N$ times in parallel.
We state the formal definition.

\begin{definition}[Multi-validator EUF-CMA]
\label{def:multivalidator-eufcma}
$\mathsf{Game}^{\mathrm{multi\text{-}EUF\text{-}CMA}}_{
\Pi^{\mathrm{std}}_{\mathrm{Magnetar}}}(\mathcal{A}, \lambda, N)$:
\begin{enumerate}[nosep,leftmargin=2em]
  \item \textbf{Setup.} The challenger runs $\textsc{KeyGen}$
        independently $N$ times to obtain $(sk_i, pk_i)$ for
        $i = 1, \ldots, N$. The adversary $\mathcal{A}$ commits
        to a corrupt set $F \subset [N]$ with $|F| < K$ at the
        outset, where $K$ is the quorum threshold; the
        challenger gives $\mathcal{A}$
        $\{(pk_i)\}_{i=1}^N \cup \{sk_i : i \in F\}$.
  \item \textbf{Queries.} $\mathcal{A}$ adaptively requests
        signatures from honest validators on messages $\mu_1,
        \ldots, \mu_{Q_S}$. For each query
        $(i, \mu)$ with $i \notin F$, the challenger returns
        $\sigma_i = \textsc{Sign}(sk_i, \mu, \mathit{ctx})$.
        $\mathcal{A}$ may invoke the random oracle $\mathcal{O}_H$
        up to $Q_H$ times.
  \item \textbf{Forgery.} $\mathcal{A}$ outputs $(\mu^\star,
        \mathit{cert}^\star)$ and \emph{wins} iff
        $\textsc{VerifyCert}(\mathit{cert}^\star, \mu^\star,
        \mathit{registry}) \ge K$ and there exist $K - |F|$
        signers $i \notin F$ whose signatures in $\mathit{cert}^\star$
        are valid forgeries on $\mu^\star \notin \{\mu_j : (i, \mu_j)
        \in \mathit{queries}\}$.
\end{enumerate}
The advantage is
$\mathsf{Adv}^{\mathrm{multi\text{-}EUF\text{-}CMA}}_{
\Pi^{\mathrm{std}}_{\mathrm{Magnetar}}, \mathcal{A}}(\lambda, N)
= \Pr[\mathcal{A} \text{ wins}]$.
\end{definition}

The multi-validator forgery condition reduces to single-party SLH-DSA
UF-CMA via a standard hybrid argument: each honest validator's
keypair is independent, so any forgery on validator $i$'s signature
yields a single-party SLH-DSA UF-CMA forgery on $(pk_i, sk_i)$. The
reduction has a factor $N$ loss for the hybrid (the standard hybrid
argument over independent keypairs); the SLH-DSA UF-CMA bound at the
SHAKE-192s parameter set ($\le 2^{-192}$ classical, $\le 2^{-128}$
quantum) absorbs this factor comfortably for any $N \le 2^{60}$.

The THBS-SE security game is the slot-bound permissionless
threshold EUF-CMA game: the adversary corrupts up to $t-1$
parties, observes Round-1/Round-2 broadcasts of the honest
parties at chosen slot bindings $\mathit{bind}^*$ and messages
$\mu^*$, may invoke the public combiner on any subset of those
broadcasts, and wins by producing a signature on a fresh
$(\mathit{bind}^\star, \mu^\star)$ that verifies under the
committee group public key. The named selected-element-reveal
invariant
(Theorem~\ref{thm:thbsse-selected-element-reveal}) bounds the
adversary's per-round leak to the
Shamir information-theoretic share class plus public-transcript
bytes; we state the formal security argument in
\S\ref{sec:security:thbsse-reveal}.