08e-ring-lwe.ipynb

Kernel: SageMath 10.5

Ring-LWE: Structured Lattices for Efficient Cryptography

Module 08e | Lattices and Post-Quantum Cryptography

From random matrices to polynomial rings, shrinking keys from megabytes to kilobytes.

Objectives

By the end of this notebook you will be able to:

1. Explain why plain LWE has impractically large keys and how algebraic structure fixes this.

2. Work confidently in the polynomial quotient ring $R_q = \mathbb{Z}_q[x]/(x^n+1)$.

3. Generate and verify a Ring-LWE instance in SageMath.

4. Visualize the negacyclic matrix that underlies polynomial multiplication in $R_q$.

5. Compare LWE, Ring-LWE, and Module-LWE in terms of key size and security assumptions.

6. Use the Number Theoretic Transform (NTT) for fast polynomial multiplication.

Prerequisites

• 08d. Learning With Errors: you know that LWE gives us $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \bmod q)$ where $\mathbf{A}$ is a random matrix, $\mathbf{s}$ is a secret vector, and $\mathbf{e}$ is a small noise vector.

• 02c. Polynomial Rings and 02f. Quotient Rings: you have seen how to form quotient rings $R[x]/(f(x))$ and do arithmetic in them.

Bridge from 08d: In the LWE notebook, we saw that the public matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ is completely random, every entry is independent. This gives strong security guarantees, but it also means the public key contains $m \cdot n$ ring elements. For practical parameters ($n \approx 1024$), that is over a million integers just for the matrix. Can we do better?

1. The Key-Size Problem in Plain LWE

Motivating Question: LWE keys are megabytes large. Can we add mathematical STRUCTURE to shrink them to kilobytes, without making the problem easy to solve?

Let us make the problem concrete. In standard LWE with security parameter $n$, the public matrix $\mathbf{A}$ has dimensions roughly $n \times n$ (we often take $m \approx n$ samples). Each entry is an element of $\mathbb{Z}_q$, requiring $\lceil \log_2 q \rceil$ bits.

For NIST-level security ($n = 1024$, $q \approx 2^{12}$), the matrix $\mathbf{A}$ alone requires:

$$n^2 \cdot \lceil \log_2 q \rceil = 1024^2 \cdot 12 \approx 12{,}582{,}912 \text{ bits} \approx 1.5 \text{ MB}$$

That is enormous for a public key. Compare: RSA-2048 has a 256-byte key, and ECC uses about 32 bytes. We need a way to compress $\mathbf{A}$ while preserving the hardness of the underlying problem.

# --- Key size comparison: plain LWE ---

n_param = 1024
q_param = 3329       # Kyber's modulus
bits_per_elem = ceil(log2(q_param))

lwe_matrix_bits = n_param^2 * bits_per_elem
lwe_matrix_bytes = lwe_matrix_bits / 8

print(f"Plain LWE (n={n_param}, q={q_param}):")
print(f"  Matrix A has {n_param}x{n_param} = {n_param^2} entries")
print(f"  Each entry: {bits_per_elem} bits")
print(f"  Total for A: {lwe_matrix_bits:,} bits = {lwe_matrix_bytes:,.0f} bytes = {lwe_matrix_bytes/1024:.1f} KB")
print()

# Ring-LWE: A is specified by a single polynomial (n coefficients)
rlwe_bits = n_param * bits_per_elem
rlwe_bytes = rlwe_bits / 8

print(f"Ring-LWE (n={n_param}, q={q_param}):")
print(f"  Polynomial a(x) has {n_param} coefficients")
print(f"  Total for a(x): {rlwe_bits:,} bits = {rlwe_bytes:,.0f} bytes = {rlwe_bytes/1024:.1f} KB")
print()
print(f"Compression ratio: {lwe_matrix_bytes / rlwe_bytes:.0f}x smaller!")

A factor of 1024x reduction in key size. That is the power of structure. But the central question is: does this structure make the problem easier to break?

The answer, after over a decade of cryptanalysis, is: for carefully chosen rings, no known attacks exploit the structure. Let us now understand exactly what ring we use and why.

2. The Ring $R_q = \mathbb{Z}_q[x]/(x^n+1)$

