papers/lp-020-quasar-consensus/sections/13-why-not-threshold-ml-dsa-or-threshold-fa.tex

\section{Threshold ML-DSA via Pulsar; Why Not Threshold FALCON}

\label{sec:why-not-threshold}
\label{app:no-threshold-mldsa}

\subsection{Threshold ML-DSA is achieved by Pulsar (BCC/CEF)}
\label{sec:threshold-mldsa-pulsar}

\textbf{This subsection supersedes the earlier ``why not threshold
ML-DSA'' position of Quasar~3.0.} That position --- that ML-DSA cannot
be thresholdized without either reconstructing the key or relaxing the
FIPS rejection bound, and that Quasar therefore uses individual ML-DSA
signatures rolled up by Groth16 in place of a threshold --- is now
obsolete. Threshold ML-DSA, \emph{byte-equal} to FIPS~204, \emph{is}
achieved by \textbf{Pulsar} (LP-4450~\cite{lp4450}, formal companion
LP-073~\cite{lp073}). We restate the two classical obstacles and show
how Pulsar's \emph{boundary-cleared nonce transcript with carry
elimination} (BCC/CEF) eliminates each without leaking key material.

ML-DSA (FIPS~204, formerly CRYSTALS-Dilithium) uses Fiat--Shamir with
Aborts: the signer samples a masking vector $\mathbf{y}$, commits
$\mathbf{w} = \mathbf{A}\mathbf{y}$, derives challenge $c$, forms
response $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$, and runs a
\emph{secret-dependent} rejection-and-hint sequence over
$\mathbf{w}_0 - c\mathbf{s}_2$ and $c\mathbf{t}_0$.

