pulsar/spec/nist-mptc-category.tex

% Pulsar NIST MPTC category targeting -- included by pulsar.tex.
% Mirrors docs/nist-mptc-category.md (now deleted; this file is the
% canonical LaTeX form).

\paragraph{Reference.}
NIST IR 8214C, \emph{First Call for Multi-Party Threshold Schemes}
(January 2026). Package deadline expected 2026-Nov-16. Preview
deadline 2026-Jul-20.

\subsection{Pulsar target: Class N1 + N4}

NIST MPTC subdivides threshold schemes into:

\begin{itemize}[leftmargin=*, itemsep=0pt]
\item \textbf{Class S} (Special) --- threshold-friendly primitives
that \emph{are not} output-interchangeable with a NIST-specified
primitive. Submission evaluated for ``novel threshold-friendly
design.''
\item \textbf{Class N} (Normal-mode) --- threshold implementations
\emph{of} a NIST-specified primitive whose outputs are
interchangeable with the corresponding non-threshold primitive's
outputs.
  \begin{itemize}[leftmargin=*, itemsep=0pt]
  \item \textbf{N1}: signing
  \item \textbf{N2}: encryption / decryption
  \item \textbf{N3}: KEM
  \item \textbf{N4}: ML keygen / DKG (Module-Lattice key generation,
  distributed)
  \end{itemize}
\end{itemize}

Pulsar aims for \textbf{N1 (threshold ML-DSA signing) + N4
(distributed ML-DSA keygen)}. The headline interchangeability claim:

\begin{quote}
A signature $\sigma$ produced by a Pulsar threshold ceremony on
message $\mu$ against group public key $\mathit{pk}$ verifies under
unmodified FIPS~204 \texttt{ML-DSA.Verify}$(\mathit{pk}, \mu,
\sigma)$ returning \texttt{accept}.
\end{quote}

If we can prove and demonstrate this, Pulsar is a Class N
candidate. If the output is not bit-for-bit FIPS~204 (e.g.\ encoding
differs in any field), Pulsar falls back to Class S --- still
valid, but a weaker NIST positioning.

\subsection{Output interchangeability --- what has to hold}

ML-DSA-65 signatures (FIPS~204 \S5.4, Algorithm~26 \texttt{sigEncode})
are encoded as a fixed-length 3309-byte string $\sigma = (\tilde c,
\mathbf{z}, \mathbf{h})$ whose three components decompose exactly as:

\begin{verbatim}
sigma = (c_tilde || z || h)                                  3309 bytes
  c_tilde in {0,1}^{2 lambda}                                  48 bytes
        // FIPS 204 commitment-hash length; 2 lambda bits with
        // lambda=192 = 384 bits.
        // (2 lambda here is the FIPS 204 commitment-hash parameter,
        // not the security level -- the two happen to numerically
        // agree for ML-DSA-65 because the standard ties one to the
        // other at this parameter set.)
  z in R^ell_q                                               3200 bytes
        // ell = 5 polynomials, each 256 coefficients, packed at
        // log2(2 gamma_1) = 20 bits per coefficient.
        // 5 * 256 * 20 / 8 = 3200 bytes.
  h in {0,1}^{omega + k}                                       61 bytes
        // omega = 55 (hint bound), k = 6 (commitment-vector
        // dimension). FIPS 204 Algorithm 22 hintBitPack + Algorithm
        // 28 sigEncode pack omega + k = 61 bits as 61 bytes (one
        // byte per bit position, terminator-first encoding per the
        // standard).
  total: 48 + 3200 + 61 = 3309 bytes                  (FIPS 204 Table 2)
\end{verbatim}

For Pulsar to claim Class N1, the threshold-aggregated signature
MUST deserialize as exactly this triple, with the same byte layout,
the same canonicalization rules, and the same rejection criteria.
The threshold protocol is allowed to perform multiple rounds
internally, but its emitted artifact MUST be a single FIPS~204
$\sigma$.

This is non-trivial: ML-DSA's rejection sampling means a single-shot
threshold output can fail rejection and require restart. Pulsar's
2-round structure handles this for R-LWE; Pulsar needs to
reproduce the rejection-restart logic for M-LWE without leaking
secret information across the restart.