Bridge from Module 02: In 02f. Quotient Rings, you learned that we can form a quotient ring $R[x]/(f(x))$ by taking polynomials modulo $f(x)$. Now we apply that same construction with a specific choice: $f(x) = x^n + 1$ where $n$ is a power of 2.

Elements of $R_q = \mathbb{Z}_q[x]/(x^n+1)$ are polynomials of degree at most $n-1$ with coefficients in $\mathbb{Z}_q$:

$$a(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1}, \quad a_i \in \mathbb{Z}_q$$

Addition is coefficient-wise modulo $q$. Multiplication is polynomial multiplication followed by reduction modulo $x^n + 1$ (and coefficients modulo $q$).

The key reduction rule is: $x^n \equiv -1 \pmod{x^n+1}$. This means any power $x^{n+k}$ wraps around with a sign flip: $x^{n+k} \equiv -x^k$.

Why $x^n+1$ specifically? When $n$ is a power of 2, the polynomial $x^n+1$ is the $2n$-th cyclotomic polynomial $\Phi_{2n}(x)$, which is irreducible over $\mathbb{Q}$. This means $R_q$ has no zero divisors when $q$ is chosen appropriately, the ring has good algebraic properties for both security and efficiency.

# --- Setting up R_q in SageMath ---
n = 8       # Small n for pedagogy (power of 2)
q = 17      # Small prime modulus

# Build the quotient ring R_q = Z_q[x] / (x^n + 1)
Zq = Zmod(q)
Px.<x> = PolynomialRing(Zq)
Rq.<xbar> = Px.quotient(x^n + 1)

print(f"Ring: R_q = Z_{q}[x] / (x^{n} + 1)")
print(f"Elements are polynomials of degree <= {n-1} with coefficients in Z_{q}")
print(f"Number of elements: q^n = {q}^{n} = {q^n}")
print()

# Verify the key reduction rule: x^n = -1 in R_q
print(f"x^{n} in R_q = {xbar^n}")
print(f"This equals -1 = {Zq(-1)} (mod {q}), confirming x^n ≡ -1")

# --- Arithmetic in R_q: a worked example ---

# Define two polynomials in R_q
a = Rq([3, 1, 4, 1, 5, 9, 2, 6])   # a(x) = 3 + x + 4x^2 + x^3 + 5x^4 + 9x^5 + 2x^6 + 6x^7
b = Rq([2, 7, 1, 8, 2, 8, 1, 8])   # b(x) = 2 + 7x + x^2 + 8x^3 + 2x^4 + 8x^5 + x^6 + 8x^7

print("a(x) =", a)
print("b(x) =", b)
print()

# Addition: coefficient-wise mod q
print("a + b =", a + b)
print()

# Multiplication: polynomial product, then reduce mod (x^n+1) and mod q
c = a * b
print("a * b =", c)
print()
print("(Remember: any degree-k term with k >= n wraps around with a sign flip)")

Checkpoint, do this by hand first!

Before running the next cell, compute $(1 + 2x) \cdot (3 + x)$ in $R_q$ with $n = 8$, $q = 17$ by hand.

Hint: Multiply normally to get $3 + x + 6x + 2x^2 = 3 + 7x + 2x^2$. Since the degree is less than $n = 8$, no reduction modulo $x^n + 1$ is needed. All coefficients are already less than $q = 17$, so the answer is $3 + 7x + 2x^2$.

# --- Verify your hand computation ---
p1 = Rq([1, 2])      # 1 + 2x
p2 = Rq([3, 1])      # 3 + x
print(f"(1 + 2x) * (3 + x) = {p1 * p2}")
print()

# Now a case where reduction IS needed:
# x^7 * x^2 = x^9 = x^(8+1) = -x^1 (since x^8 = -1)
p3 = Rq([0,0,0,0,0,0,0,1])   # x^7
p4 = Rq([0,0,1])              # x^2
print(f"x^7 * x^2 = {p3 * p4}")
print(f"Expected: -x = {q-1}*x = {Zq(-1)}*xbar (since x^9 = x^(8+1) = -x)")

3. Ring-LWE: The Core Construction

Now we can state Ring-LWE. It is beautifully simple, just LWE, but with polynomials instead of vectors and matrices:

	LWE	Ring-LWE
