How Post-Quantum Cryptography Actually Works: Lattice Mathematics, ML-KEM, and the Mechanics of Kyber

Modern internet security rests on public-key cryptography. When an application initiates a Secure Sockets Layer / Transport Layer Security (TLS 1.3) connection, executes an SSH session, or validates an electronic signature, it relies on mathematical operations whose security depends on the computational difficulty of specific number-theoretic problems: integer factorization (RSA) and discrete logarithms over finite fields or elliptic curve groups (ECDHE, ECDSA, Ed25519).

In 1994, Peter Shor published a quantum algorithm demonstrating that a fault-tolerant quantum computer running Shor's algorithm can factor integers and calculate discrete logarithms in polynomial time. Using Shor's algorithm, a quantum computer with a few thousand stable physical qubits running quantum error correction could break a 2048-bit RSA key or a 256-bit elliptic curve key in seconds.

To protect communications against hostile entities recording encrypted network traffic today to decrypt it once quantum hardware becomes available (a strategy known as store now, decrypt later), the global cryptographic community standardized new mathematical primitives. In 2024, the National Institute of Standards and Technology (NIST) published FIPS 203, standardizing the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM, originally known as CRYSTALS-Kyber).

Rather than relying on prime factorization or point multiplication on algebraic curves, post-quantum lattice cryptography relies on the hardness of high-dimensional geometric problems over discrete vector spaces.

This article examines the mathematical mechanics, polynomial ring structures, error distribution sampling, and transform algorithms that power ML-KEM and lattice-based post-quantum cryptography. We trace public key generation, ciphertext encapsulation, decapsulation error bounds, Number Theoretic Transform (NTT) acceleration, and the Fujisaki-Okamoto transform for chosen-ciphertext security.

+-----------------------------------------------------------------------------------+
|                     SHOR'S ALGORITHM VS LATTICE CRYPTOGRAPHY                      |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  1. CLASSICAL PUBLIC-KEY CRYPTOGRAPHY (Vulnerable to Quantum Period-Finding)     |
|     RSA / ECC Problem:  Find hidden period r of f(x) = a^x mod N                |
|     Quantum Attack:     Quantum Fourier Transform (QFT) finds period r in O(n^3)  |
|                         Polynomial time reduction breaks RSA/ECDH key exchange.  |
|                                                                                   |
|  2. LATTICE-BASED CRYPTOGRAPHY (Quantum Resistant)                                |
|     Module-LWE Problem: Find secret vector s given A*s + e mod q                 |
|     Geometric View:     Find the closest lattice point in a 256-dimensional space  |
|                         when random error vector e shifts the coordinate.          |
|     Quantum Hardness:   No known quantum algorithm accelerates solving Learning    |
|                         With Errors faster than sub-exponential time bounds.      |
|                                                                                   |
+-----------------------------------------------------------------------------------+

The Quantum Threat Model and Shor's Algorithm

Understanding why post-quantum algorithms are engineered around lattice structures requires analyzing why classical public-key primitives fail under quantum computation.

The Algebraic Structure of RSA and Elliptic Curve Cryptography

Classical public-key cryptosystems rely on trapdoor one-way functions. For example:

• RSA: Given two large prime numbers $p$ and $q$, computing $N = p \cdot q$ is trivial ($O(n^2)$ integer multiplication). Given only $N$, finding $p$ and $q$ via classical algorithms (such as the General Number Field Sieve) requires sub-exponential time $O(\exp((\sqrt[3]{64/9} + o(1)) (\ln N)^{1/3} (\ln \ln N)^{2/3}))$.
• Elliptic Curve Cryptography (ECC): Given a generator point $G$ on an elliptic curve $E(\mathbb{F}_p)$ and a scalar private key $d$, computing the public key point $Q = d \cdot G$ via scalar multiplication requires $O(\log d)$ point additions using double-and-add algorithms. Reversing this operation to compute $d = \log_G Q$ requires $O(\sqrt{N})$ group steps using Pollard's rho algorithm.

Both problems can be recast as instances of the Hidden Subgroup Problem (HSP) for finite abelian groups.

How Shor's Algorithm Solves the Hidden Subgroup Problem

Shor's algorithm reduces factoring and discrete logarithms to order-finding: finding the smallest positive integer $r$ such that $a^r \equiv 1 \pmod N$.

A classical computer finds $r$ by evaluating modular exponentiations sequentially, requiring exponential time. A quantum computer executes order-finding in polynomial time using three quantum physical mechanisms:

1. Quantum Superposition: The quantum computer initializes an input register of $2n$ qubits into an equal superposition of all possible states from $0$ to $2^{2n}-1$ using Hadamard gates.
2. Modular Exponentiation Circuit: The quantum register evaluates the function $f(x) = a^x \pmod N$ simultaneously across all states in superposition, entangling the input register with the output register.
3. Quantum Fourier Transform (QFT): Measuring the output register collapses it to a random value $f(x_0)$. The input register remains in a superposition of states $x_0, x_0+r, x_0+2r, \dots$ spaced exactly by the hidden period $r$. The Quantum Fourier Transform applies destructive interference to non-periodic computational paths and constructive interference to periodic paths, allowing a single measurement to yield the period $r$ with high probability.

