Notebook 05 — Ring-LWE and Module-LWE

Goal: lift LWE from scalars to polynomials, and then to vectors of polynomials.

Ring-LWE (RLWE) restates LWE inside the ring R_q = Z_q[x]/(x^n + 1). Secret s, error e, and public coefficient a are polynomials. A sample is (a, b = a.s + e) in R_q x R_q. One polynomial packs n values, so one RLWE sample replaces n plain-LWE samples.

import numpy as np
from pqc_edu.polyring import Poly
from pqc_edu.ntt import ntt, intt, pointwise_mul, poly_mul_ntt, Q, N
from pqc_edu.sampling import prf, cbd, sample_uniform

rho = b'\x01' * 32
sigma = b'\x02' * 32
a = sample_uniform(rho, 0, 0)          # uniform a in R_q (NTT domain)
s = cbd(prf(sigma, 0, N * 3 // 4), eta=3)  # small secret (time domain)
e = cbd(prf(sigma, 1, N * 3 // 4), eta=3)  # small error  (time domain)
s_hat = ntt(s)
# b_hat = a * s_hat + ntt(e), but since a is already in NTT domain:
b_hat = pointwise_mul(a, s_hat) + ntt(e)
print('a (first 5 coeffs, NTT dom):', a.coeffs[:5].tolist())
print('s (first 5 coeffs, time) :', s.coeffs[:5].tolist())
print('e (first 5 coeffs, time) :', e.coeffs[:5].tolist())
print('b (first 5 coeffs, NTT dom):', b_hat.coeffs[:5].tolist())

a (first 5 coeffs, NTT dom): [1590, 2952, 2536, 830, 2397]
s (first 5 coeffs, time) : [3328, 3328, 1, 3328, 3328]
e (first 5 coeffs, time) : [1, 2, 3327, 3327, 3327]
b (first 5 coeffs, NTT dom): [92, 925, 2929, 2360, 90]

Why Module-LWE (MLWE)? Ring-LWE’s strong algebraic structure (one prime-power cyclotomic ring) worried some cryptographers — fewer degrees of freedom means fewer knobs for security analysis. Module-LWE works in R_q^k: s and e are length-k vectors of polynomials; A is a kxk matrix of polynomials. ML-KEM uses k in {2, 3, 4} — a compromise between plain-LWE generality and Ring-LWE efficiency.

k = 2
rho = b'\x11' * 32
sigma = b'\x22' * 32
eta = 2

# Build k x k matrix A (in NTT domain)
A_hat = [[sample_uniform(rho, i, j) for j in range(k)] for i in range(k)]
# Secret s, error e: length-k vectors of small CBD polys
s = [cbd(prf(sigma, i, N*eta//4), eta) for i in range(k)]
e = [cbd(prf(sigma, k + i, N*eta//4), eta) for i in range(k)]
s_hat = [ntt(p) for p in s]
# t_hat = A_hat @ s_hat + ntt(e)
t_hat = []
for i in range(k):
    acc = Poly.zero(N, Q)
    for j in range(k):
        acc = acc + pointwise_mul(A_hat[i][j], s_hat[j])
    acc = acc + ntt(e[i])
    t_hat.append(acc)
print('Built MLWE public key t_hat with', k, 'polynomials, each of length', N)
print('first 5 coeffs of t_hat[0]:', t_hat[0].coeffs[:5].tolist())

Built MLWE public key t_hat with 2 polynomials, each of length 256
first 5 coeffs of t_hat[0]: [3111, 804, 3259, 1591, 989]

This is exactly the public-key shape ML-KEM uses: (A, t = A.s + e) with s, e small. The next notebook implements the full FIPS 203 K-PKE encryption on top of this, plus the Fujisaki-Okamoto wrapper for CCA security. -> 06_ml_kem_spec.ipynb.