Public randomness	Matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$	Polynomial $a(x) \in R_q$
Secret	Vector $\mathbf{s} \in \mathbb{Z}_q^n$	Polynomial $s(x) \in R_q$
Error	Vector $\mathbf{e} \in \mathbb{Z}_q^m$ (small)	Polynomial $e(x) \in R_q$ (small coefficients)
Public output	$\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$	$b(x) = a(x) \cdot s(x) + e(x)$

The Ring-LWE problem: given $(a(x), b(x))$, find $s(x)$, or even just distinguish $b(x)$ from a uniformly random polynomial.

"Small coefficients" for $s(x)$ and $e(x)$ means each coefficient is drawn from a narrow distribution centered at 0 (e.g., $\{-1, 0, 1\}$ or a small discrete Gaussian).

# --- Generate a Ring-LWE instance ---
set_random_seed(42)

n = 8
q = 17

Zq = Zmod(q)
Px.<x> = PolynomialRing(Zq)
Rq.<xbar> = Px.quotient(x^n + 1)

def small_poly(ring, n, bound=1):
    """Sample a polynomial with small coefficients in {-bound, ..., bound}."""
    coeffs = [ZZ.random_element(-bound, bound + 1) for _ in range(n)]
    return ring(coeffs)

def uniform_poly(ring, n, q):
    """Sample a uniformly random polynomial in R_q."""
    coeffs = [ZZ.random_element(0, q) for _ in range(n)]
    return ring(coeffs)

# --- Key generation ---
a = uniform_poly(Rq, n, q)         # Public: uniformly random
s = small_poly(Rq, n, bound=1)     # Secret: small coefficients
e = small_poly(Rq, n, bound=1)     # Error: small coefficients

b = a * s + e                       # Public: Ring-LWE sample

print("=== Ring-LWE Instance ===")
print(f"  Ring: Z_{q}[x] / (x^{n} + 1)")
print(f"  a(x) = {a}   (public, random)")
print(f"  s(x) = {s}   (SECRET, small coefficients)")
print(f"  e(x) = {e}   (error, small coefficients)")
print(f"  b(x) = a*s + e = {b}   (public)")
print()
print("Public key: (a(x), b(x))")
print("Secret key: s(x)")
print()

# Verify: b - a*s should equal e
recovered_e = b - a * s
print(f"Verification: b - a*s = {recovered_e}")
print(f"Matches e? {recovered_e == e}")

4. The Negacyclic Matrix: Why Polynomial Multiplication IS Matrix Multiplication

Here is the deep connection: multiplying by a fixed polynomial $a(x)$ in $R_q$ is equivalent to multiplying a vector of coefficients by a special negacyclic matrix.

If $a(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}$, then the map $s(x) \mapsto a(x) \cdot s(x) \bmod (x^n + 1)$ corresponds to multiplying the coefficient vector of $s$ by the matrix:

$$\mathbf{A}_{\text{nega}} = \begin{pmatrix} a_0 & -a_{n-1} & -a_{n-2} & \cdots & -a_1 \\ a_1 & a_0 & -a_{n-1} & \cdots & -a_2 \\ a_2 & a_1 & a_0 & \cdots & -a_3 \\ \vdots & & & \ddots & \vdots \\ a_{n-1} & a_{n-2} & a_{n-3} & \cdots & a_0 \end{pmatrix}$$

Each row is a negacyclic shift of the first row: shift right by one, and the element that wraps around gets negated.

This is why Ring-LWE is a special case of LWE: we are restricting the random matrix $\mathbf{A}$ to this structured family. One polynomial ($n$ coefficients) determines the entire $n \times n$ matrix. That is the source of the $n$-factor compression.

# --- Build the negacyclic matrix for a(x) ---

def negacyclic_matrix(poly_coeffs, n, q):
    """
    Build the n x n negacyclic matrix corresponding to multiplication
    by a(x) in Z_q[x]/(x^n + 1).
    """
    M = matrix(Zmod(q), n, n)
    for i in range(n):
        for j in range(n):
            if i >= j:
                M[i, j] = poly_coeffs[i - j]
            else:
                # Wrapping around: pick up a minus sign
                M[i, j] = -poly_coeffs[n + i - j]
    return M

# Extract coefficients of a(x) as integers
a_lift = a.lift()  # lift from quotient ring to polynomial ring
a_coeffs = [a_lift[i] for i in range(n)]
print(f"Coefficients of a(x): {a_coeffs}")
print()