Because Shor's algorithm solves the Hidden Subgroup Problem over abelian groups in $O(n^3)$ operations, increasing RSA key sizes from 2048 to 4096 bits only doubles classical computation while failing to stop quantum decryption.

High-Dimensional Lattice Geometry and Learning With Errors

Post-quantum cryptography shifts away from group theory and order-finding toward high-dimensional geometry.

What Is a Lattice?

An $n$-dimensional lattice $\mathcal{L}$ is a discrete subgroup of $n$-dimensional Euclidean space $\mathbb{R}^n$, formed by all linear combinations of $n$ linearly independent basis vectors $\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_n$ with integer coefficients:

$$\mathcal{L} = \left{ \sum_{i=1}^n x_i \mathbf{b}_i ;:; x_i \in \mathbb{Z} \right}$$

The matrix $\mathbf{B} = [\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_n] \in \mathbb{R}^{n \times n}$ is the basis matrix of the lattice.

+-----------------------------------------------------------------------------------+
|                        TWO-DIMENSIONAL DISCRETE LATTICE                           |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|   y ^                                                                             |
|     |     .       .       .       .       .   (Lattice point v = x1*b1 + x2*b2)  |
|     |                                                                             |
|     |     .       .       .       * (Target point t = v + e)                      |
|     |                            /                                                |
|     |     .       .       v .   / e (Small error vector)                          |
|     |                     o----'                                                  |
|     |                    / \                                                      |
|     |     .       .   b2/   \ b1  .       .                                       |
|     |                  /     \                                                    |
|     +-----------------o------->--------------------->                             |
|     0                 (Origin)                      x                             |
|                                                                                   |
|  CLOSEST VECTOR PROBLEM (CVP): Given target point t, find nearest lattice point v |
|  HARDNESS: Extremely difficult in 256 or 512 dimensions without a good basis!     |
|                                                                                   |
+-----------------------------------------------------------------------------------+

Hard Lattice Problems and Lattice Reduction Algorithms

Security guarantees in lattice cryptography derive from two fundamental computational problems that remain hard even for quantum computers:

1. Shortest Vector Problem (SVP): Given a basis matrix $\mathbf{B}$ for an $n$-dimensional lattice $\mathcal{L}$, find the shortest non-zero vector $\mathbf{v} \in \mathcal{L}$ that minimizes the Euclidean norm $|\mathbf{v}|_2$.
2. Closest Vector Problem (CVP): Given a basis matrix $\mathbf{B}$ and an arbitrary target point $\mathbf{t} \in \mathbb{R}^n$ not on the lattice, find the lattice vector $\mathbf{v} \in \mathcal{L}$ that minimizes the distance $|\mathbf{v} - \mathbf{t}|_2$.

When the dimension $n$ exceeds 256 or 512, finding exact or approximate solutions to SVP and CVP requires exponential time $2^{\Omega(n)}$.

To measure the security of lattice parameters, cryptographers evaluate the performance of lattice reduction algorithms:

• LLL (Lenstra-Lenstra-Lovász): A polynomial-time algorithm that computes a moderately reduced basis. LLL finds a lattice vector within a factor of $2^{O(n)}$ of the true shortest vector. While efficient, the approximation factor grows exponentially with dimension $n$, making LLL ineffective for attacking 256-dimensional cryptosystems.
• BKZ (Block-Korkine-Zolotarev): A block-wise reduction algorithm that generalizes LLL by calling an exact SVP solver on sub-lattices of block size $\beta$. As the block size $\beta$ increases, BKZ achieves tighter approximations of the shortest vector, but running time grows exponentially with $\beta$ as $2^{O(\beta)}$. Modern security estimates require $\beta \ge 400$ to attack ML-KEM-768, which demands over $2^{192}$ operations.

Learning With Errors (LWE)

In 2005, Oded Regev introduced the Learning With Errors (LWE) problem, proving a structural reduction from worst-case lattice problems to average-case algebraic equations.

Consider a system of linear equations over a finite prime field $\mathbb{Z}_q$:

$$\mathbf{A} \cdot \mathbf{s} = \mathbf{b} \pmod q$$

Where $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ is a known random matrix, $\mathbf{s} \in \mathbb{Z}_q^n$ is a secret vector, and $\mathbf{b} \in \mathbb{Z}_q^m$ is the resulting vector. Given $\mathbf{A}$ and $\mathbf{b}$, an attacker can recover the secret $\mathbf{s}$ in milliseconds using standard Gaussian elimination ($O(n^3)$ matrix inversion).

The LWE problem introduces a small random error vector $\mathbf{e} \in \mathbb{Z}_q^m$, sampled from a narrow noise distribution:

$$\mathbf{b} = \mathbf{A} \cdot \mathbf{s} + \mathbf{e} \pmod q$$

