Sampling Module-LWE Instances: A Reference Reproduction

Before measuring anything about structured-lattice schemes, it helps to have a small, unambiguous generator for the underlying hard instances. This note gives a reference sampler for the Module Learning With Errors (Module-LWE) distribution and nothing more — no scheme, no optimization, just a fixture.

The distribution

Work over the cyclotomic ring $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ with $n$ a power of two. A Module-LWE sample of rank $k$ is a pair drawn as follows: a uniform vector $\mathbf{a}$, a fixed secret $\mathbf{s}$, and a small error $e$ combine into the second coordinate.

$$(\mathbf{a},\, b) \in R_q^{k} \times R_q, \qquad \mathbf{a} \sim \mathcal{U}\!\left(R_q^{k}\right), \quad b = \mathbf{a}^{\top}\mathbf{s} + e \pmod{q},$$

where each coefficient of $\mathbf{s}$ and $e$ is drawn from a small centered distribution $\chi$ (here, a centered binomial). The hardness assumption is that $(\mathbf{a}, b)$ is computationally indistinguishable from $(\mathbf{a}, u)$ for $u \sim \mathcal{U}(R_q)$.

A reference sampler

The implementation mirrors the equation line for line: sample $\mathbf{a}$ uniformly, sample $\mathbf{s}$ and $e$ from $\chi$, and form $b$ in the ring.

import numpy as np

def cbd(eta, shape, rng):
    """Centered binomial distribution with parameter eta."""
    a = rng.integers(0, 2, size=(*shape, eta)).sum(-1)
    b = rng.integers(0, 2, size=(*shape, eta)).sum(-1)
    return a - b

def ring_mul(f, g, q, n):
    """Multiply in Z_q[x]/(x^n + 1) via the negacyclic convolution."""
    full = np.convolve(f, g)
    lo, hi = full[:n], full[n:]
    res = lo.copy()
    res[: hi.size] -= hi          # x^n = -1
    return res % q

def sample_mlwe(k, n, q, eta, rng):
    a = rng.integers(0, q, size=(k, n))          # a ~ U(R_q^k)
    s = cbd(eta, (k, n), rng) % q                # s_i <- chi
    e = cbd(eta, (n,), rng) % q                  # e   <- chi
    b = np.zeros(n, dtype=np.int64)
    for i in range(k):
        b = (b + ring_mul(a[i], s[i], q, n)) % q  # b = a^T s + e
    return a, (b + e) % q

rng = np.random.default_rng(20260603)
a, b = sample_mlwe(k=2, n=256, q=3329, eta=2, rng=rng)
print(a.shape, b.shape)   # (2, 256) (256,)

The parameters above ($n = 256$, $q = 3329$, $k = 2$) are deliberately the ML-KEM-512 ring, so the fixture lines up with a real scheme — but this code makes no security claim. It exists to be counted and timed, which is what the Assumption Diversification measurements need next.