A_nega = negacyclic_matrix(a_coeffs, n, q)
print("Negacyclic matrix A_nega:")
print(A_nega)
print()

# Verify: A_nega * s_vec should give the same result as a * s in R_q
s_lift = s.lift()
s_vec = vector(Zmod(q), [s_lift[i] for i in range(n)])

product_matrix = A_nega * s_vec
product_ring = a * s
product_ring_coeffs = [product_ring.lift()[i] for i in range(n)]

print(f"Matrix multiplication A_nega * s = {list(product_matrix)}")
print(f"Ring multiplication a*s coeffs   = {product_ring_coeffs}")
print(f"Match? {list(product_matrix) == product_ring_coeffs}")

# --- Visualize: negacyclic matrix vs random LWE matrix ---

# Negacyclic (structured) matrix from Ring-LWE
G1 = matrix_plot(A_nega, cmap='viridis', colorbar=True)
# Add text labels on cells
for i in range(n):
    for j in range(n):
        G1 += text(str(int(A_nega[i,j])), (j, n-1-i), fontsize=9, color='white')
G1 += text(f'Ring-LWE: Negacyclic matrix ({n}x{n})\n(determined by {n} coefficients)',
           (n/2-0.5, n+0.5), fontsize=11)

# Random (unstructured) matrix from plain LWE
A_random = random_matrix(Zmod(q), n, n)
G2 = matrix_plot(A_random, cmap='viridis', colorbar=True)
for i in range(n):
    for j in range(n):
        G2 += text(str(int(A_random[i,j])), (j, n-1-i), fontsize=9, color='white')
G2 += text(f'Plain LWE: Random matrix ({n}x{n})\n({n}x{n} = {n^2} independent entries)',
           (n/2-0.5, n+0.5), fontsize=11)

graphics_array([G1, G2]).show(figsize=[12, 5])

print(f"\nThe left matrix has visible diagonal structure: each row is a negacyclic shift.")
print(f"The right matrix has no discernible pattern: every entry is independent.")
print(f"Ring-LWE bets that the structured matrix still hides s(x) just as well.")

Misconception Callout: "Adding structure always makes crypto weaker."

This is a natural intuition, and it is not entirely wrong, structure does reduce the problem's generality, and some structured variants of lattice problems are easier. But Ring-LWE specifically has been studied intensively since Lyubashevsky, Peikert, and Regev introduced it in 2010. No known attacks on Ring-LWE exploit the ring structure when parameters are chosen correctly (i.e., $n$ is a power of 2, $q$ is chosen appropriately, and errors are large enough).

The security of Ring-LWE is supported by a worst-case to average-case reduction: solving a random Ring-LWE instance is at least as hard as solving the Shortest Vector Problem (SVP) on ideal lattices in the worst case. This is a weaker assumption than plain LWE's reduction to general lattices, but it is still considered strong enough for cryptographic use.

5. Module-LWE: The Middle Ground (and What Kyber Actually Uses)

Crypto Foreshadowing: Kyber (now standardized as ML-KEM in FIPS 203) does not use Ring-LWE directly. It uses Module-LWE, a clever middle ground.

The spectrum from less structure to more structure:

Variant	Public matrix shape	Structure	Key size
LWE	$\mathbf{A} \in \mathbb{Z}_q^{n \times n}$	None (fully random)	$O(n^2)$
Module-LWE	$\mathbf{A} \in R_q^{k \times k}$	$k \times k$ matrix of ring elements	$O(k^2 \cdot n)$
Ring-LWE	$a \in R_q$ (single element)	Maximally structured	$O(n)$

Module-LWE uses a small matrix (e.g., $k = 2, 3,$ or $4$) where each entry is a polynomial in $R_q$. Kyber uses $n = 256$ and $k \in \{2, 3, 4\}$ for its three security levels.

Why not just use Ring-LWE? Module-LWE gives a more conservative security assumption (closer to plain LWE) while still being efficient. It also lets you adjust the security level by changing $k$ without changing the ring dimension $n$.

# --- Module-LWE example with k=2 (like Kyber-512) ---

# Parameters inspired by Kyber-512 (scaled down for pedagogy)
n_mod = 8       # Ring dimension (Kyber uses 256)
q_mod = 17      # Modulus (Kyber uses 3329)
k = 2           # Module rank (Kyber-512 uses k=2)