+-----------------------------------------------------------------------------------+
|                        LEARNING WITH ERRORS (LWE) FORMULATION                     |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  PUBLIC MATRIX A         SECRET s       NOISE e        PUBLIC VECTOR b            |
|  (Uniform Random)        (Secret)       (Small Error)  (Output)                   |
|                                                                                   |
|  [ a11  a12  ...  a1n ]  [ s1 ]         [ e1 ]         [ b1 ]                     |
|  | a21  a22  ...  a2n |  | s2 |         | e2 |         | b2 |                     |
|  |  :    :    :    :  | *| :  |    +    | :  |    =    | :  |   mod q              |
|  [ am1  am2  ...  amn ]  [ sn ]         [ em ]         [ bm ]                     |
|                                                                                   |
|  GAUSSIAN ELIMINATION BREAKS: Adding error e renders linear algebra solvers      |
|  incapable of isolating s. The problem becomes as hard as solving CVP in R^n.     |
|                                                                                   |
+-----------------------------------------------------------------------------------+

By adding the small error vector $\mathbf{e}$, Gaussian elimination fails completely: subtracting equations amplifies the unknown error terms rather than eliminating variables. The system transitions from trivial linear algebra to an NP-hard search problem.

Ring-LWE and Module-LWE Architectures

While standard LWE provides strong security guarantees, it requires large public keys. For dimension $n = 512$ and $m = 512$, the random matrix $\mathbf{A}$ contains $512 \times 512 = 262,144$ matrix elements, producing public keys exceeding 800 kilobytes. This key size is impractical for TLS handshakes and packet frames.

To shrink key sizes, cryptographers developed Ring-LWE and Module-LWE.

Ring-LWE: Structuring Matrices into Polynomial Rings

Ring-LWE replaces scalar entries in the matrix $\mathbf{A}$ with elements of a polynomial quotient ring:

$$R_q = \mathbb{Z}_q[X] / (X^n + 1)$$

Where:

• $n$ is a power of two (typically $n = 256$).
• $q$ is a prime modulus (in Kyber/ML-KEM, $q = 3329$).
• Polynomials in $R_q$ have degree at most $n-1 = 255$, with integer coefficients modulo $q$.
• Multiplying two polynomials is computed modulo $X^n + 1$, meaning $X^n \equiv -1$.

In Ring-LWE, a single polynomial $a(X) \in R_q$ replaces an entire $n \times n$ matrix, reducing public key storage requirements by a factor of $n$.

Module-LWE: Balancing Security and Flexibility

Ring-LWE imposes rigid structural algebraic assumptions: the entire security of the scheme rests on a single polynomial ring of degree $n$. If an algebraic attack breaks that specific ring structure, the cryptosystem fails.

Module-LWE (M-LWE) combines the flexibility of standard LWE with the efficiency of Ring-LWE. Instead of a single polynomial or a massive matrix of scalars, Module-LWE uses a small $k \times k$ matrix of polynomials:

$$\mathbf{A}(X) \in R_q^{k \times k}$$

$$\mathbf{b}(X) = \mathbf{A}(X) \cdot \mathbf{s}(X) + \mathbf{e}(X) \pmod q$$

Where:

• $k$ is the module rank parameter:
  • ML-KEM-512 (Security Category 1, equivalent to AES-128): $k = 2$.
  • ML-KEM-768 (Security Category 3, equivalent to AES-192): $k = 3$.
  • ML-KEM-1024 (Security Category 5, equivalent to AES-256): $k = 4$.

+-----------------------------------------------------------------------------------+
|                        MODULE-LWE (M-LWE) MATRIX STRUCTURE                        |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  Matrix A(X) (k x k Polynomials)    Secret s(X)    Noise e(X)    Vector b(X)      |
|  +-------------------------------+  +----------+   +----------+  +----------+     |
|  | a11(X)   a12(X)   a13(X)      |  | s1(X)    |   | e1(X)    |  | b1(X)    |     |
|  | a21(X)   a22(X)   a23(X)      | *| s2(X)    | + | e2(X)    | =| b2(X)    |     |
|  | a31(X)   a32(X)   a33(X)      |  | s3(X)    |   | e3(X)    |  | b3(X)    |     |
|  +-------------------------------+  +----------+   +----------+  +----------+     |
|                                                                                   |
|  Each element a_ij(X) is a 256-degree polynomial in Z_3329[X] / (X^256 + 1).      |
|  Modifying security level (k=2, 3, 4) reuses the exact same 256-degree ring!       |
|                                                                                   |
+-----------------------------------------------------------------------------------+

Module-LWE allows adjusting security levels simply by changing the rank parameter $k$, keeping the polynomial degree $n = 256$ and prime modulus $q = 3329$ constant across all security tiers.

Deep Dive: The ML-KEM / Kyber Cryptosystem

ML-KEM consists of three algorithms: Key Generation (KeyGen), Encapsulation (Encaps), and Decapsulation (Decaps).

1. Concrete Parameters (FIPS 203)

Why $q = 3329$? The prime $q = 3329$ was chosen because $3329 \equiv 1 \pmod{512}$. This property permits the Number Theoretic Transform (NTT) to split the polynomial ring into 128 degree-1 sub-fields, enabling fast polynomial multiplication in $O(n \log n)$ time.

2. Centered Binomial Noise Distribution ($\beta_\eta$)

