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]

Exercise 5

The identity holds at $2$ because $2^4 + 1 = 17 \equiv 0 \pmod{17}$, so reducing modulo $x^4 + 1$ does not change a polynomial’s value at $2$. What changes is the error’s image. With each $e_i \in \{-1, 0, 1\}$, $e(2) = e_0 + 2e_1 + 4e_2 + 8e_3$ takes every integer value from $-15$ to $15$, so the widened window holds $31$ values, more than the $17$ elements of $\mathbb{Z}_{17}$. Every residual passes, and the test keeps all $17$ guesses on Ring-LWE samples and on uniform ones alike. It distinguishes nothing. The other roots, $8$, $15$ and $9$, behave the same way, because their powers are $1$, $2$, $4$ and $8$ up to sign and order.

What made $x = 1$ useful is that every power of $1$ is $1$, so $e(1)$ is a plain sum of $n$ short coefficients and stays within $nB = 4$ of $0$, which is $9$ residues out of $17$. No root of $x^n + 1$ is $1$, since $1^n + 1 = 2$, and when $2n \mid q - 1$ the roots it does have are the odd powers of $\psi$ at which the NTT evaluates. The window test needs a root at which a short error keeps a short image. That claim is about this test only. At the toy parameters $e(2)$ still lands on some residues more often than others, so a test that counts how often each residual appears could separate the two kinds of sample, given enough of them.