Exercises

Answers follow each question. Try them before reading on, since the whole point of small parameters is that these are checkable by hand.

1. A second basis of $\mathbb{Z}^2$

Let $B$ be the identity matrix and

$$B' = \begin{pmatrix} 1 & 1 \\ 2 & 3 \end{pmatrix}.$$

Verify that $B'$ generates the same lattice $\mathbb{Z}^2$ by finding a unimodular $U$ with $B' = BU$.

Answer. Since $B$ is the identity, $U = B'$ itself. Its determinant is

$$\det U = 1 \cdot 3 - 1 \cdot 2 = 1 ,$$

which is $\pm 1$, so $U$ is unimodular and $\mathcal{L}(B') = \mathcal{L}(B) = \mathbb{Z}^2$ by the rule in Good and Bad Bases.

Sanity-check it the other way. The columns $(1,2)$ and $(1,3)$ are both in $\mathbb{Z}^2$, so $\mathcal{L}(B') \subseteq \mathbb{Z}^2$. And $(1,0) = 3(1,2) - 2(1,3)$ while $(0,1) = (1,3) - (1,2)$, both integer combinations, so $\mathbb{Z}^2 \subseteq \mathcal{L}(B')$.

02.2. The shortest vectors of the running lattice

For $b_1 = (3,1)$ and $b_2 = (1,2)$, list the lattice points closest to the origin by norm. Confirm the shortest length and count how many points achieve it.

Answer. Ordered by Euclidean norm, the closest non-zero points are

$$(-2, 1),\; (-1,-2),\; (1,2),\; (2,-1) \quad \text{at } \sqrt{5} \approx 2.236,$$

then

$$(-3,-1),\; (-1,3),\; (1,-3),\; (3,1) \quad \text{at } \sqrt{10} \approx 3.162,$$

then $(-4,2)$ and $(-2,-4)$ at $\sqrt{20} \approx 4.472$.

So $\lambda_1 = \sqrt{5}$, achieved by exactly four points. They are two vectors and their negations: $\pm(1,2)$ and $\pm(2,-1)$.

Four rather than two because $(1,2)$ and $(2,-1)$ are genuinely different lattice vectors that happen to share a length. That is a coincidence of this lattice, not a general rule.

03.3. A determinant-1 lattice with a long shortest vector

Construct $\mathcal{L} \subset \mathbb{R}^2$ with $\det \mathcal{L} = 1$ whose shortest vector is longer than $1$. How close can you get to Minkowski's bound of $\sqrt{2}$?

Answer. The best packing in the plane is the hexagonal lattice. Take

$$b_1 = \left(\,3^{1/4},\; 0\,\right), \qquad b_2 = \left(\tfrac{1}{2} \cdot 3^{1/4},\; \tfrac{\sqrt{3}}{2} \cdot 3^{1/4}\right).$$

Both have length $3^{1/4} \approx 1.316$, the angle between them is $60^\circ$, and the determinant is $3^{1/4} \cdot \frac{\sqrt{3}}{2} \cdot 3^{1/4} = \frac{\sqrt{3}}{2}\sqrt{3} = \frac{3}{2}$. Rescale by $\sqrt{2/3}$ to bring the determinant to $1$, and the shortest vector becomes

$$3^{1/4}\sqrt{2/3} \;=\; \left(\tfrac{4}{3}\right)^{1/4} \;\approx\; 1.0746 .$$

Minkowski's bound at $n = 2$, $\det = 1$ is $\sqrt{2} \approx 1.414$, so the hexagonal lattice reaches about $76\%$ of it. That gap is not slack in your construction. The hexagonal lattice is provably optimal in two dimensions, so $(4/3)^{1/4}$ is the true maximum and Minkowski's bound is simply not tight.

04.4. Why noise is not optional

Take the worked LWE instance with $s = (5, 11, 2)$ but set every error to zero. Recover $s$.

Answer. With no noise the samples are exact, so $b = (4, 7, 0)$ and

$$A = \begin{pmatrix} 1 & 4 & 3 \\ 2 & 0 & 7 \\ 6 & 9 & 12 \end{pmatrix}.$$

The determinant of $A$ modulo $17$ is $12$, which is non-zero, so $A$ is invertible and

$$s = A^{-1} b \bmod 17 = (5, 11, 2).$$

Exact, in one step.

Compare with Noise Breaks Linear Algebra, where the same inversion on the noisy $b' = (5, 7, 16)$ returned $(13, 14, 7)$. Three errors of magnitude at most one turned a one-step solve into an unrelated answer.

05.5. The variance of the centred binomial

Show that $X \sim \text{CBD}_\eta$ has variance $\eta/2$.

Answer. Write $X = \sum_{i=1}^{\eta}(a_i - b_i)$ with all bits independent and uniform.

Each term $a_i - b_i$ takes the value $-1$ with probability $1/4$, $0$ with probability $1/2$, and $+1$ with probability $1/4$. Its mean is zero by symmetry, and its variance is

$$\mathbb{E}[(a_i - b_i)^2] \;=\; \tfrac{1}{4}(1) + \tfrac{1}{2}(0) + \tfrac{1}{4}(1) \;=\; \tfrac{1}{2}.$$

The $\eta$ terms are independent, and variances of independent variables add, so

$$\operatorname{Var}(X) \;=\; \eta \cdot \tfrac{1}{2} \;=\; \tfrac{\eta}{2}.$$

Checking directly: $\eta = 2$ gives variance $1.0$, and $\eta = 3$ gives $1.5$. Both match.

6. Why a larger $q$ makes LWE easier

Argue why raising $q$ while holding the error distribution fixed weakens LWE. What is the role of $\sigma/q$?

Answer. What matters is not the absolute size of the noise but its size relative to the modulus, the ratio $\sigma/q$.

The noise hides the secret by making each equation ambiguous. If $\sigma$ stays fixed while $q$ grows, each error covers a smaller fraction of $\mathbb{Z}_q$, so each sample pins the secret down more tightly. In the extreme, $q$ enormous against $\sigma$ means the noise barely perturbs anything and the system is nearly exact, which is solvable.

Geometrically, from The Learning With Errors Problem: the observed $b$ sits at distance $\|e\|$ from a lattice point, and the lattice spacing scales with $q$. Larger $q$ with fixed $\sigma$ means the target sits proportionally closer to its lattice point, and bounded-distance decoding gets easier as that ratio shrinks.

This is why ML-KEM's small $q = 3329$ is a security-conscious choice rather than only an efficiency one. It keeps $\sigma/q$ comfortably large while also keeping coefficients at 12 bits.

7. The lattice $D_3$

Let $D_3 = \{(x_1,x_2,x_3) \in \mathbb{Z}^3 : x_1 + x_2 + x_3 \text{ even}\}$. Exhibit a basis and compute the determinant.

Answer. A basis is

$$(1,-1,0), \qquad (1,1,0), \qquad (0,1,-1).$$

Each has an even coordinate sum, so each is in $D_3$, and integer combinations preserve that parity, so the lattice they generate is inside $D_3$.

The determinant of the matrix with those rows is $2$.

That value is the sanity check on completeness. $D_3$ is exactly half of $\mathbb{Z}^3$, keeping one parity class out of two, and $\mathbb{Z}^3$ has determinant $1$. A sublattice of index $2$ has determinant $2$, which is what came out, so the three vectors generate all of $D_3$ and not a smaller piece of it.