The secret vector $\mathbf{s}$ and error vector $\mathbf{e}$ are not sampled uniformly at random across $\mathbb{Z}q$. They are sampled from a Centered Binomial Distribution $\beta\eta$ with parameter $\eta$.

To sample a single polynomial coefficient from $\beta_\eta$:

1. Draw $2\eta$ independent uniform random bits: $a_1, a_2, \dots, a_\eta$ and $b_1, b_2, \dots, b_\eta$.
2. Compute the coefficient value:

$$x = \sum_{i=1}^\eta a_i - \sum_{i=1}^\eta b_i$$

For $\eta = 2$, the output $x$ takes values in ${-2, -1, 0, 1, 2}$ with probabilities:

$$P(X = -2) = \frac{1}{16}, \quad P(X = -1) = \frac{4}{16}, \quad P(X = 0) = \frac{6}{16}, \quad P(X = 1) = \frac{4}{16}, \quad P(X = 2) = \frac{1}{16}$$

+-----------------------------------------------------------------------------------+
|               CENTERED BINOMIAL DISTRIBUTION (ETA = 2) PROBABILITY                |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  Probability                                                                      |
|     6/16 |                    +-------+                                           |
|     5/16 |                    |       |                                           |
|     4/16 |            +-------+       +-------+                                   |
|     3/16 |            |       |       |       |                                   |
|     2/16 |            |       |       |       |                                   |
|     1/16 |    +-------+       |       |       +-------+                           |
|      0   +----+-------+-------+-------+-------+-------+----> Coefficient Value    |
|              -2      -1       0       1       2                                   |
|                                                                                   |
|  Properties: Centered at 0, small magnitude, symmetric bounds.                    |
|                                                                                   |
+-----------------------------------------------------------------------------------+

This distribution concentrates coefficients near zero while injecting enough variance to make finding $\mathbf{s}$ NP-hard.

3. Key Generation (KeyGen)

The goal of KeyGen is to produce a public key containing a random matrix $\mathbf{A}$ and a noisy output vector $\mathbf{t} = \mathbf{A} \cdot \mathbf{s} + \mathbf{e}$.

ALGORITHM 1: ML-KEM.KeyGen()
--------------------------------------------------------------------------------
Input:  None (uses system randomness)
Output: Public Key pk, Secret Key sk
 
1. Sample 32 random bytes z and 32 random bytes d from CSPRNG.
2. (rho, sigma) := G(d)                   // Expand seed via SHA3-512
3. A_hat := Parse(XOF(rho))              // Generate k x k matrix A in NTT domain
4. (s, e) := Sample_CBD(PRF(sigma))       // Sample secret s and error e from CBD
5. s_hat := NTT(s)                       // Convert secret to NTT domain
6. e_hat := NTT(e)                       // Convert error to NTT domain
7. t_hat := A_hat * s_hat + e_hat        // Matrix-vector multiplication in NTT
8. pk := ByteEncode(t_hat) || rho        // Public key is public vector t and seed rho
9. sk := ByteEncode(s_hat) || pk || H(pk) || z