Zq_m = Zmod(q_mod)
Px_m.<x> = PolynomialRing(Zq_m)
Rq_m.<xbar> = Px_m.quotient(x^n_mod + 1)

# Public matrix: k x k matrix of ring elements
A_mod = matrix(Rq_m, k, k, lambda i,j: uniform_poly(Rq_m, n_mod, q_mod))

# Secret: vector of k small polynomials
s_mod = vector(Rq_m, [small_poly(Rq_m, n_mod) for _ in range(k)])

# Error: vector of k small polynomials
e_mod = vector(Rq_m, [small_poly(Rq_m, n_mod) for _ in range(k)])

# Public output
b_mod = A_mod * s_mod + e_mod

print(f"=== Module-LWE Instance (k={k}) ===")
print(f"Ring: Z_{q_mod}[x] / (x^{n_mod}+1), module rank k={k}")
print()
print(f"A is a {k}x{k} matrix of ring elements:")
for i in range(k):
    for j in range(k):
        print(f"  A[{i},{j}] = {A_mod[i,j]}")
print()
print(f"s = vector of {k} small polynomials:")
for i in range(k):
    print(f"  s[{i}] = {s_mod[i]}")
print()
print(f"b = A*s + e:")
for i in range(k):
    print(f"  b[{i}] = {b_mod[i]}")
print()

# Key size comparison
bits_per = ceil(log2(q_mod))
lwe_size = (k*n_mod)^2 * bits_per
mlwe_size = k^2 * n_mod * bits_per
rlwe_size = n_mod * bits_per

print(f"Key sizes (for equivalent n_total = k*n = {k*n_mod}):")
print(f"  Plain LWE matrix:  {lwe_size} bits ({(k*n_mod)}^2 * {bits_per})")
print(f"  Module-LWE matrix: {mlwe_size} bits ({k}^2 * {n_mod} * {bits_per})")
print(f"  Ring-LWE poly:     {rlwe_size} bits ({n_mod} * {bits_per})")

6. The Number Theoretic Transform (NTT): Fast Multiplication

Naive polynomial multiplication in $R_q$ costs $O(n^2)$ coefficient operations. The Number Theoretic Transform (NTT) brings this down to $O(n \log n)$, exactly like the FFT, but over $\mathbb{Z}_q$ instead of $\mathbb{C}$.

The NTT requires a primitive $2n$-th root of unity in $\mathbb{Z}_q$, i.e., an element $\omega \in \mathbb{Z}_q$ such that $\omega^{2n} \equiv 1 \pmod{q}$ and $\omega^k \not\equiv 1$ for $0 < k < 2n$. This exists when $q \equiv 1 \pmod{2n}$.

The NTT evaluates a polynomial at the powers of $\omega$, turning multiplication into pointwise operations:

$$a \cdot b = \text{NTT}^{-1}(\text{NTT}(a) \odot \text{NTT}(b))$$

where $\odot$ denotes component-wise multiplication.

# --- NTT for multiplication in R_q = Z_q[x]/(x^n+1) ---

n_ntt = 8
q_ntt = 17   # q = 17 = 16 + 1 = 2*8 + 1, so q ≡ 1 (mod 2n). Good!

