papers/lux-lattice-cryptography-primer/sections/06-how-ml-dsa-dilithium-works.tex

\section{How ML-DSA Works}


ML-DSA is a digital signature scheme based on the ``Fiat-Shamir with aborts'' paradigm
over Module-LWE.

\subsection{Key Generation}

\begin{enumerate}[nosep]
  \item Sample $\mathbf{A} \in R_q^{k \times \ell}$ from a seed.
  \item Sample secret vectors $\mathbf{s}_1 \in R_q^\ell$, $\mathbf{s}_2 \in R_q^k$
    with small coefficients.
  \item Compute $\mathbf{t} = \mathbf{A}\mathbf{s}_1 + \mathbf{s}_2$.
  \item Public key: $(\text{seed}, \mathbf{t})$. Secret key: $(\mathbf{s}_1, \mathbf{s}_2)$.
\end{enumerate}

\subsection{Signing (Fiat-Shamir with Aborts)}

\begin{enumerate}[nosep]
  \item Sample random masking vector $\mathbf{y}$ with bounded coefficients.
  \item Compute $\mathbf{w} = \mathbf{A}\mathbf{y}$ and extract high bits: $\mathbf{w}_1$.
  \item Compute challenge: $c = H(\text{msg} \| \mathbf{w}_1)$.
  \item Compute response: $\mathbf{z} = \mathbf{y} + c \cdot \mathbf{s}_1$.
  \item \textbf{Rejection sampling}: If $\|\mathbf{z}\|_\infty$ is too large, \emph{restart}.
    This prevents the signature from leaking information about $\mathbf{s}_1$.
  \item Output signature: $(c, \mathbf{z})$.
\end{enumerate}

The rejection sampling step is critical: without it, statistical analysis of many
signatures reveals $\mathbf{s}_1$. With it, the distribution of $\mathbf{z}$ is
independent of $\mathbf{s}_1$ (up to the bound check).

\begin{lstlisting}[language=Go,caption={ML-DSA signing with rejection sampling}]
func Sign(sk *SecretKey, msg []byte) Signature {
    for {
        // Sample masking vector
        y := sampleMask(gamma1)

        // w = A * y
        w := mulMatVec(sk.A, nttVector(y))
        w1 := highBits(w, alpha)

        // Challenge
        c := challengeHash(msg, w1)
        cPoly := sampleChallenge(c)

        // Response
        z := addVectors(y, scalarMulVector(cPoly, sk.S1))

        // Rejection: check norm bound
        if infNorm(z) >= gamma1-beta {
            continue // Restart
        }

        // Check hint
        r0 := lowBits(
            subVectors(w, scalarMulVector(cPoly, sk.S2)),
            alpha,
        )
        if infNorm(r0) >= gamma2-beta {
            continue // Restart
        }

        return Signature{C: c, Z: z}
    }
}
\end{lstlisting}

\subsection{Verification}

\begin{enumerate}[nosep]
  \item Compute $\mathbf{w}' = \mathbf{A}\mathbf{z} - c \cdot \mathbf{t}$.
  \item Extract high bits: $\mathbf{w}'_1$.
  \item Check: $c = H(\text{msg} \| \mathbf{w}'_1)$ and $\|\mathbf{z}\|_\infty < \gamma_1 - \beta$.
\end{enumerate}

Verification is straightforward and never requires rejection sampling.

%% ============================================================