\begin{enumerate}[nosep]
  \item \textbf{Rejection sampling.}  The abort decision depends on the
    \emph{combined} response $\mathbf{z} = \sum_i \lambda_i \mathbf{z}_i$
    and on $\mathbf{w}_0 - c\mathbf{s}_2$, neither of which a single
    party can evaluate without the others' shares.  \emph{Pulsar's
    resolution:} move the decision \emph{offline} and make it
    \emph{message-independent}.  A nonce aggregate $\mathbf{w}$ is
    \emph{boundary-clear} iff every coefficient of $\mathbf{w}$ has
    centred low bits $|\mathbf{w}_0| < \gamma_2 - 2\beta -
    \text{slack}$.  A boundary-clear nonce guarantees, for \emph{every}
    admissible challenge $c$, that
    $\mathsf{HighBits}(\mathbf{w} - c\mathbf{s}_2) =
    \mathsf{HighBits}(\mathbf{w}) = \mathbf{w}_1$ and that the FIPS
    $\mathbf{r}_0$-norm check holds --- \emph{without ever forming}
    $c\mathbf{s}_2$, $c\mathbf{t}_0$, $\mathbf{r}_0$, or $\mathbf{w}_0$.
    The combined rejection decision becomes a per-nonce predicate
    evaluated once, offline, over public-after-clearance high bits.

  \item \textbf{Hint computation.}  FIPS verification reconstructs the
    high bits of $\mathbf{w} - c\mathbf{s}_2$ from a hint $\mathbf{h}$
    without knowing $\mathbf{s}_2$; the signer normally computes
    $\mathbf{h} = \mathsf{MakeHint}(\mathbf{w}_0 - c\mathbf{s}_2 +
    c\mathbf{t}_0, \mathbf{w}_1)$, which a threshold must either feed
    from a trusted combiner or compute via the secret-bearing
    intermediates.  \emph{Pulsar's resolution:} recover the hint from
    \emph{public data only}.  The combiner forms
    $\mathbf{w}' = \mathbf{A}\mathbf{z} - c\mathbf{t}_1 \cdot 2^d$
    (exactly the quantity the FIPS verifier forms) and derives
    $\mathbf{h}$ from $\mathbf{w}'$ and the public $\mathbf{w}_1$ via the
    standard FIPS $\mathsf{UseHint}$ decision ($\mathsf{FindHint}$):
    $h_j = 0$ if $\mathsf{HighBits}(\mathbf{w}'_j) = \mathbf{w}_{1,j}$;
    $h_j = 1$ iff $\mathsf{UseHint}(1, \mathbf{w}'_j) = \mathbf{w}_{1,j}$;
    otherwise the nonce admits no valid FIPS hint and is consumed and
    retried.  No party reconstructs $c\mathbf{s}_2$ or $c\mathbf{t}_0$.
\end{enumerate}

\paragraph{Verification-equivalence.}  FIPS~204 $\mathsf{Verify}$
computes $\mathbf{w}'_{\text{approx}} = \mathbf{A}\mathbf{z} -
c\mathbf{t}_1 \cdot 2^d$ and accepts iff $\tilde c =
H(\mu, \mathsf{UseHint}(\mathbf{h}, \mathbf{w}'_{\text{approx}}))$.
Pulsar builds $\mathbf{h}$ via $\mathsf{FindHint}$ so that
$\mathsf{UseHint}(\mathbf{h}, \mathbf{w}') = \mathbf{w}_1$ by
construction; boundary clearance bounds the $c\mathbf{t}_0 -
c\mathbf{s}_2$ residual to $\pm 1$ high-bit carries that the hint
corrects.  The threshold signature therefore verifies byte-for-byte
under unmodified FIPS~204 --- the same algebra as single-party
$\mathsf{Sign}$, with the hint recovered from public data rather than
from the secret residual.

\paragraph{Mode restriction.}  BCC/CEF is sound only where
$\|c\mathbf{t}_0\|_\infty \leq \tau \cdot 2^{d-1} < \gamma_2$, which
makes the FIPS $c\mathbf{t}_0$ check vacuous and bounds the carry to a
single high-bit step.  This holds for \textbf{ML-DSA-65}
($49 \cdot 4096 < \gamma_2 = 261888$) and \textbf{ML-DSA-87}
($60 \cdot 4096 < \gamma_2$), but \emph{not} for ML-DSA-44
($39 \cdot 4096 > \gamma_2 = 95232$).  Pulsar supports ML-DSA-65 and
ML-DSA-87 only.

\paragraph{Consensus-native certification.}  Boundary clearance is
certified by a NonceTranscript quorum run by the validator set itself
(consensus-native MPC, not a separate signing service), which emits a
$\mathsf{NonceCert}$ carrying \emph{only} $\mathbf{w}_1 =
\mathsf{HighBits}(\mathbf{w})$ and a clearance quorum certificate ---
never the full commitment $\mathbf{w}$.  Online signing is then the
Ringtail-style two rounds (bind canonical nonce; open linear
$\mathbf{z}$-partial) plus a public-hint finalize, orchestrated inside
\texttt{luxfi/consensus} as a Quasar cert profile, with the BCC/CEF
crypto primitives in \texttt{luxfi/pulsar}.

\paragraph{The V13 finding (what NOT to do).}  An earlier Pulsar
construction (\texttt{v0.3 AlgebraicAggregate}) broadcast the
secret-bearing intermediates $c\mathbf{s}_2$ and $c\mathbf{t}_0$ to a
combiner so it could run the FIPS sign-side checks and $\mathsf{MakeHint}$
verbatim.  Broadcasting $c\mathbf{s}_2$ / $c\mathbf{t}_0$ \emph{leaks
long-term key material} --- this is the \textbf{V13 finding}
(\texttt{PULSAR-V13-HINT-LEAK}; a sibling \texttt{PULSAR-V13-W-LEAK}
exposes the full $\mathbf{w}$ in a $\mathsf{NonceCert}$).  That path is
removed/gated fail-closed; BCC/CEF is the no-leak replacement, and
$\mathsf{NonceCert}$ carries only $\mathbf{w}_1$ plus a clearance proof.
The detailed analysis is LP-4450~\cite{lp4450} (V13 section) and the
Pulsar paper LP-073~\cite{lp073}.

\paragraph{Honest status.}  Pulsar is \textbf{review-ready, not
production-certified.}  Byte-equality of the no-leak path is
demonstrated under both the \texttt{cloudflare/circl} and
\texttt{pq-crystals} reference verifiers (ML-DSA-65 and ML-DSA-87), and
the boundary-clearance $\Rightarrow$ $\mathsf{FindHint}\leftrightarrow
\mathsf{UseHint}$ correspondence is machine-checked in Lean.  Two
genuinely novel components --- tight small-norm lattice range proofs for
the nonce/DKG witnesses, and evaluating $\mathsf{HighBits}$/boundary
clearance inside the MPC over secret-shared $\mathbf{w}$ --- are
\emph{fail-closed pending external review}.  Until reviewed verifiers
are installed, the production signer refuses the BCC/CEF path and the
Quasar composer uses the Corona leg in Pulsar's place.  Pulsar's stock
FIPS~204 \emph{verifier} is always available; only the threshold
\emph{signer} is gated.

\paragraph{Relationship to the Z-Chain ML-DSA rollup.}  Quasar's
individual-ML-DSA-plus-Groth16 lane (\S\ref{sec:lane3}) is retained as a
\emph{complementary accountability} mechanism --- it proves \emph{which}
validators signed (per-validator attribution and slashing evidence) and
compresses $N$ signatures to a constant-size on-chain footprint.  Pulsar
provides the \emph{threshold} property: a single FIPS-204 signature
under one group key.  The two are orthogonal lanes, not competitors:
the rollup gives accountability and footprint, Pulsar gives a genuine
threshold seal.  Where the earlier text claimed a threshold ``cannot''
be built, the correct statement is that a byte-equal threshold
\emph{can} be built (Pulsar), and Quasar composes both.

\subsection{Threshold FALCON}

FALCON~\cite{falcon-spec} uses NTRU lattices and a hash-then-sign
paradigm with Gaussian sampling via a Gram-Schmidt-like procedure
(the ``FALCON tree'').  Unlike ML-DSA --- whose Fiat--Shamir-with-Aborts
structure Pulsar thresholdizes via BCC/CEF --- FALCON's trapdoor
Gaussian sampling has no analogous public-data reformulation.
Thresholdizing FALCON requires distributed Gaussian sampling, which
remains an open problem:

\begin{enumerate}[nosep]
  \item The FALCON signing key is a short basis for an NTRU lattice.
    Shamir-sharing this basis and reconstructing Gaussian samples from
    shares requires parties to jointly sample from a lattice Gaussian
    without leaking the basis---strictly harder than threshold
    Fiat--Shamir with Aborts.

  \item Known approaches (Ducas and Prest~\cite{ducas2016}) for
    distributed NTRU sampling require $O(n^2)$ communication rounds,
    negating FALCON's performance advantage over ML-DSA.

  \item FALCON was not selected as NIST's primary standard (ML-DSA
    was); it is a secondary standard under FIPS~206 (draft).  Building
    threshold cryptography on a secondary standard adds adoption risk.
\end{enumerate}

\textbf{Quasar's position.}  Threshold ML-DSA \emph{is} used, via
Pulsar's BCC/CEF construction (byte-equal to FIPS~204, ML-DSA-65 and
ML-DSA-87), subject to the honest review-ready status above; until that
review lands, the Corona Module-LWE leg fills the threshold PQ niche and
individual ML-DSA-plus-Groth16 provides per-validator accountability.
Threshold FALCON is not used: distributed trapdoor Gaussian sampling
remains an open problem with no byte-equal threshold construction.