Appendix D: Solutions for Chapter 8

This page collects solutions and editorial notes for the exercises in Chapter 8: The LWE problem. 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 lwe package under solutions/ch08-lwe. From a clone of the companion repository, pytest tests/ch08 runs its suite. Appendix C has the setup.

Exercise 1

The expected behavior is not a gradient. Over 100 seeds at each of $B = 1$, $3$, $10$ and $30$, $\mathrm{solve\_mod\_q}$ returns None on 100 of 100 instances at every width, and never returns the true secret. Recovery has already failed completely at $B = 1$, which is the point the chapter’s own worked block makes when it prints recovered noisy = None. There is no $B$ at which the solver degrades gracefully. A single unit of noise is enough. The “wrong secret” outcome stays rare because $\mathrm{solve\_mod\_q}$ either finds a candidate satisfying every consistency row or reports failure. Spurious-but-consistent secrets are unlikely with $m - n = 4$ extra check rows.

The residual distribution is the reason, and it also does not change with $B$. The consistency check on the last $m - n$ rows asks $A_{\text{check}} s \equiv b_{\text{check}} \pmod q$ exactly. Those rows do not carry the raw error: forward elimination replaces each one with a $\mathbb{Z}_q$-linear combination of every error coordinate, scaled by pivot inverses. Multiplying a small error by an arbitrary element of $\mathbb{Z}_q$ destroys its smallness. Measured over 200 seeds, the mean absolute residual in symmetric representatives is $24.2$ at $B = 1$ and $24.3$ at $B = 30$. A value drawn uniformly from $\mathbb{Z}_{97}$ averages $24.2$. The fraction of nonzero consistency rows runs from $98.4\%$ to $99.1\%$ across the same range. The residuals are indistinguishable from uniform as soon as any noise is present, which is why the failure is immediate rather than progressive.

A strong answer connects that to the final part of the question. The check detects noise but extracts nothing from it, so it is not an attack: it says an instance is noisy without narrowing the search for $s$. The regime where a consistent but wrong secret comes back is $m = n$, where there are no consistency rows left to fire, and it is reached by varying $m$ rather than $B$.

Exercise 2

The brute force enumerates $q^n$ candidate secrets. For $(q, n) = (97, 4)$ the loop runs $97^4 = 88{,}529{,}281$ iterations, each computing $\lVert A s - b \rVert_\infty$ in $O(m n)$ work. Write it as a per-candidate Python loop and it takes about fourteen minutes at roughly $10^5$ candidates per second; batch the candidates through numpy and the same enumeration finishes in about thirty seconds. Either is fine for one instance, and neither scales.

On a real LWE pair the minimum residual is at most $B$, achieved at the true secret. On a uniform pair it is not $q/2$, and assuming so would break the distinguisher. The minimum is taken over $q^n$ candidates, so it is the smallest of about $88.5$ million draws. A residual of $\infty$-norm at most $t$ has probability $((2t+1)/q)^m$. Setting $q^n \cdot ((2t+1)/q)^m \approx 1$ at $(n, q, m) = (4, 97, 8)$ gives $t \approx 4$. Measured over six uniform pairs, the minimum residual came out $4$, $4$, $5$, $5$, $5$, $6$. The distinguisher still separates cleanly at the threshold $B = 1$, but the margin is one unit against four, not one against forty-eight.

Cost is $O(m n \cdot q^n)$. For fixed $n$ this is polynomial in $q$. For fixed $q$ it is $O(q^n)$, exponential in $n$. ML-KEM-768 is Module-LWE at module rank $3$ over a degree-$256$ ring, so its flat-LWE dimension is $3 \cdot 256 = 768$. The brute force is infeasible there by many hundreds of orders of magnitude, and lattice cryptography rests on exactly that gap.

print(97 ** 4)
# ==> 88529281

Exercise 3

The expected output: $\lvert \det B \rvert = 97^4 = 88{,}529{,}281$, and $A^\top v \equiv 0 \pmod{97}$ for every row $v$ of $B$. The construction depends on $A$ having full column rank modulo $q$. In the chapter’s notation, $\Lambda_q^\perp(A) = \{v \in \mathbb{Z}^m : A^\top v \equiv 0 \pmod q\}$ has determinant $q^n$ exactly when $A$ has rank $n$ modulo $q$. If $A$ is rank-deficient mod $q$, the lattice has smaller determinant and the constructed basis fails the orthogonality check on the extra rows.