+-----------------------------------------------------------------------------------+
|                        ML-KEM KEY GENERATION FLOW                                 |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  Seed d  ---> [ G (SHA3-512) ] ---> Seed rho  ---> [ SHAKE-128 XOF ] -> Matrix A  |
|                                `--> Seed sigma -> [ PRF (CBD) ]    -> Secret s    |
|                                                                    -> Error e     |
|                                                                                   |
|  NTT Domain Computation:                                                          |
|  t_hat = ( A_hat * s_hat ) + e_hat                                                |
|                                                                                   |
|  PUBLIC KEY  (pk):  [ Vector t_hat (encoded) ] + [ Seed rho (32 bytes) ]          |
|  SECRET KEY  (sk):  [ Vector s_hat (encoded) ] + [ pk ] + [ H(pk) ] + [ Seed z ] |
|                                                                                   |
+-----------------------------------------------------------------------------------+

Notice that the matrix $\mathbf{A}$ is not transmitted explicitly in the public key. Instead, the 32-byte seed rho is transmitted. The recipient regenerates the exact $k \times k$ matrix $\mathbf{A}$ deterministically by passing rho into the SHAKE-128 Extendable Output Function (XOF). This optimization shrinks the public key from hundreds of kilobytes down to 1,184 bytes for ML-KEM-768.

4. Encryption and Encapsulation (Encaps)

Key Encapsulation Mechanisms do not encrypt arbitrary long messages directly. They establish a shared 256-bit symmetric key $K$ between two parties, which is then used with authenticated symmetric ciphers such as AES-256-GCM or ChaCha20-Poly1305.

ALGORITHM 2: ML-KEM.Encaps(pk)
--------------------------------------------------------------------------------
Input:  Public Key pk
Output: Ciphertext c, Shared Secret K
 
1. Sample 32 random bytes m from CSPRNG.
2. (K_bar, r) := G(m || H(pk))           // Derive pseudo-random coins r and key seed
3. A_hat := Parse(XOF(rho))              // Regenerate matrix A from seed rho in pk
4. (y, e1, e2) := Sample_CBD(PRF(r))     // Sample ephemeral vectors y, e1, and noise e2
5. y_hat := NTT(y)                       // Convert ephemeral secret to NTT domain
6. u := NTT_Inverse(A_hat^T * y_hat) + e1// Vector u calculation
7. v := NTT_Inverse(t_hat^T * y_hat) + e2 + Decompress(m) // Vector v calculation
8. c := Compress(u) || Compress(v)       // Compress and format ciphertext
9. K := KDF(K_bar || H(c))               // Final shared key derivation

How the Message $m$ Is Encoded into Polynomial Space

The 32-byte message $m$ consists of 256 individual bits $m_0, m_1, \dots, m_{255}$.

To add the message $m$ to a polynomial $v(X)$, each bit $m_i$ is mapped to a high-distance polynomial coefficient modulo $q = 3329$:

$$\text{Decompress}(m_i) = \begin{cases} 0 & \text{if } m_i = 0 \ \left\lceil \frac{q}{2} \right\rceil = 1665 & \text{if } m_i = 1 \end{cases}$$

+-----------------------------------------------------------------------------------+
|                        MESSAGE BIT POLYNOMIAL ENCODING                            |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  Bit m_i = 0  ---> Mapped to coefficient value   0                               |
|  Bit m_i = 1  ---> Mapped to coefficient value 1665 (q/2 = 3329/2)                |
|                                                                                   |
|  COEFFICIENT SPACE MODULO 3329:                                                   |
|                                                                                   |
|          Bit 0 Region                      Bit 1 Region             Bit 0 Region  |
|      [ -832  to  +832 ]                [ +833  to  +2496 ]        [ +2497 ... ] |
|  <------------------------->      <------------------------->      <------------> |
|  0                         832    833                     2496    2497       3328 |
|                            ^                               ^                      |
|                            |--- Decoding Threshold Boundary |                      |
|                                                                                   |
|  NOISE TOLERANCE: Noise additions up to +/- 832 leave bits correctly decodable!   |
|                                                                                   |
+-----------------------------------------------------------------------------------+

Setting $m_i = 1$ to $\lceil q/2 \rceil = 1665$ maximizes the Euclidean distance between 0 and 1 in the modular ring $\mathbb{Z}_{3329}$. As long as accumulated noise errors remain less than $q/4 \approx 832$, the recipient can decode the message bit without error.

5. Decapsulation (Decaps)

The recipient receives ciphertext $c = (u, v)$ and computes an estimate of the message $m$.

ALGORITHM 3: ML-KEM.Decaps(c, sk)
--------------------------------------------------------------------------------
Input:  Ciphertext c = (u, v), Secret Key sk
Output: Shared Secret K
 
1. Extract (s_hat, pk, h, z) from sk
2. (u_vec, v_poly) := Decompress(c)
3. u_hat := NTT(u_vec)
4. w := v_poly - NTT_Inverse(s_hat^T * u_hat)   // Noise subtraction step
5. m' := Compress_Bits(w)                       // Decode message bits from coefficients
6. (K_bar', r') := G(m' || h)                  // Re-encrypt verification
7. c' := Encrypt_Internal(pk, m', r')          // Regenerate expected ciphertext
8. if c == c':
       return KDF(K_bar' || H(c))               // Success path
   else:
       return KDF(z || H(c))                    // Rejection path (Implicit Rejection)

Mathematical Proof of Noise Cancellation

Let us trace the algebraic expansion of the decapsulation term $w$:

Recall the ciphertext constructions from Encapsulation: $$\mathbf{u} = \mathbf{A}^T \mathbf{y} + \mathbf{e}_1$$

$$v = \mathbf{t}^T \mathbf{y} + e_2 + \left\lceil \frac{q}{2} \right\rceil m$$

Recall the public key from KeyGeneration: $$\mathbf{t} = \mathbf{A} \mathbf{s} + \mathbf{e}$$

Now expand $w = v - \mathbf{s}^T \mathbf{u}$:

$$w = \left( \mathbf{t}^T \mathbf{y} + e_2 + \left\lceil \frac{q}{2} \right\rceil m \right) - \mathbf{s}^T \left( \mathbf{A}^T \mathbf{y} + \mathbf{e}_1 \right)$$

Substitute $\mathbf{t}^T = (\mathbf{A} \mathbf{s} + \mathbf{e})^T = \mathbf{s}^T \mathbf{A}^T + \mathbf{e}^T$:

$$w = \left( (\mathbf{s}^T \mathbf{A}^T + \mathbf{e}^T) \mathbf{y} + e_2 + \left\lceil \frac{q}{2} \right\rceil m \right) - \mathbf{s}^T \mathbf{A}^T \mathbf{y} - \mathbf{s}^T \mathbf{e}_1$$

$$w = \mathbf{s}^T \mathbf{A}^T \mathbf{y} + \mathbf{e}^T \mathbf{y} + e_2 + \left\lceil \frac{q}{2} \right\rceil m - \mathbf{s}^T \mathbf{A}^T \mathbf{y} - \mathbf{s}^T \mathbf{e}_1$$

The structural matrix terms $\mathbf{s}^T \mathbf{A}^T \mathbf{y}$ cancel out identically:

$$w = \left\lceil \frac{q}{2} \right\rceil m + \underbrace{\left( \mathbf{e}^T \mathbf{y} + e_2 - \mathbf{s}^T \mathbf{e}1 \right)}{\text{Combined Noise Vector } E}$$

$$w = \left\lceil \frac{q}{2} \right\rceil m + E$$

The decapsulator is left with the original message scaled by $\lceil q/2 \rceil$, plus an accumulated noise vector $E = \mathbf{e}^T \mathbf{y} + e_2 - \mathbf{s}^T \mathbf{e}_1$.

Because $\mathbf{s}, \mathbf{e}, \mathbf{y}, \mathbf{e}1, e_2$ were all sampled from the narrow Centered Binomial Distribution $\beta\eta$, the magnitude of every entry in $E$ is bounded well below $q/4 = 832$.

When the decoder rounds each coefficient of $w$:

• If the coefficient is close to $0 \pmod q$ (within $[-832, 832]$), it decodes bit $m_i = 0$.
• If the coefficient is close to $1665 \pmod q$ (within $[833, 2496]$), it decodes bit $m_i = 1$.

The noise is eliminated, recovering the exact 32-byte message $m$ with zero error.

Number Theoretic Transform (NTT) Acceleration

The core computational bottleneck in lattice cryptography is polynomial multiplication in the quotient ring $R_q = \mathbb{Z}_q[X]/(X^{256} + 1)$.

Naively multiplying two 256-degree polynomials using schoolbook multiplication requires $256^2 = 65,536$ coefficient multiplications.

ML-KEM avoids this bottleneck by using the Number Theoretic Transform (NTT), a Discrete Fourier Transform (DFT) evaluated over finite modular fields.

+-----------------------------------------------------------------------------------+
|                        NTT POLYNOMIAL MULTIPLICATION FLOW                         |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  Standard Space Polynomials: a(X), b(X)   (65,536 operations via schoolbook)       |
|       |                                                                           |
|       |-- NTT(a) -------------> a_hat(X)  (256 operations)                       |
|       |-- NTT(b) -------------> b_hat(X)  (256 operations)                       |
|                                      |                                            |
|                                      v Pointwise Multiplication                   |
|                                 c_hat = a_hat * b_hat  (256 operations)           |
|                                      |                                            |
|       |<-- INVERSE_NTT(c_hat) <------'                                            |
|       v                                                                           |
|  Result Polynomial: c(X) = a(X) * b(X) mod (X^256 + 1)                            |
|                                                                                   |
|  TOTAL TIME COMPLEXITY: O(n log n)  --> Reduced from 65,536 to ~1,280 ops!        |
|                                                                                   |
+-----------------------------------------------------------------------------------+

Algebraic Splitting of $X^{256} + 1$ Modulo 3329

The polynomial $X^{256} + 1$ factors into 128 quadratic polynomials over $\mathbb{Z}_{3329}$:

$$X^{256} + 1 = \prod_{i=0}^{127} \left(X^2 - \gamma^{2i+1}\right) \pmod{3329}$$

Where $\gamma = 17$ is a primitive 256th root of unity in $\mathbb{Z}_{3329}$, satisfying $\gamma^{256} \equiv 1 \pmod{3329}$ and $\gamma^{128} \equiv -1 \pmod{3329}$.

The NTT maps a 256-degree polynomial $f(X)$ into 128 degree-1 polynomials:

$$\hat{f}i(X) = f{0,i} + f_{1,i} X \in \mathbb{Z}_{3329}[X] / \left(X^2 - \gamma^{2 \text{bitrev}(i) + 1}\right)$$

Multiplying two polynomials in the NTT domain requires 128 independent degree-1 polynomial multiplications:

$$(a_0 + a_1 X)(b_0 + b_1 X) = (a_0 b_0 + a_1 b_1 \gamma^{2k+1}) + (a_0 b_1 + a_1 b_0) X \pmod{X^2 - \gamma^{2k+1}}$$

Each degree-1 multiplication requires 4 scalar multiplications in $\mathbb{Z}_{3329}$. Total multiplication across the entire 256-degree ring requires $128 \times 4 = 512$ scalar operations instead of 65,536, yielding a 128-fold speedup.

Butterfly Operations and Montgomery Reduction

High-performance C implementations of NTT use Cooley-Tukey butterfly circuits for forward NTT and Gentleman-Sande butterflies for inverse NTT.

Because butterfly updates repeatedly multiply integer coefficients, implementations rely on Montgomery Reduction to keep modular arithmetic fast without division instructions.

For a 32-bit integer product $a \cdot b$, Montgomery reduction computes:

$$\text{MontReduce}(a \cdot b) = (a \cdot b \cdot R^{-1}) \pmod q$$

Where $R = 2^{16} = 65536$. By keeping all NTT coefficients in the Montgomery domain, multiplication requires only 3 register multiplications, 1 bitwise shift, and 0 division instructions per butterfly.

IND-CCA2 Security and the Fujisaki-Okamoto Transform

A basic lattice encryption scheme (like the internal Encrypt_Internal routine) is only passively secure against chosen-plaintext attacks (IND-CPA). If an attacker can submit adaptively chosen ciphertexts to a decapsulation oracle, they can craft malicious ciphertexts with tailored noise vectors $E$ to trigger decryption failures, recovering the secret key $\mathbf{s}$ bit by bit.

To prevent chosen-ciphertext attacks (IND-CCA2), ML-KEM wraps the underlying CPA-secure scheme inside the Fujisaki-Okamoto (FO) Transform.

+-----------------------------------------------------------------------------------+
|                        FUJISAKI-OKAMOTO (FO) TRANSFORM                            |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  Received Ciphertext c = (u, v)                                                   |
|         |                                                                         |
|         v Decrypt using secret key s                                              |
|  Recovered Message Candidate m'                                                   |
|         |                                                                         |
|         v Re-derive coins: (K_bar', r') = G(m' || H(pk))                          |
|  Re-encrypt: c' = Encrypt_Internal(pk, m', r')                                    |
|         |                                                                         |
|         +-----------------------+-----------------------+                         |
|         |                                               |                         |
|         v (Does c' == c ?)                              v (Does c' != c ?)        |
|  MATCH: Valid Ciphertext                      MISMATCH: Tampered Ciphertext       |
|  Return K = KDF(K_bar' || H(c))               Return K = KDF(z || H(c))           |
|  (Legitimate Session Key)                     (Implicit Rejection Pseudo-Random)  |
|                                                                                   |
+-----------------------------------------------------------------------------------+

The Implicit Rejection Defense

When decapsulating a ciphertext $c$:

1. The recipient decrypts $c$ to recover candidate message $m'$.
2. The recipient re-encrypts $m'$ using the public key pk and the deterministic coins $r' = G(m' \parallel H(pk))$ to produce expected ciphertext $c'$.
3. The recipient checks whether $c' == c$:
   • If $c' == c$: The ciphertext was formed correctly without tampering. Return the valid key $K = \text{KDF}(\bar{K}' \parallel H(c))$.
   • If $c' \neq c$: The ciphertext was modified or constructed maliciously. The recipient does not return an error code or alert. Returning an error code would give an attacker a side-channel oracle confirming that the ciphertext was invalid. Instead, the recipient returns a deterministic pseudo-random key $K = \text{KDF}(z \parallel H(c))$, derived from a secret random seed $z$ stored in the secret key.

Because the attacker receives a pseudo-random key that is indistinguishable from a real key, the attack fails without revealing whether decapsulation failed due to noise bounds or ciphertext tampering. This provides IND-CCA2 security.

Side-Channel Security and Constant-Time Implementation Invariants

Lattice cryptosystems introduce physical security considerations beyond traditional integer arithmetic. Because operations depend on conditional checks and polynomial coefficient distributions, software implementations must eliminate side-channel vulnerabilities:

1. Constant-Time Comparison: The byte comparison $c' == c$ in step 8 of decapsulation must execute in constant time regardless of where a byte mismatch occurs. Using standard C memcmp() creates a timing oracle allowing attackers to learn matching ciphertext bytes. Implementations use bitwise OR accumulation over constant-time XOR differences.
2. Constant-Time CBD Sampling: Sampling from the Centered Binomial Distribution $\beta_\eta$ must not use conditional branches based on secret bits. Coefficients are generated using popcount operations (such as __builtin_popcount or SIMD vcnt) over 32-bit unsigned integers.
3. Table Leakage Mitigation in NTT: Lookups into the zetas array of powers of $\gamma$ must be memory-aligned and accessed systematically to prevent microarchitectural cache-line leakage. SIMD vector implementations (using AVX2 on x86-64 or NEON on ARM64) load zetas into vector registers, preventing secret-dependent data cache access patterns.

C Reference Implementation: Polynomial Multiplication and NTT

The following C program implements single-polynomial NTT transformation, pointwise multiplication, and inverse NTT reduction in $R_{3329}[X]/(X^{256} + 1)$.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
 
#define N 256
#define Q 3329
#define MONTGOMERY_R 2285 // 2^16 mod 3329
#define QINV 62209        // -q^-1 mod 2^16
 
// Primitive 256th root of unity modulo 3329
static const int16_t zetas[128] = {
    -1044,  -758,   -89, -1344,  -409,  -496,  1176,   147,
     1249,   444,   825,  1331,  1400,  1526, -1510,  -982,
     1328,  1297, -1349,  -844, -1481,  -145,  1279,  -779,
     -783,  1152,   178, -1274,  1006, -1141,   252,   807,
     -516,  -248,  -916,   130,  -872,  -630,  -356,  1030,
      176, -1172, -1202, -1078,  1315,  -395, -1164,   734,
     -769,  -416,  1227,   910,   860,  -384,  -813,  1105,
      947,  -867,  -144,  -822,   634,  -902, -1207,  1119,
     1482,  -668,  1145, -1094,   763, -1149, -1451,   564,
     -946,  -244,  1330,   955, -1254,  -483,  1028,   895,
     -957,  -707,  -371, -1231,   604, -1124,   990, -1265,
     -923, -1340,   978,  -823, -1357,   854,   772,   466,
     -290,   370,   848,  -377,  -366,  1114,  -435,   482,
      761, -1004, -1250,  -275,   820,  1291,  -650,  -805,
      912,    41, -1089, -1123, -1325,  -413, -1300,   122,
     1126,  1071, -1062,   950, -1066,   476,  1226,  -753
};
 
// Montgomery Reduction: computes (a * R^-1) mod Q
static int16_t montgomery_reduce(int32_t a) {
    int16_t u = (int16_t)(a * QINV);
    int32_t t = (int32_t)u * Q;
    int16_t res = (int16_t)((a - t) >> 16);
    return res;
}
 
// Canonical modular reduction into [0, Q-1]
static int16_t barrett_reduce(int16_t a) {
    int16_t t = (int16_t)(((int32_t)a * 20159) >> 26);
    a -= t * Q;
    if (a >= Q) a -= Q;
    if (a < 0) a += Q;
    return a;
}
 
// Forward Number Theoretic Transform (In-Place Cooley-Tukey)
void ntt(int16_t poly[N]) {
    int len, start, j, k = 1;
    int16_t zeta, t;
 
    for (len = 128; len >= 2; len >>= 1) {
        for (start = 0; start < N; start += 2 * len) {
            zeta = zetas[k++];
            for (j = start; j < start + len; ++j) {
                t = montgomery_reduce((int32_t)zeta * poly[j + len]);
                poly[j + len] = poly[j] - t;
                poly[j] = poly[j] + t;
            }
        }
    }
 
    for (j = 0; j < N; ++j) {
        poly[j] = barrett_reduce(poly[j]);
    }
}
 
// Pointwise multiplication in NTT domain
void poly_basemul_montgomery(int16_t r[N], const int16_t a[N], const int16_t b[N]) {
    for (int i = 0; i < N / 2; ++i) {
        int16_t rx = montgomery_reduce((int32_t)a[2*i] * b[2*i] + 
                                       montgomery_reduce((int32_t)a[2*i+1] * b[2*i+1]) * zetas[64 + i]);
        int16_t ry = montgomery_reduce((int32_t)a[2*i] * b[2*i+1] + (int32_t)a[2*i+1] * b[2*i]);
        r[2*i]   = barrett_reduce(rx);
        r[2*i+1] = barrett_reduce(ry);
    }
}
 
int main(void) {
    int16_t poly_a[N];
    int16_t poly_b[N];
    int16_t poly_c[N];
 
    memset(poly_a, 0, sizeof(poly_a));
    memset(poly_b, 0, sizeof(poly_b));
 
    // Test polynomial a(X) = 5 + 3X
    poly_a[0] = 5;
    poly_a[1] = 3;
 
    // Test polynomial b(X) = 2 + 7X
    poly_b[0] = 2;
    poly_b[1] = 7;
 
    printf("Executing Number Theoretic Transform (NTT) on R_3329[X] / (X^256 + 1)...\n");
 
    ntt(poly_a);
    ntt(poly_b);
 
    poly_basemul_montgomery(poly_c, poly_a, poly_b);
 
    printf("Pointwise multiplication completed successfully in NTT domain.\n");
    printf("First two NTT domain coefficients: c[0] = %d, c[1] = %d\n", poly_c[0], poly_c[1]);
 
    return 0;
}

Performance and Security Parameter Comparison

While post-quantum public keys and ciphertexts are larger than classical X25519 keys, ML-KEM execution speed (KeyGen, Encaps, and Decaps) is significantly faster than RSA-2048 and competitive with Curve25519 due to $O(n \log n)$ NTT acceleration.

Summary

Post-quantum lattice cryptography replaces integer factorization and discrete logarithms with the geometry of high-dimensional discrete vector spaces:

1. Quantum Resistance: Shor's algorithm solves hidden subgroup problems over abelian groups in polynomial time, but fails against the Shortest Vector Problem (SVP) and Learning With Errors (LWE) over high-dimensional lattices.
2. Module-LWE Construction: Structuring matrices into polynomial rings $R_q = \mathbb{Z}_{3329}[X]/(X^{256} + 1)$ reduces public key sizes from megabytes to approximately 1 kilobyte while preserving security modularity.
3. Centered Binomial Noise: Sampling secrets and error vectors from a narrow binomial distribution $\beta_\eta$ prevents Gaussian elimination while keeping noise bounds within $q/4 \approx 832$ decoding thresholds.
4. NTT Acceleration: Factoring $X^{256} + 1$ into 128 quadratic polynomials over $\mathbb{Z}_{3329}$ enables polynomial multiplication in $O(n \log n)$ time, providing a 128-fold speedup over schoolbook multiplication.
5. IND-CCA2 Security via Fujisaki-Okamoto: Re-encrypting candidate messages during decapsulation and returning pseudo-random keys on mismatch (implicit rejection) thwarts chosen-ciphertext attacks without creating timing or error oracles.

By combining lattice geometry with algebraic polynomial rings, ML-KEM ensures robust, high-performance confidential communications in the post-quantum era.