papers/lux-lattice-cryptography-primer/sections/05-how-ml-kem-kyber-works.tex

\section{How ML-KEM Works}


ML-KEM is a key encapsulation mechanism (KEM): it produces a shared secret between two
parties. It builds on M-LWE.

\subsection{Key Generation}

\begin{enumerate}[nosep]
  \item Sample random matrix $\mathbf{A} \in R_q^{k \times k}$ (from a seed via SHAKE-128).
  \item Sample secret $\mathbf{s} \in R_q^k$ and error $\mathbf{e} \in R_q^k$ with small
    coefficients (centered binomial distribution).
  \item Compute $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$.
  \item Public key: $(\text{seed for } \mathbf{A}, \mathbf{t})$. Secret key: $\mathbf{s}$.
\end{enumerate}

\begin{lstlisting}[language=Go,caption={ML-KEM key generation (simplified)}]
func KeyGen() (PublicKey, SecretKey) {
    seed := randBytes(32)
    A := expandA(seed)  // k x k matrix of ring elements

    s := sampleCBD(eta1) // Secret: small coefficients
    e := sampleCBD(eta1) // Error: small coefficients

    // t = A*s + e (all operations in NTT domain)
    sNTT := nttVector(s)
    t := addVectors(mulMatVec(A, sNTT), nttVector(e))

    pk := PublicKey{Seed: seed, T: compress(t)}
    sk := SecretKey{S: sNTT}
    return pk, sk
}
\end{lstlisting}

\subsection{Encapsulation}

\begin{enumerate}[nosep]
  \item Generate random message $m \gets \{0,1\}^{256}$.
  \item Derive randomness: $(r, K) = G(m \| H(\text{pk}))$.
  \item Encrypt $m$ under the public key using randomness $r$:
    $\mathbf{u} = \mathbf{A}^T \mathbf{r} + \mathbf{e}_1$ and
    $v = \mathbf{t}^T \mathbf{r} + e_2 + \lceil q/2 \rceil \cdot m$.
  \item Ciphertext: $(\mathbf{u}, v)$. Shared secret: $K$.
\end{enumerate}

\subsection{Decapsulation}

\begin{enumerate}[nosep]
  \item Decrypt: $m' = \text{Decompress}(v - \mathbf{s}^T \mathbf{u})$.
  \item Re-encrypt: $(\mathbf{u}', v') = \text{Enc}(\text{pk}, m'; r')$.
  \item If $(\mathbf{u}', v') = (\mathbf{u}, v)$, output $K = \text{KDF}(m' \| H(\text{ct}))$.
  \item Otherwise, output a random key (implicit rejection).
\end{enumerate}

The re-encryption step (Fujisaki-Okamoto transform) converts CPA security to CCA
security: it prevents the adversary from learning anything by submitting crafted
ciphertexts.

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