Appendix D: Solutions for Chapter 9

This page collects solutions and editorial notes for the exercises in Chapter 9: Ring-LWE and Module-LWE. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the ring_lwe package under solutions/ch09-ring-lwe. From a clone of the companion repository, pytest tests/ch09 runs its suite. Appendix C has the setup.

Exercise 1

The exercise walks the calculation. Key checks: $x^9 \equiv x \cdot x^8 \equiv x \cdot (-1) = -x \equiv 16 x \pmod{x^8 + 1, 17}$, and $x^8 \equiv -1 \equiv 16 \pmod{x^8 + 1, 17}$. The negacyclic minus sign is the difference between this ring and the cyclic ring $\mathbb{Z}[x]/(x^n - 1)$. In the cyclic ring $x^9 \equiv x$ rather than $-x$.

def ring_mul(f, g, n=8, q=17):
    out = [0] * n
    for i in range(n):
        for j in range(n):
            k = i + j
            sign = 1 if k < n else -1
            out[k % n] = (out[k % n] + sign * f[i] * g[j]) % q
    return out


f = [0] * 8; f[5] = 1   # x^5
g4 = [0] * 8; g4[4] = 1  # x^4
g3 = [0] * 8; g3[3] = 1  # x^3
print(ring_mul(f, g4))
print(ring_mul(f, g3))
# ==> [0, 16, 0, 0, 0, 0, 0, 0]
# ==> [16, 0, 0, 0, 0, 0, 0, 0]

Exercise 2

The negacyclic NTT evaluates $f(x)$ at the odd powers of $\psi$, where $\psi$ is a primitive $2n$-th root of unity in $\mathbb{Z}_q$. For $f = x$, the evaluation is $f(\psi^{2k+1}) = \psi^{2k+1}$, which gives the sequence $(\psi^1, \psi^3, \psi^5, \psi^7)$ modulo $q$. With $\psi = 2, q = 17$: $\psi^1 = 2$, $\psi^3 = 8$, $\psi^5 = 32 \bmod 17 = 15$, $\psi^7 = 128 \bmod 17 = 9$.

print([pow(2, 2 * k + 1, 17) for k in range(4)])
# ==> [2, 8, 15, 9]

Exercise 3

The verification is a transcription of the Module-LWE definition. For each output row $i$, recompute $\mathbf{b}[i] = \sum_{j=0}^{k-1} \mathbf{A}[i,j] \cdot \mathbf{s}[j] + \mathbf{e}[i]$ in the ring $R_q$, then assert termwise equality with the package-returned $\mathbf{b}$. The test in tests/ch09/test_module_collapses_to_ring.py does this for $k = 1, 2, 3$ and is the reference. Writing it yourself reinforces where the two indices go. The $m$ rows are the samples; the $k$ columns are the components of the secret. At $k = 1$ each row is a single ring product, so the $m$ rows are $m$ Ring-LWE samples sharing one secret. At $k > 1$ each row sums $k$ ring products against a rank-$k$ secret, and those $k$ terms are never observed separately. At this exercise’s $(k, m) = (3, 4)$ that is four samples, not three.

Exercise 4

The condition $16 \mid q - 1$ is the existence requirement for a primitive $16$-th root of unity in $\mathbb{Z}_q^*$, which has order $q - 1$. The primes below 200 satisfying this are $17, 97, 113, 193$. Once $\psi$ is found, the order check $\psi^{16} \equiv 1, \psi^8 \not\equiv 1$ rules out roots of order 1, 2, 4, or 8. The order must divide 16 and be larger than 8, so the order is 16.

def is_prime(n):
    return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1))


primes = [q for q in range(3, 200) if is_prime(q) and (q - 1) % 16 == 0]
print(primes)
# ==> [17, 97, 113, 193]