# Find a primitive 2n-th root of unity mod q
def find_primitive_root(q, order):
    """Find an element of multiplicative order `order` in Z_q."""
    Zq = Zmod(q)
    for g in range(2, q):
        w = Zq(g)^((q - 1) // order)
        if w^order == 1 and all(w^k != 1 for k in range(1, order)):
            return w
    return None

omega = find_primitive_root(q_ntt, 2 * n_ntt)
print(f"Primitive {2*n_ntt}-th root of unity mod {q_ntt}: omega = {omega}")
print(f"Verification: omega^{2*n_ntt} = {omega^(2*n_ntt)}, omega^{n_ntt} = {omega^n_ntt}")
print()

# NTT and inverse NTT (using the "negacyclic" variant for x^n+1)
def ntt_negacyclic(coeffs, omega, q, n):
    """Compute NTT for the negacyclic ring Z_q[x]/(x^n+1).
    Evaluate a(x) at omega^1, omega^3, omega^5, ..., omega^(2n-1)."""
    Zq = Zmod(q)
    result = []
    for i in range(n):
        # Evaluate at omega^(2i+1)
        point = Zq(omega)^(2*i + 1)
        val = sum(Zq(coeffs[j]) * point^j for j in range(n))
        result.append(val)
    return result

def intt_negacyclic(values, omega, q, n):
    """Inverse NTT for the negacyclic ring."""
    Zq = Zmod(q)
    n_inv = Zq(n)^(-1)
    result = []
    for j in range(n):
        coeff = Zq(0)
        for i in range(n):
            point = Zq(omega)^(2*i + 1)
            coeff += values[i] * point^(-j)
        result.append(coeff * n_inv)
    return result

# Test: multiply two polynomials using NTT
Zq_n = Zmod(q_ntt)
Px_n.<x> = PolynomialRing(Zq_n)
Rq_n.<xbar> = Px_n.quotient(x^n_ntt + 1)

a_coeffs_ntt = [3, 1, 4, 1, 5, 9, 2, 6]
b_coeffs_ntt = [2, 7, 1, 8, 2, 8, 1, 8]

# NTT approach: transform, pointwise multiply, inverse transform
a_ntt = ntt_negacyclic(a_coeffs_ntt, omega, q_ntt, n_ntt)
b_ntt = ntt_negacyclic(b_coeffs_ntt, omega, q_ntt, n_ntt)
c_ntt = [a_ntt[i] * b_ntt[i] for i in range(n_ntt)]   # Pointwise!
c_coeffs_ntt = intt_negacyclic(c_ntt, omega, q_ntt, n_ntt)

# Direct approach: use SageMath's ring multiplication
a_ring = Rq_n(a_coeffs_ntt)
b_ring = Rq_n(b_coeffs_ntt)
c_ring = a_ring * b_ring
c_ring_coeffs = [c_ring.lift()[i] for i in range(n_ntt)]

print("NTT-based multiplication:")
print(f"  NTT(a)          = {a_ntt}")
print(f"  NTT(b)          = {b_ntt}")
print(f"  NTT(a) * NTT(b) = {c_ntt}  (pointwise!)")
print(f"  INTT(result)     = {c_coeffs_ntt}")
print()
print(f"Direct ring multiplication: {c_ring_coeffs}")
print(f"Match? {list(c_coeffs_ntt) == c_ring_coeffs}")
print()
print("Key insight: NTT turns O(n^2) convolution into O(n) pointwise multiplications,")
print("plus two O(n log n) transforms. This is how Kyber achieves fast performance.")

Exercises

Exercise 1: Build a Ring-LWE Instance (Fully Worked)

Task: Construct a Ring-LWE instance in $R_q = \mathbb{Z}_{23}[x]/(x^4+1)$. Use secret $s(x) = 1 + x - x^3$ and error $e(x) = -1 + x^2$. Choose a random $a(x)$ and compute $b(x) = a(x) \cdot s(x) + e(x)$. Verify by recovering $e(x)$ from $b(x) - a(x) \cdot s(x)$.

Solution:

# === Exercise 1: Fully Worked Solution ===

# Step 1: Set up the ring
n1 = 4
q1 = 23
Zq1 = Zmod(q1)
P1.<x> = PolynomialRing(Zq1)
R1.<xbar> = P1.quotient(x^n1 + 1)
print(f"Ring: Z_{q1}[x] / (x^{n1} + 1)")
print()

# Step 2: Define the secret and error polynomials
s1 = R1([1, 1, 0, -1])   # s(x) = 1 + x - x^3   (coefficients: [1, 1, 0, -1])
e1 = R1([-1, 0, 1, 0])   # e(x) = -1 + x^2       (coefficients: [-1, 0, 1, 0])
print(f"Secret:  s(x) = {s1}")
print(f"Error:   e(x) = {e1}")
print(f"Note: coefficients of s are in {{-1, 0, 1}}, small!")
print(f"Note: coefficients of e are in {{-1, 0, 1}}, small!")
print()

# Step 3: Sample a random public polynomial a(x)
set_random_seed(123)
a1 = uniform_poly(R1, n1, q1)
print(f"Public:  a(x) = {a1}   (uniformly random)")
print()

# Step 4: Compute b(x) = a(x) * s(x) + e(x)
b1 = a1 * s1 + e1
print(f"Compute: b(x) = a(x)*s(x) + e(x) = {b1}")
print()

# Step 5: Verify, recover e from b - a*s
recovered_e1 = b1 - a1 * s1
print(f"Verify:  b(x) - a(x)*s(x) = {recovered_e1}")
print(f"Matches e(x)? {recovered_e1 == e1}")
print()
print("Public key: (a(x), b(x)), these two polynomials are revealed.")
print("Secret key: s(x), this polynomial must stay secret.")
print("An attacker sees (a(x), b(x)) and must find s(x). The noise e(x) makes this hard.")

Exercise 2: Negacyclic Matrix and Key Size (Guided)

Task: For the Ring-LWE instance from Exercise 1 (with $n=4$, $q=23$):

1. Build the $4 \times 4$ negacyclic matrix $\mathbf{A}_{\text{nega}}$ corresponding to $a(x)$.

2. Verify that $\mathbf{A}_{\text{nega}} \cdot \mathbf{s} + \mathbf{e} = \mathbf{b}$ where $\mathbf{s}, \mathbf{e}, \mathbf{b}$ are coefficient vectors.

3. Compute the ratio of key sizes: plain LWE ($n^2$ entries) vs Ring-LWE ($n$ entries).

Hints:

• Use the negacyclic_matrix() function defined earlier.

• Extract coefficient vectors using .lift() followed by indexing.

• The key size ratio should be exactly $n$.

# === Exercise 2: Fill in the blanks ===

# Step 1: Build the negacyclic matrix
a1_lift = a1.lift()
a1_coeffs = [a1_lift[i] for i in range(n1)]
# TODO: call negacyclic_matrix with the right arguments
# A1_nega = negacyclic_matrix(???, ???, ???)

# Step 2: Extract coefficient vectors and verify
# TODO: build s_vec, e_vec from s1, e1 using .lift()
# s1_vec = vector(Zmod(q1), [???])
# e1_vec = vector(Zmod(q1), [???])

# TODO: compute b_vec = A1_nega * s1_vec + e1_vec and compare with b1's coefficients
# b1_vec = ???

# Step 3: Key size comparison
# TODO: print the ratio n^2 / n and confirm it equals n
print("Uncomment and fill in the code above to complete this exercise.")

Exercise 3: NTT Multiplication (Independent)

Task: Work in $R_q = \mathbb{Z}_{17}[x]/(x^8+1)$.

1. Find a primitive 16th root of unity $\omega$ modulo 17 (use find_primitive_root).

2. Define $f(x) = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7$ and $g(x) = 1 + x$.

3. Compute $f(x) \cdot g(x)$ in $R_q$ using:

   • (a) Direct ring multiplication in SageMath.

   • (b) NTT-based multiplication using ntt_negacyclic and intt_negacyclic.

4. Verify both methods give the same result.

5. Bonus: What is $f(x) \cdot g(x)$ conceptually? Note that $f(x) = \frac{x^8 - 1}{x - 1}$ and think about what happens when you multiply by $(1+x)$ modulo $x^8+1$.

No hints for this one, you have all the tools you need from the notebook above.

# === Exercise 3: Your solution here ===

# (Write your code below)

Summary

Concept	Key idea
Key-size bottleneck	Plain LWE requires $O(n^2)$ elements for the public matrix, meaning megabytes of key material at cryptographic parameters
The ring $R_q$	Working in $\mathbb{Z}_q[x]/(x^n+1)$ (with $n$ a power of 2) replaces the random matrix with a single polynomial, compressing keys by a factor of $n$
Negacyclic structure	Multiplying by $a(x)$ in $R_q$ is equivalent to multiplying by a negacyclic matrix. One polynomial ($n$ coefficients) determines the entire $n \times n$ matrix.
Module-LWE	The middle ground used by Kyber/ML-KEM: a small $k \times k$ matrix of ring elements, balancing efficiency with conservative security
NTT acceleration	The Number Theoretic Transform enables $O(n \log n)$ polynomial multiplication, making Ring-LWE-based schemes competitive with classical cryptography in speed

Crypto Foreshadowing: The NIST standard ML-KEM (formerly Kyber, FIPS 203) uses Module-LWE over the ring $\mathbb{Z}_{3329}[x]/(x^{256}+1)$ with module ranks $k \in \{2, 3, 4\}$. In the next notebook, we will see how Ring-LWE becomes a complete key encapsulation mechanism.

Next: Kyber / ML-KEM Overview