\subsection{Required package deliverables}

Per NIST IR 8214C \S5:

\begin{center}
\begin{tabular}{lll}
\toprule
element & format & location \\
\midrule
Technical Specification & PDF (LaTeX) & \texttt{spec/pulsar.pdf} \\
Reference Implementation & open-source code & \texttt{ref/go/} \\
Report on Experimental Evaluation & PDF + reproducible scripts &
  \texttt{bench/results/REPORT.md} + \texttt{bench/run\_all.sh} \\
Notes on Patent Claims & PDF & \texttt{spec/patent-notes.tex} \\
Concrete parameter set & section in spec & \texttt{spec/parameters.tex} \\
Security analysis (proofs) & section in spec & \texttt{spec/security-games.tex} \\
Public repository & GitHub or equiv & \url{https://github.com/luxfi/pulsar} \\
Build/test/benchmark scripts & shell & \texttt{scripts/*.sh} \\
Open-source license & text & \texttt{LICENSE} (Apache-2.0) \\
I/O test vectors & JSON / RSP & \texttt{vectors/kat-v1.\{json,rsp\}} \\
\bottomrule
\end{tabular}
\end{center}

Optional but strongly recommended:

\begin{itemize}[leftmargin=*, itemsep=0pt]
\item Executive summary (1-2 pages) at front of spec.
\item Threat-model document (\texttt{spec/threat-model.tex}).
\item System-model document (\texttt{spec/system-model.tex}).
\item Closure-record appendix (\texttt{BLOCKERS.md}) so reviewers
see every closed finding with commit + tag.
\end{itemize}

\subsection{Required security strengths}

NIST MPTC \S4.5 gives the required and suggested security-strength
targets:

\begin{center}
\begin{tabular}{llll}
\toprule
target & classical & post-quantum (NIST PQ category) & statistical \\
\midrule
\textbf{required} ($\ge 1$ parameterization) & $\ge 128$ bits &
  $\ge$ Category 1 & $\ge 40$ bits \\
\textbf{suggested} (additional, optional) & $\ge 192$ bits &
  $\ge$ Category 3 & $\ge 64$ bits \\
\bottomrule
\end{tabular}
\end{center}

Pulsar will ship parameter sets matching ML-DSA-65 (Category 3)
for the suggested target, and potentially ML-DSA-44 (Category 2) and
ML-DSA-87 (Category 5) for full coverage.

\subsection{Class N vs Class S decision}

Pulsar is N if and only if:

\begin{enumerate}[leftmargin=*, itemsep=0pt]
\item A working reference implementation produces signatures
byte-equal to FIPS~204 ML-DSA on the same $(\mathit{pk}, \mu)$ for
some valid threshold ceremony.
\item The threshold key generation produces a $\mathit{pk}$ that's a
valid FIPS~204 ML-DSA public key (no extra public material
distinguishable from a single-party $\mathit{pk}$).
\item The verification relation in the spec is the FIPS~204 verifier
verbatim, with no Pulsar-specific changes.
\end{enumerate}

If any of (1)-(3) fails, we ship as Class S with a clear ``future
work: output interchangeability'' note. The class decision is
finalized at the point we freeze the spec encoding.

\subsection{Pulsar (R-LWE) for comparison}

Pulsar (R-LWE) targets \textbf{Class S1 + S4}: special
threshold-friendly two-round signature, not output-interchangeable
with any NIST-approved primitive. The S1/S4 framing is the right
framing for Corona-derivatives unless and until NIST blesses
Corona-shaped outputs as a primitive.

\subsection{Status}

\begin{itemize}[leftmargin=*, itemsep=0pt]
\item[$\square$] Class declared (N vs S, awaiting spec freeze)
\item[$\square$] Preview writeup drafted
\item[$\square$] Preview submitted (target 2026-Jul-20)
\item[$\square$] Spec freeze
\item[$\square$] Reference impl complete
\item[$\square$] KATs cross-validated against FIPS~204 reference
\item[$\square$] Experimental-evaluation report
\item[$\square$] Patent-claims notes finalized
\item[$\square$] Package submitted (target 2026-Nov-16)
\end{itemize}